Let S1, S2 be two stacks.
For a given element, you push it to S1, and if push it to S2 iff it is smaller than S2.top()
That allows you to track the minimum elements on the stack.
For pop(), you pop from S1, and pop for S2 only if the popped element from S1 is equal to S2.top()
שאלו שאלה על 9 מטבעות. 8 זהות במשקלן ואחת שוקלת יותר. מה הדרך הנכונה ביותר לשקילה עם מאזניים על מנת למצוא את המטבע השונה במינימום שקילות.
תשובות
הוסף תשובה
|
לצפיה בתשובות
ינואר 2022
צריך מסקימום 3 שקילות (רק שקילה אחת במקרה הטוב):
שקילה ראשונה: מטבעות 1-4 על כף מאזניים אחת, מטבעות 5-8 על כף שנייה. אם המאזניים מאוזנות אז מטבע מספר 9 הוא הכבד יותר, אם לא ממשיכים:
שקילה שנייה: לוקחים את הרביעיה הכבדה יותר ומפצלים אותה לשניים-שניים על המאזניים.
שקילה שלישית: לוקחים את זוג המטבעות הכבד יותר ומפצלים אותו למטבעות בודדים על המאזניים, וכך נגלה את המטבע הכבד ביותר.
מרץ 2022
אפשר לעשות תמיד ב2 שקילות.
לוקחים את מטבע 1-3 ואת מטבע 4-6, אם הן מאוזנות אז המטבע המזויף נמצא ב7-9. בסוף עושים עוד שקילה אחת עם ה3 מטבעות שנשאר. אם מאוזן המטבע שנותר בחוץ הוא המזויף. ככה תמיד מוצאים את התשובה ב2 שקילות.
ראיון לתפקיד 
