רוטר - חידה נחמדה לסופ''ש

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"חידה נחמדה לסופ''ש"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #15430	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 15430

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

19:13 06.08.09

חידה נחמדה לסופ''ש

משהו נחמד ששאלו אותי.
אתם צריכים לייצג מחסנית שמכילה את הפעולות pop,push,get_min,get_max
וכולן צריכות להתבצע ב O(1)
אתם גמישים לגמרי בייצוג המחסנית
ומבחינת מקום אתם מוגבלים ל O(N)
תסבירו איך אתם פותרים את הבעייה , וינר לפותר

בהצלחה

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
בהצלחה חבר'ה.. :)	Nesher	06.08.09 19:56	1
הצעת פיתרון שלי	Nokia	06.08.09 20:29	2
לא התעמקתי בפתרון, אבל יש אחד פשוט בהרבה	ldan192	07.08.09 00:14	3
זה אמור לעבוד , יפה מאד !	Net_Boy	07.08.09 12:50	4

Nesher

חבר מתאריך 2.7.02
2 הודעות, 24 פידבק

19:56 06.08.09

1. בהצלחה חבר'ה.. :)
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Nokia
חבר מתאריך 1.7.02
538 הודעות

20:29 06.08.09

2. הצעת פיתרון שלי
בתגובה להודעה מספר 0

נניח לממש סוג של רשימה מקושרת שלכל איבר בה 4 שדות: הערך, מצביע לאיבר המקסימלי ברשימה אחריו (כולל אותו), מצביע לאיבר המינימלי ברשימה אחריו (כולל אותו),מצביע לאיבר הבא.
כמובן צריך לשמור את המצביע לראש הרשימה..
המימוש של הפעולות:
push - נניח שדוחפים מספר. אז ניצור ממנו node שהאיבר הבא אחריו יהיה ראש הרשימה הנוכחי, נעדכן את ראש הרשימה הנוכחי להיות הnode שיצרנו.
שדה המקסימום שלנו יהיה מצביע לעצמינו אם האיבר הנוכחי גדול מהערך של האיבר שראש הרשימה הישן הצביע עליו בתור המקסימלי , או המקסימום של ראש הרשימה הישן אחרת. באופן דומה קובעים את הערך של האיבר המינימלי בnode
pop - מוחקים את הNODE ראש הרשימה (עדכוני מצביעים)
getMax - השדה של המקסימום באיבר שהוא ראש הרשימה (בגלל הבנייה הוא גם יהיה המקסימום של הרשימה)
getMin - השדה של המינימום באיבר שהוא ראש הרשימה.
זה מה שעלה לי בראש...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

00:14 07.08.09

3. לא התעמקתי בפתרון, אבל יש אחד פשוט בהרבה
בתגובה להודעה מספר 2

והוא מסתמך על סוג של double duffering.

אני לא אגלה עדיין אבל זה היה רמז

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

12:50 07.08.09

4. זה אמור לעבוד , יפה מאד !
בתגובה להודעה מספר 2

ערכתי לאחרונה בתאריך 07.08.09 בשעה 12:57 בברכה, Net_Boy

יש עוד שיטה לעשות את מה שהתכוונת (אני חושב שזה מה שעידן התכוון אליו)
אבל השיטה הזאת מצוינת ועונה על כל תנאי החידה , וינר בדרך אליך

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד