חידה מעצבנת שאחי הקטן שאל

[5127109]

אז למה חפשת מישהו כזה?

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


אם כבר, עוד שאלה. (שאלו אותי בראיון עבודה קדמון)

ישנו מערך של מספרים שלמים בסדר עולה מ1-n.
[1,2,3,4] וכו
מספר אחד חסר.
איך מגלים מה המספר החסר הכי מהר ויעיל שיש.

 

[undo]

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

O(Log n)

 

[פרוגיוזרית]

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


אם כבר, עוד שאלה. (שאלו אותי בראיון עבודה קדמון)

ישנו מערך של מספרים שלמים בסדר עולה מ1-n.
[1,2,3,4] וכו
מספר אחד חסר.
איך מגלים מה המספר החסר הכי מהר ויעיל שיש.

מחברים את כל אברי המערך = result.
במקביל סוכמים מ1 עד n. זה ה expected.
ואז עושים expected-result ומקבלים את המספר החסר.
זמן ריצה o

 

[undo]

מחברים את כל אברי המערך = result.
במקביל סוכמים מ1 עד n. זה ה expected.
ואז עושים expected-result ומקבלים את המספר החסר.
זמן ריצה o

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

 

[מירי ממודיעין עילית]

נו ומה התשובה בתכלס?
אני במתחחחחחחחחחחח

 

[B HAPPY]

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

אמנם זה
(O(n
אבל בלי תנאי ה- if
(אם זה מערך גדול אז יתכן שזמן ההשוואה הוא משמעותי)

 

[undo]

אמנם זה
(O(n
אבל בלי תנאי ה- if
(אם זה מערך גדול אז יתכן שזמן ההשוואה הוא משמעותי)

לא הבנתי. תוכלי לפרט יותר?

 

[B HAPPY]

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

 

[5127109]

מחברים את כל אברי המערך = result.
במקביל סוכמים מ1 עד n. זה ה expected.
ואז עושים expected-result ומקבלים את המספר החסר.

ואז זה המיקום שלו במדיוק - בלי צורך לעבור על אברי המערך. זה התשובה.

במתחחחחחחחחחחח

 

[פרוגיוזרית]

לא הבנתי. תוכלי לפרט יותר?

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

 

[B HAPPY]

ואז זה המיקום שלו במדיוק - בלי צורך לעבור על אברי המערך. זה התשובה.

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

 

[B HAPPY]

@פרוגיוזרית הסברנו ביחד...

 

[5127109]

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

נכון

 

[פרוגיוזרית]

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

לא נראה לי זה עובד. איך תדעי כל פעם על איזה חצי לא להסתכל?

 

[B HAPPY]

לא נראה לי זה עובד. איך תדעי כל פעם על איזה חצי לא להסתכל?

אם המספר החציוני תואם לאינדקס שלו - החסר נמצא במספרים הגדולים ממנו
ואם לא - אז בקטנים

 

[פרוגיוזרית]

אם המספר החציוני תואם לאינדקס שלו - החסר נמצא במספרים הגדולים ממנו
ואם לא - אז בקטנים

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

 

[פרוגיוזרית]

אאתגר אתכם הלאה.
נתון מערך לא ממוין בגודל n-2, נתון שהמספרים בו הם ייחודיים מ1 עד N, וחסרים בו שני מספרים (לכן גודלו n-2).
מצאו את שני האיברים החסרים בזמן ריצה של o

 

[s976]

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

יש מצב שחסרים כאן פרטים? יש כנראה הגבלה כל שהיא על האיברים, לא?
זה מספרים? מ-1 עד n ?

 

[פרוגיוזרית]

יש מצב שחסרים כאן פרטים? יש כנראה הגבלה כל שהיא על האיברים, לא?
זה מספרים? מ-1 עד n ?

ערכתי.

 

[פינחס רוזנצוויג]

בונים מערך מאופס בגודל N
עוברים על מערך המספרים הלא ממוינים
מסמנים 1 בכל אינדקס שהערך שלו קיים במערך...

זה הפתרון הכי פשוט
(זה יעלה עוד O מקוםׂ)
ׂ