נושאים פעיליםנושאים פעילים  הצגת רשימה של חברי הפורוםרשימת משתמשים  חיפוש בפורוםחיפוש  עזרהעזרה
  הרשמההרשמה  התחברותהתחברות RSS עדכונים
תיכנות
RSS UnderWarrior Forums : RSS תיכנות
נושא

נושא: חידה מראיון עבודה

 שליחת תגובהשליחת נושא חדש
כותב
הודעה << נושא קודם | נושא הבא >>
ג'יין
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 03 March 2008 בשעה 21:41 | IP רשוּם
ציטוט ג'יין
יותר קלי לי באנגלית, מקווה שזה לא משנה:

You are given an array with n actors, each has a weight and an age.

You should build a data structure that has only one function: for any two real numbers i,j you should be able to return the youngest actor in this range of heights (if exists).

You can take as much time as you want (finite...) to build the data structure and you may assume that no changes will be made after initialization.

Any ideas?

Thanks.
חזרה לתחילת העמוד הצג את כרטיס החבר של ג'יין חפש הודעות אחרות של ג'יין בקר בדף הבית של ג'יין
 
ג'יין
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 03 March 2008 בשעה 22:10 | IP רשוּם
ציטוט ג'יין

כמובן ששכחתי את החלק החשוב ביותר -

התשובה לשאילתא צריכה להינתן בזמן קבוע (O של 1).
חזרה לתחילת העמוד הצג את כרטיס החבר של ג'יין חפש הודעות אחרות של ג'יין בקר בדף הבית של ג'יין
 
Dark Phoenix
משתמש פעיל
משתמש פעיל


הצטרף / הצטרפה: 22 December 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 50
נשלח בתאריך: 03 March 2008 בשעה 23:05 | IP רשוּם
ציטוט Dark Phoenix
הדרך היחידה שאני חושב עליה זה מילון דו מימדי, שזה בעצם טבלה של כל טווחי הגבהים האפשריים. לכל תא A(i,j), יהיה את ערך השחקן הצעיר ביותר בטווח הזה. מעבר לזה אני לא מצליח למצוא פתרון בתנאיים שלך
חזרה לתחילת העמוד הצג את כרטיס החבר של Dark Phoenix חפש הודעות אחרות של Dark Phoenix
 
ג'יין
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 03 March 2008 בשעה 23:28 | IP רשוּם
ציטוט ג'יין

חשבתי על מטריצה, אבל זה לא נראה לי אפשרי כי צריך תא עבור כל זוג ערכים (טווח גבהים), ויש אינסוף זוגות כאלה (כל זוג ממשיים).

ממש מוזר, הא?
חזרה לתחילת העמוד הצג את כרטיס החבר של ג'יין חפש הודעות אחרות של ג'יין בקר בדף הבית של ג'יין
 
11010010110
פורומיסט על
פורומיסט על
סמל אישי

הצטרף / הצטרפה: 23 April 2006
משתמש: מנותק/ת
הודעות: 2621
נשלח בתאריך: 03 March 2008 בשעה 23:42 | IP רשוּם
ציטוט 11010010110
יש בעיה קטנה - i ו j הם ממשיים

בהתחלה נבנה פונקציות f ו g (אם הטווח כולל את אחד
מהקצוות ולא את השני אז זה תהיה אותה פונקציה)

כל פונקציה כזאת תקבל מספר ממשי ותיתן מספר טבעי n -
האינדקס של העמודה או השורה המתאימים במערך של השחקנים

את 2 ה n ים ניתן כקלט לפתרון של Dark Phoenix

הפונקציות (בתכלס - מערכים ממויינים) ייבנו בשלב האתחול
של המערכת

הבעיה אם כן היא בעייה של חיפוש במערך ממויין. ואז זה לא
O 1 אלא לפחות O log N וזה לא מתאים

ניתן להתחכם אם הפונקציות כך שיהיה מסובך להגדיר אותן כ
חיפוש אבל הייתי מחפש פתרון אחר - בכיוון של איך לקודד את
זה במס' ממשיים
חזרה לתחילת העמוד הצג את כרטיס החבר של 11010010110 חפש הודעות אחרות של 11010010110
 
Dark Phoenix
משתמש פעיל
משתמש פעיל


הצטרף / הצטרפה: 22 December 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 50
נשלח בתאריך: 04 March 2008 בשעה 06:54 | IP רשוּם
ציטוט Dark Phoenix
אוי משום מה בלבלתי את זה עם מספרים טבעיים.
ובעקרון O(1) זה רק חישוב או שליפה, או אפילו מספר מצומצם שלהם. כשצריך לחשב מינימום בתחום צריך לעבור על התחום הזה ולמצוא את המינימלי. מה שהצעתי זה דרך של שליפה, מה שקורה ב-O(1) אבל מאוד לא יעיל. מעבר לזה, כמו שאמרו מקודם, זה כנראה חיפוש בינארי או חיפוש פיבונאצ'י בסדר גודל לוגריתמי
חזרה לתחילת העמוד הצג את כרטיס החבר של Dark Phoenix חפש הודעות אחרות של Dark Phoenix
 

אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם

  שליחת תגובהשליחת נושא חדש
גרסת הדפסה גרסת הדפסה

קפיצה לפורום
אינך יכול/ה לשלוח נושאים חדשים בפורום זה
אינך יכול/ה להגיב לנושאים בפורום זה
אינך יכול/ה למחוק את הודעותיך ותגוביך בפורום זה
אינך יכול/ה לערוך את הודעותיך ותגובותיך בפורום זה
אינך יכול/ה לצור סקרים בפורום זה
אינך יכול/ה להצביע בסקרים בפורום זה