חידה האם אתם מספיק חכמים כדי לעבוד בגוגל?

[מסקרה]

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

 

[RGS]

שאלה מראיון עבודה בגוגל
You're standing in front of a 100 story building with two identical bowling balls. You've been tasked with testing the bowling balls' resilience. The building has a stairwell with a window at each story from which you can (conveniently) drop bowling balls.
To test the bowling balls you need to find the first floor at which they break. It might be the 100th floor or it might be the 50th floor, but if it breaks somewhere in the middle you know it will break at every floor above.
Devise an algorithm which guarantees you'll find the first floor at which one of your bowling balls will break. You're graded on your algorithm's worst-case running time.

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

 

[RGS]

ועוד אחת קצת יותר מתמטית
Monty Hall asks you to choose one of three doors. One of the doors hides a prize and the other two doors have no prize. You state out loud which door you pick, but you don’t open it right away.
At this point, Monty will always open one of the other two doors that do not have a prize behind it.
At this moment, there are two closed doors, one of which you picked.
The prize is behind one of the closed doors, but you don’t know which one.
Monty asks you, “Do you want to switch doors?”
The question is what's better to do - what door to open or it doesn't matter.

שווה להחליף
שלב ראשון: יש לך שלוש דלתות, אחת מהן מסתירה פרס ושתי האחרות ריקות. בהתחלה, הסיכוי שלך לבחור את הדלת עם הפרס הוא 1 מתוך 3, כלומר 1/3.

שלב שני: נניח שבחרת דלת מסוימת (נניח דלת 1). הסיכוי שהפרס מאחורי דלת 1 הוא 1/3, והסיכוי שהפרס מאחורי אחת משתי הדלתות האחרות (דלתות 2 ו-3) הוא 2/3.

שלב שלישי: מונטי פותח אחת משתי הדלתות האחרות (נניח דלת 2) ומראה שאין מאחוריה פרס. כעת יש לך שתי דלתות סגורות: דלת 1 (שבחרת בתחילה) ודלת 3.

שלב רביעי: מונטי שואל אותך אם תרצה להחליף את הבחירה שלך לדלת הנותרת (דלת 3).

הנקודה הקריטית היא שעדיין יש סיכוי של 2/3 שהפרס נמצא מאחורי דלתות 2 ו-3 (שאתה לא בחרת בהתחלה), אך כעת אנו יודעים שדלת 2 ריקה, ולכן כל הסיכוי של 2/3 עובר לדלת 3.

לעומת זאת, הסיכוי שהפרס מאחורי דלת 1, שבחרת בהתחלה, נשאר 1/3.

מכאן נובע שהסיכוי לזכות בפרס אם תחליף את הבחירה שלך הוא 2/3, בעוד שהסיכוי לזכות בפרס אם לא תחליף את הבחירה שלך הוא 1/3.

 

[shimשימי]

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

למה 15?
אם בהתחלה 14 אז זה יוצא 14 זריקות

 

[RGS]

למה 15?
אם בהתחלה 14 אז זה יוצא 14 זריקות

צודק.
טעות...

 

[מתן מאור]

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

זה מונטי הול, וקולמסים רבים נשתברו עליה:

חידה - הבעיה של מונטי הול

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

www.prog.co.il

 

[אליהו פ]

למה 15?
אם בהתחלה 14 אז זה יוצא 14 זריקות

11 זה הכי מדוייק

 

[shimשימי]

11 זה הכי מדוייק

תסביר!

 

[צלמת+]

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

1. "בוב תכתוב לי את מספר הטלפון שלך"...-
אני יתקשר למספר טלפון שלו דרך המספר שלי...
2. "בוב יש לך את המספר שלי" -
זה מה שביקשו בעיקרון- לוודא...
3. לכתוב לבוב שלושה מספרי טלפון ולכתוב בראשם: "תזהה את המספר"
שניי מספרים של מכרים\משפחה של בוב שג'ון לא מכיר אותם ולא מכיר את המספר שלהם
ברגע שבוב יקבל את שלושת המספרים הוא יזהה את שתי המספרים האחרים שבטוח כתובים לו...
ואז ידע שהשלישי הוא המספר שלי... אבל זה סיכון כי זה רק 3 מספרים...

 

[israel m]

שאלה מראיון עבודה בגוגל
You're standing in front of a 100 story building with two identical bowling balls. You've been tasked with testing the bowling balls' resilience. The building has a stairwell with a window at each story from which you can (conveniently) drop bowling balls.
To test the bowling balls you need to find the first floor at which they break. It might be the 100th floor or it might be the 50th floor, but if it breaks somewhere in the middle you know it will break at every floor above.
Devise an algorithm which guarantees you'll find the first floor at which one of your bowling balls will break. You're graded on your algorithm's worst-case running time.
אתם עומדים בבנין בן 100 קומות וצריכים לבחון את העמידות של שני כדורי באולינג זהים הדרך לבחון את זה זה לזרוקאת הכדורי/ם מהחלון בחדר המדרגות ולראות מאיזה קומה הוא נשבר יכול להיות שהוא ישבר רק מזריקה מהקומה ה100 ויכול להיות שמ50 אבל אם הוא לא שרד נפילה מ50 קומות הוא לא ישרוד גם נפילה של 51 52 וכן הלאה... הצע פתרון שמבטיח שתמצא את הקומה הראשונה שממנה הכדורים לא ישרדו

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

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

1. למה בסדר יורד? אם הכדור אינו נשבר בקומה 14 מה העניין לבדוק בקומה 13? ואם נשבר מה יועיל לבדוק ב13 אולי נשבר גם ב12?

2. ואם הכדורים חסונים ונשברים רק בקומה 99? איך תצליחו ע"י 14 או 11 בדיקות?

התשובה שלי היא: הטלה של כדור מקומה 2. 4. 6. 8. וכן הלאה... מתי שישבר הכדור הראשון נעשה הטלה מקומה מתחת לוודא את הקומה המדויקת...

 

[RGS]

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

1. למה בסדר יורד? אם הכדור אינו נשבר בקומה 14 מה העניין לבדוק בקומה 13? ואם נשבר מה יועיל לבדוק ב13 אולי נשבר גם ב12?

2. ואם הכדורים חסונים ונשברים רק בקומה 99? איך תצליחו ע"י 14 או 11 בדיקות?

התשובה שלי היא: הטלה של כדור מקומה 2. 4. 6. 8. וכן הלאה... מתי שישבר הכדור הראשון נעשה הטלה מקומה מתחת לוודא את הקומה המדויקת...

סדר יורד הכוונה לכמות הכדורים שממנה זורקים את הכדור.
אני מתחילה מהקומה הכי למעלה, וזורקת ממנה את הכדור ל14 קומות מתחת. במקרה שנשבר הכדור אני זורקת את הכדור השני את 13 הקומות שנשארו אחד אחד, עד שאני מוצאת את הקומה שבה זה נשבר. בסה"כ 14 זריקות.
אם לא נשבר אחרי 14 קומות אני זורקת 13 קומות מתחת, אם זה נשבר אני זורקת על אותו קונספט שכתבתי למעלה.
בסה"כ 2 זריקות- זריקה ל14 קומות ועוד זריקה ל13 קומות חוץ מזה נשאר לי עוד 12 קומות שלא בדקתי ובמקרה שזה נשבר שם יש לי 12+2=14.
ככה כל פעם שזה עדיין לא נשבר נוסף לי עוד זריקה אחת ופחות זריקה במקרה שהכדור הראשון אכן נשבר.
מקווה שיותר ברור.

 

[israel m]

עדיין קצת לא ברור. אבל הבנתי עכשיו את התשובה
הכוונה היא: 14 זריקות
1. מקומה 14
2. מקומה 27 (14+13)
3. מקומה 39 (27+12)
וכן הלאה... מדלגים בסדר יורד
כשבפעם שנשבר אטיל מההטלה האחרונה לזו. נניח שנשבר בהטלה השלישית מקומה 39 נותרו לי עוד 11 זריקות מ28 עד 38...
כך שבסוף ההטלה האחרונה תהיה שמינית עם רווח של 6 הטלות אחורה...
ולפי זה מקסימום ההטלות הוא 14.

 

[israel m]

חידה מצורפת

 

[pe1234]

בהלוך זה אותו דבר אבל בחזור יותר זמן כי זה נגד הרוח