שלום


משהו מכיר דרך (בפסדו קוד כמובן) לשלוף את הערך הכי גדול ממחסנית בזמן של o(1) ?

אפשרות שנשמור את האיבר הכי גדול בפעולת INSERT הוא אסור



קיים פתרון , אני פשוט לא יודע מה הוא.

_

אני הלוחם של היום והלויס ליין של המחר

תגדיר לשלוף ותגיד איך ממומשת המחסנית...

דבר ראשון, במחסנית אתה תמיד אמור להוציא את האיבר בראש המחסנית. להוציא את האיבר הכי גדול בה שובר את כל הרעיון של מחסנית וזה הזוי.
דבר שני, אם המחסנית ממומשת כמערך ציקלי, למשל, הוצאה מהאמצע היא בלתי אפשרית, בטח ב-(O(1. יש טריק של לשמור על שדות מאותחלים במערך ע"י 2 מערכי עזר ב-(O(1 אבל שוב, זה מימוש הזוי לחלוטין עבור מחסנית.
אם המחסנית ממומשת ברשימה אז אפשר בכל הכנסה לשמור את הערך המקסימאלי הנוכחי ולהשוות אותו לאיבר החדש המוכנס, ואם כן לשמור את האיבר שמצביע עליו. הבעיה היא שב-(O(1 מדובר בפתרון חד-פעמי כי אחרי שתוציא את האיבר הכי גדול - איך תמצא את האחד הבא?

בקיצור, שאלה הזויה...

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

אם תעשה מיון לפני ההכנסה אז זה הדרך היחידה האפשרית שאני רואה..

לא קיים פיתרון כזה בוודאות.

כי אם תניח בשלילה שקיים פיתרון אז נובע מכך שאתה יכול לבצע מיון ב-[tex]O(n)[/tex] במקרה הגרוע, בסתירה לכך שלא קיים (ויש לזה הוכחה מתמטית) מיון מבוסס השוואת הפועל ביעילות טובה יותר מ-[tex]\Theta (n\log n)[/tex]

אפשר לשנות את הפונקציות המרכזיות של מחסנית כגון push ו pop אבל חובה להשאיר את זמן הסיבכיות הרגיל שלהן כ o(1)


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

או שאולי שימוש בHUSH TABLE ... אבל השאלה שוב , איך אני שומר את השדה הכי גבוה...



שוב ...אסור לשמור במשתנה מבחוץ לגבי האיבר הכי גדול


תודה

_

אני הלוחם של היום והלויס ליין של המחר

אתה יכול להביא את השאלה המדויקת? לי עדיין לא ברור מה מותר ומה אסור ומה בדיוק צריך לעשות.

לקוחה מראיון עבודה מחברה כלשהי


מה שכן , מי שרשם אותה , כתב אותה כך :

"להוסיף למימוש רגיל של מחסנית – שיטה שמחזירה ב-O(1) את האיבר המקסימלי במחסנית.
אין לשנות את זמן הריצה של שאר השיטות (אבל אפשר ורצוי להוסיף להן דברים).
רמז: לשמור במשתנה את האיבר המקסימלי הנוכחי לא יעזור"

_

אני הלוחם של היום והלויס ליין של המחר

"להחזיר" או "לשלוף"

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

בכל מקרה שאלות כאלה בראיונות בד"כ מיועדות בישביל לבחון את היכולת של המועמד "להתחכם"...

הדרך היחידה היא כנראה לגרום למחסנית לא להיות LIFO... שזה די הורג את הקונספט של מחסנית:

קוד:

def newPush(newValue):
	if len(stack) > 0:
		previousValue = pop()
		if newValue > previousValue:
			push(previousValue); push(newValue)
		else:
			push(newValue); push(previousValue)
	else:
		push(newValue)

ציטוט:

במקור נכתב על ידי Michael Shermer Smart people are very good at rationalizing things they came to believe for non-smart reasons.

האם מדובר על סיבוכיות במקרה הממוצע? כי במקרה הגרוע זה בלתי אפשרי כמו ש-RP אמר. אם אתה מכניס כל איבר ב-(O(1 ומוציא את המקסימלי ב-(O(1 אז הצלחת לממש מיון בעל סיבוכיות (O(n במקרה הגרוע.

(אגב הגעתי לאשכול הזה בגלל השורה הנעה במה שבראש )

אז עבור כל פעולת PUSH היית מגדיר פעולת multiPOP
o(n) / n = o(1) .a
שבעצם הייתה עוברת על כל איברי המחסנית ובדוקת מי הכי גדול?

_

אני הלוחם של היום והלויס ליין של המחר

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

בס"ד

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

מימוש לדוגמא: (לא בדקתי אותו, והוא מתעלם מתחילת המחסנית, אבל אני מקווה שהרעיון מובן)

קוד PHP:

 struct stack {
int val;
struct stack *back;
int greatest;
};

void push(struct stack **st,int i)
{
struct stack *new=(struct stack *)malloc(sizeof(struct stack));
new->val=i;
new->back=*st;
if ((*st)->greatest>i) new->greatest=(*st)->greatest;
else new->greatest=i;
*st=new;
}

int pop(struct stack **st)
{
struct stack *tmp;
int i;
i=(*st)->val;
tmp=(*st)->back;
free(*st);
*st=tmp;
return i;
}

int greater(struct stack *st)
{
return st->greatest;
} 


שמת לב שלא התייחסת ל-greatest ב-pop? מה קורה אם האיבר הכי גדול כרגע יצא?

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

בס"ד

לכל איבר, יש משתנה greatest, שהוא האיבר הכי גדול עד אליו.
אם מוציאים את האיבר הכי גדול, ה-greatest של האיבר העליון יכיל את הערך הכי גדול שעכשיו במחסנית.

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