חידה מראיון

[janemayers]

חידה מראיון

היי, שאלו אותי את השאלה הבאה: בסוכנות לליהוק שחקנים רוצים מבנה נתונים שיחזיר את השחקן המבוגר ביותר במאגר בטווח גבהים מסוים (טווח של שני מספרים ממשיים). הבנייה הראשונית של מבנה הנתונים תארך O nlogn זמן והתשובה לכל שאילתא תארך O logn. אח"כ שאלו את אותה שאלה עם בנייה בזמן בלתי מוגבל ותשובה לשאילתא בזמן קבוע. די הסתבכתי עם זה. מה דעתכם? מה הייתם מציעים? תודה, ג'יין

 

[maverick 42]

בגדול

נראה לי שהדרך הראשונה דורשת לחלק את השחקנים לקבוצות של טווחי גבהים, ואז לחפש את השחקן המבוגר ביותר בטווח הנדרש, ואילו בדרך השניה גם מחלקים לפי טווחי גבהים, אבל דואגים שהסדר של השחקנים בתוך הטווח יהיה לפי גיל, ככה שהמבוגר ביותר יהיה בראש הרשימה.

 

[janemayers]

בקטן

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

 

[ELIELI22]

רק אני לא רואה כאן בעיה.

או שאני חלוד ומדמיין דברים אחרים.?

 

[ELIELI22]

שאלה?

כל אדם יש 2 נתונים לגביו. גובהה וגיל לטובת מבנה הנתונים והשאילתות?

 

[janemayers]

כן. כל הנתונים ידועים מראש ולא משתנים אף פעם.

 

[vicz]

תכתוב את הרעיון

 

[egozi13]

מעניין מאוד

לאיזה תפקיד ראיינו אותך. קשה לי לחשוב על הרבה תפקידים שתשובה מלאה לשאלה כזו חשובה לגביהם ... התשובה שאני כמראיין הייתי רוצה לשמוע היא: טבלה בבסיס נתונים, עם שאילתת SQL נלווית ... בשביל המראיין הפלצן אני אנסה לחשוב על משהו, אפילו שאני חלוד מאוד - עשיתי את הקורס בפתוחה לפני 4-5 שנים, ומאז אני עסוק בכתיבת תוכנות שעובדות ונותנות ערך מוסף ללקוחות, ולא בסיבוב עצים אדומים-שחורים. למקרה הראשון יש כנראה שילוב של ערימות מינימום ומקסימום, או עצ חיפוש שכל צומת מצביעה על עץ חיפוש אחר, דברים כאלו. אין לי כח לחשוב על זה עכשיו. למקרה השני - מייצרים matrix ובכל תא מחשבים את הגיל המקסימלי בין הגובה המבוטא בשורה לגובה המבוטא בטור.

 

[vinney]

יש לך משהו נגד עצים אדומים-שחורים?

כי אני די בטוח שהשתמשת בהם לא פעם ולא פעמיים במהלך כתיבת התוכנות האלה שנותנות את הערך המוסף. מה זה הזלזול הזה?

 

[egozi13]

אין לי דבר נגדם - להיפך, זה מבנה נתונים מרהיב

אבל למעט לטובת האוניברסיטה, לא היה לי את העונג לממש או לשתמש (ישירות) בעץ א"ש לייצוג נתונים בזיכרון. אם ראיינו את הבחורה לתפקיד של תכנות WEB, מערכות מידע ושאר ירקות (המהווים חלק ניכר, אם לא את רוב המשרות בשוק) אז סוג השאלות צריך להיות אחר לגמרי.

 

[vinney]

יש לך הבנה בעייתית משהו של שוק

העבודה. אני לא יודע למה אתה מתכוון ב"שאר הירקות", אבל תפקידי WEB זה מיעוט קטן במשרות בשוק.

 

[janemayers]

מטריצה?

איך יוצרים מטריצה עם אינסוף שורות ואינסוף עמודות? הרי אנחנו צריכים להחזיר תשובה לכל שני ערכים ממשיים... הטווח אינו מוגבל.

 

[egozi13]

מס' האנשים הוא סופי

המטריצה היא של גבהי האנשים. את הולכת לטור/שורה של האיש שגובהו כגובה הקלט או טיפהל'ה פחות

 

[HaifaMan]

תגדיר "טיפהלה" פחות?

יש לך מטריצה עם 100 עמודות מסודרת לפי הגבהים. עכשיו כקלט קיבלת 1.78. איך תדע בזמן קבוע לאיזו עמודה לפנות? לא נראה לי שהרעיון שלך מוגדר בשלמות.

 

[egozi13]

אוף אני עדיין חושב "מעשי" ולא "אקדמי"

אם מדובר בגובה אז זה לא ממש תחום רציף (אלא מטר.סנטימטר) ואני יכול לגבב לפי מודולו 10. זה למעשה מתאר רשימה של כל קבוצות הגובה הקיימות (עם הגיל המקסימלי בקבוצה), מסודרות בטבלת גיבוב על מודולו 10 למשל. ואו אני ממש חלוד. מזל שעל המדף לידי יש את קורמן/ליזרסון/ריבסט ... לגבי המקרה הראשון אולי כך? 1. בנית עץ חיפוש לפי גובה השחקנים עלות: nlogn 2. אם השורש קטן מהתחום: חיפוש "ימינה" עד השחקן הגבוה ביותר בתחום, תוך כדי שמירת מצביע למבוגר ביותר מרגע הכניסה לתחום. אם השורש גדול מהתחום: חיפוש "שמאלה" עד השחקן הנמוך ביותר בתחום, תוך כדי שמירת מצביע למבוגר ביותר מרגע הכניסה לתחום. אם השורש בתחום: חיפוש ימינה עד לגבוה ביותר, שמאלה עד לנמוך ביותר, ושמירת המצביע למבוגר. עלות: logn +logn

 

[HaifaMan]

2 שלך לא טוב

נגיד ואתה מחפש את השחקן הכי גבוה - תמיד תרד ימינה. בהכרח תפספס כך שחקנים שלא נמצאים לאורך המסלול הזה, ויכול להיות שדווקא אחד מהם זה מי שאתה צריך להחזיר.

 

[egozi13]

לא הבנתי למה

שים לב ששלב 2 מתחיל ב fork: אם השורש קטן מהתחום המבוקש, אז כל התחום נמצא מימין, ואני לא אפספס אף אחד. אם השורש גדול מהתחום, אז כל התחום משמאל, ובחיפוש שמאלא לא אפספס אף אחד אם השורש בתוך התחום, נחפש ימינה וגם שמאלה (2logn)

 

[HaifaMan]

אם השורש קטן מהתחום

ותת העץ הימני שלו הוא בעל 3 צמתים (עוד שורש ושני בנים, שמאלי וימני) - אז בהכרח תפספס אחד מהם לא?

 

[egozi13]

למה לפספס?

בסריקה תוכית של תת העץ הימני האלגוריתם יעבור על כל הצמתים בתת העץ מהנמוך לגבוה.

 

[HaifaMan]

כל הצמתים לא שווה לo d ?

אם תעבור על כל הצמתים בתת העץ הימני (נניח שהם בערך חצי מסה"כ הצמתים ונניח שכולם בתחום המבוקש) לא חרגת מהסיבוכיות?