יש מערך עם n+1 איברים בטווח 1 עד n ויש איבר שחוזר על עצמו, איך מוצאים אותו בסיבוכויות שונות?
תשובות
הוסף תשובה
|
לצפיה בתשובות
מרץ 2019
בסיבוכיות של n- בודק מה הסכום מ1 עד n, על ידי הכפלת חצי N בסכום של 1+N. סוכם את האיברים, ומפחית מהסכום שקיבלת את הסכום מ1 עד N.
אפשר גם באותה סיבוכיות לעבור על המערך עצמו ולסמן מספרים שקיבלת ולעצור כשהגעת למספר שמופיע פעמיים.
אני חושב שכל פתרון אחר יהיה מבוסס מיון ואז זה כבר מגיע לnlogn.
נתון עץ שכל צומת ממוספר והמיספור הוא לפי רמות. כלומר שלב ראשון (שורש) 1, שלב שני (הבנים של השורש) 2 משמאל ו-3 מימין וכן הלאה.
בהינתן מספר צומת עליך להחזיר את הצעדים הרלוונטים ע"מ להגיע ישירות אל צומת זה מהשורש
תשובות
הוסף תשובה
|
לצפיה בתשובות
נובמבר 2017
כל עוד המספר שקיבלת שונה מאפס:
-בצע shift right 1 למספר
-בצע and 1
אם המספר שקיבלת אי זוגי - ימינה
אם המספר שקיבלת זוגי - שמאלה
ינואר 2018
log x
כאשר הלוג בבסיס 2 והX זה מספר הצומת, ניקח את הערך "רצפה"
יולי 2019
נתבונן בעץ הבא:
1
3 2
7 6 5 4
נראה שכאשר נלך שמאלה המספר מוכפל ב2 וכאשר נלך ימינה המספר מוכפל ב2 ועוד 1 וכן:
נוכל לעבור מהמספר המבוקש כלפי מעלה בסיבוכיות logn ולשחזר את כל המסלול כולל את הפניות(ימינה או שמאלה)
נניח והמספר יהיה 6:
נחלק את 6 בשתים המספר או 3 בגלל ש6 זוגי נדע שהמעבר מ 3 ל6 הוא שמאלה.
נחלק את 3 בשתים והמספר הוא 1 בגלל ש3 אי זוגי נדע שהמעבר מ1 ל3 הוא ימינה.
אלביט מערכות בע"מ היא חברה ישראלית העוסקת בפיתוח ובייצור של מערכות אלקטרוניות ואמצעי לחימה מתקדמים. אלביט מערכות מפתחת, משווקת ומבצעת אינטגרציה של מערכות אלקטרוניות ואלקטרו-אופטיות ביטחוניות מתקדמות ללקוחות בכל רחבי העולם. החברה מתמקדת בפיתוח מערכות שליטה ובקרה, ומערכות מודיעין לשוק הצבאי, בביצוע השבחות של כלי טיס, כלי שיט ורכבים ובפיתוח ומסירה של מערכות כלי טיס בלתי מאוישים.
ראיון לתפקיד 
