קיימים 25 סוסים ורוצים למצוא את שלושת הסוסים המהירים ביותר.
כדי לקבוע זאת עושים מירוץ בינהם אך יש הגבלה שבכל מקצה יכולים לרוץ 5 סוסים בלבד. מהי הכמות המינימלית של מקצים שצריך לעשות כדי לדעת בוודאות מיהם שלושת הסוסים המהירים ביותר.
תשובות
הוסף תשובה
|
לצפיה בתשובות
מרץ 2021
תחילה יש לחלק את הסוסים לחמישה מקצים. כל מקצה כזה נותן לנו שלושה סוסים הנמצאים במקום הראשון השני והשלישי לאותו מקצה. אלו שהגיעו למקום הרביעי והחמישי אפשר להתעלם מהם כי הם בוודאות לא הכי מהירים.
לאחר מכן ניקח את כל המקומות הראשונים של החמישה מקצים הראשונים ונבחן אותם במקצה נוסף. המנצח של המקצה השישי הוא בוודאות הסוס המהיר ביותר. כדי לדעת בוודאות מי המקום השני והשלישי יש לעשות מקצה אחרון בו ישתתפו:
1. המקום שני מהמקצה השישי.
2. המקום השלישי מהמקצה השישי.
3. המקום השני מהמקצה שממנו הגיע הסוס הכי מהיר.
4. המקום השלישי מהמקצה שממנו הגיע הסוס הכי מהיר.
5.המקום השני מהמקצה שממנו הגיע הסוס שהגיע למקום השני במקצה השישי.
בסוף המקצה השביעי נדע שמי שהגיע למקום הראשון והשני הם הסוסים השני והשלישי הכי מהירים.
את המקצה האחרון אנחנו עושים כי יכול להיות שמי שהגיע למקום שני מהמקצה שממנו הגיע הסוס הכי מהיר, יותר מהיר מהסוס שהגיע למקום שני במקצה המנצחים (המקצה השישי). אותו הדבר לגבי מקום שלישי.
מבחן עם עוד שלושה או ארבעה סטודנטים שמהלכן יוצאים ומבצעים ראיון פרונטלי מול ראש הצוות.
שאלות מתוך הראיון
שדה תעופה יכול להכיל N מטוסים ברגע נתון. נתונה רשימות זמני המראות ורשימת זמני נחיתות כשני מערכים. בדוק האם הרשימות חוקיות כך שאין חריגה מ-N.
תשובות
הוסף תשובה
|
לצפיה בתשובות
מאי 2020
בהנחה שמתחילים את היום ב-0 מטוסים, ניתן למיין את שני המערכים באמצעות RADIX SORT ובכך לבצע זאת באו גדול של N זמן. לאחר מכן לעבור בלולאה על רשימת ההמראות:
עבור כל נחיתה, נוריד אחד ממונה המטוסים שלנו, אך נזיז את המצביע לאיבר במערך ההמראות עד לשעת הנחיתה שעליה אנו מסתכלים, ונוריד את המונה מטוסים שלנו.
אם באיזה שהוא שלב עברנו את N, לא חוקי
אם ירדנו מ-0, הקלט לא חוקי
אחרת הרשימה חוקית
ראיון לתפקיד 
