הראיון מתבצע מול מראיין והתשובות נכתבות על גבי לוח עם טושים.
שאלות מתוך הראיון
יש לך עץ חיפוש בינארי ומספר שלם n. מצא את הדרך היעילה ביותר לאתר שני צמתים (nodes) שסכומם שווה ל-n.
תשובות
הוסף תשובה
|
לצפיה בתשובות
מאי 2020
ניתן לעבור על כל הזוגות האפשריים ולחפש אם מישהו שווה לn זה כמובן יהיה זמן ריצה ריבועי
אומנם אם נעבור צומת צומת, ועבור כל אחת נחפש את n - k בעץ (כך ש k זה הצומת הנוכחי) יש לנו n קודקודים שבכל אחד עושים חיפוש בינארי לכן ריצה n log n
יוני 2020
לעבור ב אין אורדר ולהכניס למער המערך יוצר ממיון וניתן לעבור עלין מהתחל ומהסוף לההגדיל ופי משפט ערך ביניים ניתן במידה וקיים ניתן למצוא אותו בזמן לינראי. אפשר לשים לב שאין צורך במערך ואפשר להתשמש באיטרטואים בלי להזדקק למערך. זסיוכיות זמן ריצה לינארית סיבוכיות מקום במערך לינארית באיטרטור גובה העץ כלומר לוגריטמית.
פניתי ישירות לחברה דרך הדרושים, יצרו איתי קשר, זומנתי לראיון ראשון מקצועי, קצת שאלו עליי ועל הרקע. באתי למשרת סטודנט.
שאלות מתוך הראיון
למצוא אלגוריתם למציאת תת סדרה מונוטונית עולה הארוכה ביותר במערך
תשובות
הוסף תשובה
|
לצפיה בתשובות
דצמבר 2020
ליצור מערך חדש שאיבריו יהיו, האיבר הכי קטן ועד הכי גדול במערך הנתון, בסדר עולה.
ואז להפעיל את האלגוריתם LCS (תכנון דינאמי) למציאת תת סדרה משותפת הארוכה ביותר, מבין המערך הנתון, והמערך החדש שיצרנו.
וקיבלנו את המבוקש
מרץ 2021
define LIS array in size n which contains 1s
max_s = 1
iterate from 1 to n -> i
iterate from 0 to i -> j
if arr[i] > arr[j]:
LSI[i] = max(LSI[i], LSI[j] + 1)
max_s = max(max_s, LSI[i])
ראיון לתפקיד 
