רשימה מעגלית

[yhaim]

רשימה מעגלית

האם יש דרך לדעת בהינתן פויינטר לרשימה מקושרת אם היא מעגלית או לא בסיבוכיות זמן של או של n וסיבוכיות מקום של או של 1. הכוונה במעגלית שהיא יכולה להצביע על האיבר השני או השלישי וכד'.

 

[DNile]

ודאי.

מדובר בשאלה מוכרת, שמראיינים רבים נוהגים לתת אותה כחידות. לשאלה של "האם יש דרך" עניתי. אם אתה רוצה גם לדעת את הדרך, תצטרך לבקש, אחרת אני מניח שאתה רוצה לפתור לבד, ופשוט שואל אם זה אפשרי.

 

[נועה לביא]

לי דווקא נראה שהמצב הוא אחר

ושלמישהו היה ראיון עם מישהו ששמו מתחיל בס'...

 

[DNile]

שיהיה לו לבריאות..

מה שברור זה שאותו אחד ששמו מתחיל בס' לא המציא את החידה הזאת, וגם לא היחידי שנותן אותה בראיונות.

 

[mooznach]

ואוו. חוסר יעילות אליטה...

 

[shamon51]

הדגל שלי הוא ?

יהגדיר בכל איבר דגל עבור על הרשימה והדלק את הדגל בכל צומת שאתה עובר אם הגעת לסוף = אין מעגל אם הגעת לצומת עם דגל מורם = יש

בעיה: זה טוב לבדיקה הראשונה

ולכן ובנוסף ... צריך סבוב בהתחלה להורדת כל הדגלים (קצת מסובך) אז מגדירים שדה יותר גדול (Byte) כמו 0-255 וזה מספיק ל 255 סיבובים של בדיקות שמעון

 

[משועמם14]

תגיד לי, אתה מסטול? ../images/Emo3.gif

למה לא לשמור פשוט את המצביע של האיבר ממנו אתה מתחיל, לעבור על כל הרשימה (קדימה או אחורה) ולעצור אם מגיעים ל- NULL או חזרה למצביע לאיבר שממנו התחלת...

 

[אלדד28]

פשוט מאוד -

כי המעגל לא חייב לחזור לתחילת הרשימה. שני הפתרונות האלו אינם הפתרונות הנכונים.

 

[נועה לביא]

הראשון נכון

או בכל אופן, הרעיון של לסמן יעבוד, רק שזו לא הפואנטה... הפואנטה היא מן הסתם להשתמש בכמות קבועה של זכרון ולא בO...

 

[roterl]

הראשון יעבוד אבל מסובך

גם מבחינת זמן ריצה (בפועל) וגם מבחינת זיכרון. משתמשים בשתי מצביעים- את אחד מהמצביעים מקדמים לבא, ואת השני מקדמים שתיים (כלומר לבא של הבא). אם שני המצביעים נפגשים אזי הרשימה מעגלית.

 

[yfatt]

פתרון נוסף

לעבור עם 2 מצביעים, הראשון עובר אחד אחד והשני שניים שניים, אם הם יפגשו - הרשימה מעגלית, אחרת השני יעצר ב-null.

 

[אלדד28]

נתתם את אותו הפתרון (הנכון) ../images/Emo13.gif

 

[כלמנסע]

זה מזכיר לי את...

... אלגוריתם "רוׁ" של פולארד (כהתקפה נגד RSA). סתם, להראות שאני יודע משהו. [ כלמנסע מרגיש מאוד בוגר ]

 

[shamon51]

תודה שענית בשבילי כי חשבתי לרגע ש

ישבו שאני מסטוך

 

[אלדד28]

השאלה הזו יותר עתיקה מהזנות

 

[ChipsMan]

יש לי שאלה יותר חביבה ../images/Emo13.gif

בהנתן רשימה מקושרת חד כיוונית וכמות זיכרון קבועה, צריך למצוא את האלגוריתם היעיל ביותר להדפסת הרשימה בסדר הפוך (מהסוף להתחלה).

 

[אלדד28]

תשובה

הופכים את הרשימה (בעזרת שלושה מצביעים) מדפיסים הופכים את הרשימה בחזרה (בעזרת שלושה מצביעים) - רק אם צריך.

 

[ChipsMan]

נכון ../images/Emo13.gif

ועכשיו לשאלה טיפה יותר קשה - אותו דבר רק שהפעם אסור לשנות את הרשימה (גם לא את המצביעים).

 

[erezsh]

תשובה

בהנחה והמהירות לא חשובה. 1. אתה סורק את הרשימה מההתחלה ומוצא את סוף הרשימה ומסמן את כתובת האיבר האחרון (במצביע) 2. אתה מדפיס את האיבר 3. אתה סורק את כל הרשימה עד שמגיע לאיבר שמצביע לאיבר שסימנת, ומסמן אותו במקום 4. אתה חוזר על שלבים 2 עד 4 לפי הסדר, כל עוד האיבר שסימנת אינו האיבר הראשון. 5. אתה מדפיס את האיבר הראשון

 

[נועה לביא]

מן הסתם, הסיבוכיות כן חשובה

אחרת אין פואנטה לחידה, נכון? לגבי פתרון - מצטערת אבל המוח שלי שפוך כמו ביצה עין (?), אולי מחר...