נתון תור (Queue) יש להפוך את התור בעזרת פרימיטיבס ותורים נוספים בלבד
תשובות
הוסף תשובה
|
לצפיה בתשובות
ספטמבר 2017
צריך לממש מחסנית באמצעות 2 תורים (יש מימוש באינטרנט, קל למצוא), ואח"כ להוציא איבר איבר מהתור המקורי לתוך המחסנית שבנינו, ובסוף לרוקן את המחסנית איבר איבר לתוך התור.
1. לממש מחסנית עם סמאפור כדי להגן מפני כתיבה משותפת, וכאשר המחסנית ריקה רוצים שמי שנכנס לא ייצא בידיים ריקות. שהמחסנית אף פעם לא תחזיר empty
2. נתונה 2 רשימות מקושרות, לא בגודל שווה, כאשר בנקודה מסוימת 2 הרשימות מתלכדות לרשימה אחת..לממש איך מוצאים את נקודת החיבור שממנה מתלכד לאחד..
תשובות
הוסף תשובה
|
לצפיה בתשובות
ספטמבר 2017
לגבי השאלה השניה: תחילה מוצאים את האורך של כל רשימה מקושרת. נסמן את האורכים ב l1, l2. אח"כ מראש כל רשימה מתקדמים abs(l2-l1) צעדים (כשכמובן תוך כדי התקדמות בודקים אם הצמתים זהים, אם כן - זוהי הנקודה). במידה ועד כה לא נמצאו צמתים זהים, ממשיכים לבדוק צומת צומת כשמתקדמים במקביל אחד אחד על כל רשימה עד שמגיעים ל Null (ואז אין נקודת התלכדות) או שמגיעים לצומת זהה.
דצמבר 2018
הפתרון לדעתי לא נכון.
יכול להיות שרשימה א' מתלכדת עם רשימה ב' בקודקוד הראשון של רשימה א', אבל ברשימה ב' יש איברים לפני.
למשל:
א) 1->2->3
ב)4->5->1->2->3
לכן אם תתקדם צעד צעד אתה תאבד את קודקוד 1, על ההתחלה ובחיים לא תמצא שוויון.
לדעתי רצוי לפתור את זה עם שתי hash_table, אחד לכל רשימה. ואז אתה עובר צעד צעד, ושואל האם קודקוד של רשימה א' נמצא בhash_table של רשימה ב', אם כן יש התלכדות אם לא, להכניס אותו לhash_table של רשימה א', בדומה אותו דבר עבור רשימה ב', לבדוק אם הקודקוד שלה נמצא בhash_table של רשימה א', ואם לא אז להכניס לHash_table של רשימה ב'.
בהנחה והhash_table ממומש טוב אז הכנסה וחיפוש רצות ב(o(1 ולכן זמן הריצה יהיה לינארי.
אם אסור להשתמש בhash_table אז יש פתרון ריבועי:
על כל קודקוד של רשימה א', אתה מחפש אותו ברשימה ב', הראשון שתמצא יהיה ההתלכדות.
יולי 2019
hash_table זה פתרון נכון אבל אין צורך ב - 2.
תעבור על רשימה אחת ותכניס את כל האיברים שלה ל hash.
תעבור על הרשימה השניה ותחפש איזה איבר כבר מופיע ב hash, זה האיבר המחבר.
ספטמבר 2020
הפתרון של ה - hash_table נכון אבל לא יעיל כי זה תופס מלא מקום בזכרון!!!
והפתרון הראשון נשמע הכי אידיאלי ופתרתי את הבעיה הזו פעם -
וצריך לקדם רק את ראש הרשימה הארוכה יותר ב - abs(l1 - l2) ואז 2 הרשימות יהיו באותו אורך ואז לעבור עליהם במקביל וזה מכסה גם את כל המקרי קצה - ובמקום שהם מצביעות לאותו איבר זה נקודת החיבור!!
ראיון לתפקיד 
