ביקשו שאספר על פרוייקטים שעשיתי במהלך התואר ולאחר מכן שאלו שאלות מקצועיות:
1. נתון מערך A בגודל n המכיל מספרים שלמים. נתון מערך B בגודל n המכיל הסתברויות (מספרים בין 0 ל1) - סך כל הערכים במערך B הוא 1.
כל תא במערך B מייצג ת ההסתברות שיופיע המספר שבמערך A באינדקס זהה
דוגמה:
A מכיל 5 1 3 8
B מכיל 0.1 0.2 0.2 0.5
אז הההסתברות שהמספר 8 יופיע היא 0.5, עבור המספרים 3 ו1 ההסתברות שיופיעו היא 0.2 וכך הלאה.
בנוסף נתונה פונקציה rand() שמגרילה מספר בין 0 ל1 רנדומלית.
צריך לכתוב פונקציה שבכל קריאה אליה תדפיס מספר כלשהו כך שאם קוראים לפונקציה הזו הרבה מאוד פעמים נראה שבאמת כל מספר מופיע בהסתברות הנתונה במערך B שלו.
2. נתונות 2 רשימות יש לבדוק האם קיים node משותף ברשימות. סיבוכיות o(n)
3. נתונים 2 עצים בינאריים, יש לבדוק האם יש node משותף ביניהם. סיבוכיות o(n)
תשובות
הוסף תשובה
|
לצפיה בתשובות
ינואר 2017
1. מגדירים מערך נוסף בגודל n שבתא הראשון שלו תהיה הסתברות זהה לתא הראשון של B, בתא השני שלו יהיה סכום 2 התאים הראשונים של B, בתא השלישי סכום 3 ההסתברויות משלושת התאים הראשונים של B וכך הלאה. בתא האחרון של המערך החדש יהיה הערך 1 (סכום כל ההסתברויות הוא 1)
לצורך העניין בדוגמא שניתנה בשאלה המערך החדש יכיל: 1 0.9 0.7 0.5
ואז באמצעות שימוש בפונקציית rand הנתונה שמגרילה מספר בין 0 ל1 - בהתאם למספר שהיא מגרילה בודקים באיזה תחום המספר שהוגרל - אם הוא לצורך העניין בדוגמה הזו הוגרל מספר 0.2 אז נלך לתחום של התא הראשון כי זה קטן מ0.5
אם הוגרל 0.6 אז נלך לתא השני שמהווה את התחום בין 0.5 ל0.7
ונדפיס בהתאם מספר מA לפי האינדקס של המערך החדש שיצא בrand
ינואר 2017
2. עוברים על הרשימות ובודקים האם הכתובת של האיבר האחרון זהה
3. פתרון נאיבי: עוברים על העץ הראשון t1, ועבור כל עלה עוברים על העץ t2 ובודקים האם כתובת אחד העלים בt2 זהה לכתובת העלה הנוכחי בt1.
פתרון יותר טוב: במידה וניתן לשנות את ערכי התאים שבעץ - נאתחל את כל האיברים בשני העצים ל0. נעבור על עץ t1 ובכל תא נשים את הערך 1. נעבור על העץ t2 ונבדוק אם קיים ערך 1 - אם כן זה אומר שהעצים מחוברים
פתרון נוסף: אם אסור לשנות את הערכים שבעץ - נוסיף איבר נוסף לעץ t1 ונחבר אותו לכל עלי העץ t1. כעת נעבור על העץ t2 ונבדוק האם בשלב מסויים הגענו לאיבר החדש אותו הוספנו לt1.
הראיון מורכב משני חלקים ואורכו הכול בין שעה לשעה וחצי.
בחלק הראשון שני המראיינים מדברים על המשרה באופן כללי, ואחר כך הם מבקשים מהמרואיין לספר על עצמו, נסיון תעסוקתי וכו'.
בחלק השני נשאלת שאלה טכנית, ועל המרואיין לתאר את הפתרון בע"פ ובכתב על גבי הלוח.
שאלות מתוך הראיון
יש לכתוב תכנית ב-C שמקבלת מערך ממויין A של מספרים שונים זה מזה בגודל n, מספר k וערך diff, ומחזירה 1 אם קיים במערך מספר m כך שמתקיים שההפרש בין k לבין m הוא בדיוק diff. התכנית צריכה לעבוד בסיבוכיות זמן logn
תשובות
הוסף תשובה
|
לצפיה בתשובות
מאי 2016
התכנית צריכה להראות כמו חיפוש בינארי עם שינוי קטן, שה-x שמחפשים הוא ההפרש בין diff לבין k.
אוקטובר 2017
אם קיים, m הוא הסכום של k ו diff. בגלל ש m צריך להיות במערך נעשה חיפוש בינארי על הסכום
אינטל הוא תאגיד בינלאומי אמריקאי, אשר ידוע בעיקר כמתכנן ויצרן של מיקרו־מעבדים (החל משנת 1971) ומתמחה במעגלים משולבים. כמו כן, אינטל מייצרת כרטיסי רשת, מערכות שבבים ללוחות אם, והתקנים אחרים.
ראיון לתפקיד 
