יש לכם 100 מטבעות זהב וחמישה פריטים הממוספרים מ 1 עד 5 .
כל אחד בתורו מגיע עם הצעה אך לחלק את המטבעות של זהב בינהם. במידה ומתקבל רוב אז המטבעות זהב מתחלקות במידה ואין רוב וההצעה נפסלת והפריט נפסל ולא משתתף יותר בהחלטה.
השאלה היא אך בסוף תהיה החלוקה של מטבעות הזהב?
תשובות
הוסף תשובה
|
לצפיה בתשובות
ינואר 2024
הבעיה שהצגת היא וריאציה של "בעיית השודדים הדמוקרטיים", בה חמישה שודדים צריכים לחלק ביניהם אוצר של 100 מטבעות זהב. כל שודד מציע חלוקה, והיא נדחית אם רוב השודדים (שלושה או יותר) לא מסכימים לה. אם הצעה נדחית, השודד שהציע אותה מודח מהמשחק ולא ישתתף בחלוקת האוצר.
הפתרון לבעיה זו מתבסס על ההבנה שכל שודד רוצה למקסם את הרווח שלו, תוך כדי שמירה על מינימום הקולות הנדרשים לאישור ההצעה. נניח שהשודדים פועלים בסדר האלפביתי (a, b, c, d, e), כאשר a מציע ראשון.
אם נותר שודד אחד (e), הוא יקח את כל הזהב.
אם נותרו שני שודדים (d, e), d יקח את כל הזהב, כי e לא יכול להצביע נגדו.
אם נותרו שלושה שודדים (c, d, e), c צריך רק את הצבעתו של אחד מהם כדי לאשר את החלוקה. לכן, הוא יכול להציע 99 מטבעות לעצמו ומטבע אחד לאחד מהשניים (לדוגמא, ל-d), והם יסכימו כדי לקבל משהו ולא כלום.
אם נותרו ארבעה שודדים (b, c, d, e), b יודע שאם הוא יודח, c יקח כמעט את כל האוצר. לכן, הוא יציע מטבע אחד ל-d ומטבע אחד ל-e (או ל-d), שיתמכו בו כדי לא להישאר בלי כלום.
אם כולם נותרים (a, b, c, d, e), a יודע שאם הוא יודח, b יקח הכל כמעט. לכן, הוא יציע מטבע אחד ל-c ומטבע אחד ל-e, שיתמכו בו כדי לא להישאר בלי כלום.
לסיכום, החלוקה הצפויה להתקבל בסוף היא ש-a מקבל 98 מטבעות, c מקבל מטבע אחד, ו-e מקבל מטבע אחד.
יש בשורה 100 נורות מכובות, יש 100 צפרדעים. הצפרדע הראשונה קופצת על כל נורה, הצפרדע השנייה על כל נורה שנייה, הצפרדע ה3 על כל נורה שלישית וכן הלאה, איזה מנורות ישארו דלוקות בסוף?
תשובות
הוסף תשובה
|
לצפיה בתשובות
דצמבר 2023
אם מספר המחלקים של מספר הוא זוגי, הנורה תהיה כבויה בסוף ואחרת דולקת, לכן הנורה 1 ונורות שהם משהו בחזקת 2 (כמו 4, 16...) ישארו דלוקות כי 1, המספר עצמו והשורש של המספר הם מחלקים, כל המחלקים אחרים יגיעו כזוגות של מספרים שונים, לכן סה"כ כמות המחלקים תהייה אי זוגית (למשל 16: מחלקים: (1,16) *(4,4)* (2,8) כלומר 5 מחלקים שונים)
)
שני ראיונות טכניים , שניהם עם שאלות דומות. בעיקר שאלות שמערבות רכיבים לוגיים שבעזרתם צריך לבנות רכיבים לוגיים מורכבים יותר.
שאלות מתוך הראיון
נתונים ארבעה רגיסטרים והפעולות הבאות:
inc r1 מוסיף אחד לרגיסטר
dec r1 מוריד אחד מהרגיסטר
rest r1 מאפס רגיסטר
jmpz r1, LABEL קופץ לתוית אם הרגיסטר מאופס
כתוב תוכנית בעזרת הפקודות האלו בלבד שמכפילה את הערכים שנמצאים בr1 ובr2 (רגיסטרים ספציפיים) ושמה את התוצאה ברגיסטר r3.
ישנם 5 כובעים :3 כובעים לבנים ו-2 כובעים שחורים. שלושה אנשים נעמדים בתור כאשר כל אחד רואה רק את מי שלפניו: האחרון מבניהם רואה את השניים שלפניו, האמצעי רואה רק את הראשון והראשון לא רואה אף אחד. כל השלושה עוצמים עיניים ועל ראשיהם שמים 3 כובעים. שואלים את האחרון האם הוא יודע מה הצבע של הכובע שעל ראשו כך שהשניים שלפניו שומעים. אחר כך שואלים את האמצעי האם הוא יודע מה הצבע שעל ראשו כך שהראשון שומע. בסוף שואלים את הראשון האם הוא יודע מה צבע הכובע שעל ראשו?
האם הראשון יכול תמיד לדעת מה הצבע שעל ראשו?
תשובות
הוסף תשובה
|
לצפיה בתשובות
דצמבר 2023
כן
אם האחרון אומר שכן - אז הוא רואה 2 שחורים (והראשון ידע שיש לו שחור)
אם האחרון אומר שלא - אז או שהוא רואה 2 לבנים או שהוא רואה אחד לבן אחד שחור.
אם האמצעי רואה לבן הוא יגיד שאינו יודע
אם האמצעי רואה שחור הוא יגיד שכן יודע
ינואר 2024
https://i.imgur.com/89YvT6D.png
פתרון מוסבר עם טבלת אמת ועץ החלטות
ריאיון ראשון בחברה, מספר שאלות בחומרה. השאלה הנל היתה השאלה האחרונה, מכשילה יחסית
שאלות מתוך הראיון
4. 100 גמדים עומדים בטור, כך שהראשון רואה את כל הבאים שאחריו וכן הלאה.(לא רואים את מי שנמצא מאחוריך) לכל גמד יש כובע- או שחור או לבן. הגמדים לא יודעים איזה צבע יש להם.
בכל פעם שואלים גמד באיזה צבע הכובע שלו- במידה והוא טועה הורגים אותו, אם הוא צודק נשאר בחיים.
הציעו אלגוריתם שיציל מס מקסימלי של גמדים, כאשר אך ורק לגמד הראשון בטור (שרואה את כל שאר ה99 גמדים) מותר להגיד פעם אחת או את המילה שחור או לבן בלבד.
תשובות
הוסף תשובה
|
לצפיה בתשובות
דצמבר 2023
נחליט מבעוד מועד על 'קודים'- המילה שחור תסמן "זוגי" והמילה לבן תסמן "אי זוגי".
נקבע שהרמז שהגמד הראשון (מס' 1) יגיד יהיה בהתאם לכובע של הגמד הבא אחריו-
אם לגמד מס' 2 יש כובע בצבע לבן, גמד מס' 1 יספור את כל הכובעים הלבנים של שאר הגמדים (=הגמד הראשון רואה את כל שאר הגמדים שאחריו). במידה ויש מספר זוגי של כובעים לבנים, הגמד הראשון יגיד "שחור". כך גמד מס' 2 יבין שמס הכובעים מהצבע של הכובע שלו הוא זוגי. לכן גמד מס' 2 יספור מאיזה צבע יש מס זוגי של כובעים החל ממנו והלאה (גמד 3 והלאה) וכך ידע לאיזה קבוצה הוא משתייך. כנ"ל הפוך למקרה של מספר אי זוגי של כובעים.
בתחילת הראיון סיפרו לי על המשרה ושאלו אותי כמה שאלות ואחר כך התחלנו בחלק בטכני.
שאלות מתוך הראיון
רכיב שמקבל שתי כניסות inc,dec ויציאת 3 ביטים, אם 0=inc=1,dec מוסיפים ליציאה שהייתה קודם באחד, אם 1=inc=0,dec מחסירים אחד מהיציאה, אחרת היציאה לא משתנה.