ביקשו שאספר על פרוייקטים שעשיתי במהלך התואר ולאחר מכן שאלו שאלות מקצועיות:
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.
אינטל הוא תאגיד בינלאומי אמריקאי, אשר ידוע בעיקר כמתכנן ויצרן של מיקרו־מעבדים (החל משנת 1971) ומתמחה במעגלים משולבים. כמו כן, אינטל מייצרת כרטיסי רשת, מערכות שבבים ללוחות אם, והתקנים אחרים.
ראיון לתפקיד 
