100 אנשים נכנסים לחדר עם 100 מתגים כבויים אחד אחרי השני.
האדם הראשון משנה את המצב של כל המתגים.
האדם השני משנה את המצב של כל מתג שני.
האדם השלישי משנה את המצב של כל מתג שלישי וכך הלאה.
איזה מתגים יהיו דלוקים אחרי שכל 100 האנשים יעברו ?
הראיון נמשך 3 שעות.
בחלק הראשון היה מראיין שתיאר על החברה בקצרה, שאל מעט שאלות כלליות, ולאחר מכן נתן לי מבחן תכנות ב-C, כאשר בכל פעם שעניתי על שאלה הוא עבר עליה יחד איתי ושאל דברים נוספים על הדרך.
בחלק השני הגיעה מראיינת ששאלה אותי שאלות כלליות, תיארה על החברה בהרחבה, ולבסוף נתנה לי שאלת "הצע אלגוריתם".
אומנם הראיון היה ארוך, אך המראיינים היו מאוד נחמדים ונינוחים, דבר שלא מובן מאליו.
שאלות מתוך הראיון
1. נתונה פונקציה, וצריך למצוא מה לא תקין בה.
2. נתון קטע קוד ושואלים מה יהיה הפלט. אחר כך צריך לתקן אותו כדי לקבל את מה
שבאמת היינו מצפים.
3. מימוש פונקציה שמבצעת swap בין 2 *מצביעים* + מימוש של קריאה לפונקציה.
4. מימוש פונקציה שמקבלת כקלט שורש של עץ בינארי, ומחזירה את הגובה שלו.
5. שאלות תאורטיות על הפונקציה הקודמת. סיבוכיות זמן, כמה קריאות מחסנית מתבצעות *בו
זמנית* + להסביר למה.
6. שאלת "הצע מבנה נתונים". יש לך מסמך עם מלא מילים. צריך להציע מבנה נתונים
שיחזיק כמה פעמים כל מילה מופיעה.
7. נתון מערך של אינטרוולים. צריך להציע אלגוריתם שמחזיר את המספר המקסימלי של
אינטרוולים שיש ביניהם חיתוך, ובאיזה טווח מתקיים אותו חיתוך מקסימלי.
5.
6.
7.
8.
תשובות
הוסף תשובה
|
לצפיה בתשובות
אוגוסט 2018
4. גם התשובה לכאן מופיעה באחד מהשחזורים. במקרה שלי התבקשתי לממש *מבלי להיעזר
בפונקציות עזר*, דבר שבטעות לא הקפדתי עליו בטעות :)
5. סיבוכיות זמן לינארית.
6. יכולים להיות כל מיני סוגי פתרונות. אני הצעתי hashTable. בנוסף נשאלתי איזו
פונקציית hash הייתי מציע אם המערך היה אינסופי. בגלל שיש 25 אותיות, הצעתי
פונקציה שממפה את הייצוג שלה בבסיס 25.
7. על פניו השאלה נשמעת קשה אבל הפתרון פשוט (אני מודה שהתקשיתי אתה, ממליץ בחום
לחשוב לבד על פתרון, כי זה מסוג השאלות שקשה לחזות)
הפתרון הטכני פחות קריטי. הרעיון הוא להטיל את הנקודות קצה של כל אינטרוול על ישר
כלשהו, נקרא להם Xstart, Xend.
כעט, נעבור על הישר עליו מוטלות הנקודות. בכל פעם שנתקל ב- Xstart של אינטרוול
כלשהו מספר החיתוכים המקסימלי גדל ב- 1, וכאשר נתקל ב- Xend של אינטרוול
כלשהו, מספר החיתוכים המקסימלי יקטן ב- 1. לאחר מעבר על הישר המספר שיתקבל
יהיה מספר האינטרוולים המקסימלי.