נתונה רשימה של מספרים. יש להחזיר האם הסריקה הזו יכולה להתקבל מסריקת in order של עץ חיפוש בינארי.
לכתוב אלגוריתם שמגריל פרמוטציה של מספרים כלשהם, כאשר נתונה לנו פעולה שמגרילה מספר ספציפי.
הסבר על המחלקה והצוות אליו מתראיינים, שאלות על החברה, על התפקיד ועל סיבת העזיבה ולאחר מכן שאלה מקצועית
שאלות מתוך הראיון
נתון עולם דו מימדי בגודל NxN שבו יש x אריות, y כבשים, z צמחים. אריה וכבש יכולים לזוז צעד ביום.
אריה אוכל כבש ובמידה ולא אכל d1 ימים הוא מת
כבש אוכל צמח ובמידה ולא אכל d2 ימים הוא מת
1. תתאר מבנה נתונים שיחזיק את המידע
2. מה הבעיות שיכולות להיות במבנה הנתונים שתיארת?
3. נתונה פונקציית rand. כיצד תפזר את החיות על פני העולם באופן אחיד? לאחר מכן תרשום אלגוריתם שיבצע את זה בO(N)
שאלה נוספת
4. נתונה פונקציית rand0-31, תבנה פונקציית rand0-3
5. תבנה פונקציית rand0-4 ככה שההתפלגות תהיה אחידה
תשובות
הוסף תשובה
|
לצפיה בתשובות
ינואר 2021
פתרון חלקי
1. ניתן לייצג בצורת מטריצה NxN של מצביעים לאלמנט. במידה והאלמנט הוא חיה, נשמור בתוכו איזו חיה נמצאת וכמה ימים היא לא אכלה.
2. במידה ו-N מאוד גדול ו-x,y,z קטנים יש בזבוז רב של זכרון
אפשרות נוספת
1. לשמור רשימות עם מיקומים לפי אלמנט. כלומר 3 רשימות: צמחים, כבשים ואריות.
3.
אפשרות 1:
נפזר את החיות עם פונקציה rand שפועלת על מיקום x,y. במידה ויצא מיקום שבר קיים, נבצע שוב פונקציית rand.
אפשרות 2:
נשמור מערך עם המקומות הפנויים ונבצע פונקציית rand על אינדקס המערך. ברגע ונבחר מקום, נוציא אותו מהמערך ונגריל מיקום עד גודל המערך החדש.
4. פשוט לקחת את 2 הביטים הראשונים של פונקציית rand 0-31
5. להבין למה x%5 לא יתן תוצאה אחידה (יש יותר סיכוי ל0 להיבחר מאשר ל4 למשל). לאחר שהבנו, במידה ונתקלים במספר שגורם להתפלגות לא להיות אחידה, מגרילים פעם נוספת עם אותה פונקציה.
מאי 2021
לגבי 3 האפשרות השניה, למחוק ממערך עולה גם O(N) ולכן במקרה הגרוע נשלם N בריבוע
אפשר פשוט לספור את כמות האחדים וליצור מערך חדש.
אם צריך ע"י הזזות אז אפשר לרוץ עם סמן משמאל עד שמוצאים "1" אח"כ לרוץ עם סמן מימן עד שמוצאים "0" ולהחליף בינהם. לחזור ככה בלופ עד שסמן שמאל שווה או גדול מסמן ימין. בהצלחה.
ראיון לתפקיד 
