Mellanox – Design Verification Engineer

שאלה 1:

נתון רכיב עם 3 כניסות ו-2 יציאות.

הרכיב מוציא מספר 'אחדים' שיש בכניסה.

למשל, עבור כניסות 001, 010, 100 – ביציאה יהיה 01 ('אחד' אחד)

עבור כניסות 011, 101, 110 – ביציאה יהיה 10 (שני 'אחדים')

עבור כניסה 111 – ביציאה 11 (שלושה 'אחדים')

מהרכיבים כנ"ל בלבד תבנה רכיב עם 7 כניסות ו-3 יציאות

פתרון:

ישנם סה"כ 4 רכיבים:

שני רכיבים (רכיב1 ורכיב 2) מקבלים כניסות X1-X6

מוצא שלהם זה Y1-Y4

רכיב 3 מקבל כניסות : Y2, Y4 ו-X7

מוצא של רכיב 3: Z3, Z4

רכיב 4 מקבל כניסות: Y1, Y3 ו-Z3

מוצא של רכיב 4: Z1, Z2

מוצא של הרכיב היעד: Z1, Z2 ו-Z4

לבדיקת התאמה

שאלה 2:

ישנם 25 סוסים.

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

בכל מירוץ יכולים להשתתף עד 5 סוסים.

תשובה: 7 מירוצים.

פתרון:

שלב 1: מריצים 5 מרוצים עם כל הסוסים הניתנים (נמספר מירוצים מ-1 עד 5)

בגמר המירוצים כל סוס מקבל מספר אישי: 'מקום' – 'מספר מירוץ'

למשל שלושה מנצחים במירוץ 4 יהיו: 4-1, 4-2, 4-3

מסקנת ביניים: עקרונית אותנו מעניינים 3 סוסים המנצחים בכל מירוץ – סה"כ 15 סוסים.

שלב 2: מכניסים למירוץ 6 את חמישה הסוסים המנצחים בכל מירוץ (סוסים 1-1, 2-1, 3-1, 4-1, 5-1)

המנצח במירוץ 6 הוא המהיר בין כל ה-25 – המקום הראשון המוחלט.

ועכשיו הסופר טריק – לבחור מי ישתתף במירוץ השביעי והאחרון שייקבע את מקום השני והשלישי.

שלב 3:

נניח המנצח הגדול (במירוץ 6) הוא במקור המנצח במירוץ 4 (4-1 == 6-1).

כלומר המנצח הגדול ניצח את סוסים: 1-1, 2-1, 3-1, 5-1

ברור לגמרי שסוס 2-1 מהיר יותר מסוס 2-2.

וסוס 2-2 מהיר יותר מסוס 2-3.

כלומר סוס 2-3 יכול לזכות לכל היותר במקום רביעי כי 4-1, 2-1 ו-2-2 בוודאות מהירים ממנו.

לכן 2-3 לא ממשיך תחרות.

באותו אופן יורדים מתחרות סוסים 1-3, 3-3, 5-3

סוס 4-3 עדיין לא יורד מתחרות ונחשב למועמד כי ייתכן וכל הסוסים הכי מהירים היו במירוץ 4.

עכשיו נתבונן בסוס 6-2 – סוס במקום השני במירוץ 6.

בזמנו סוס 6-2 היה המנצח במירוץ שלו. נניח זה סוס 5-1 (5-1 == 6-2)

סוס 5-1 הפסיד לסוס 4-1, אבל ניצח את 1-1, 2-1, 3-1

מה עכשיו ניתן להגיד למשל על סוס 3-2?

שישנם לפחות שלושה סוסים מהירים ממנו: 4-1, 5-1, 3-1

כלומר סוס 3-2 יורד מתחרות כמו גם סוסים 1-2, 2-2.

נניח סוס 6-3 == 3-1.

מכאן סוסים 1-1, 2-1 שהפסידו בגדול במירוץ 6 לא ישתתפו גם

נותרנו עם 5 מועמדים למירוץ 7 ואחרון: 5-1 (6-2), 3-1 (6-3), 5-2, 4-2, 4-3

שניים הראשונים במירוץ 7 יתמפו למקומות שני ושלישי בהתאם בתחרות הכללית.

לבדיקת התאמה