פורסם ב זה רק קוד, מתכוננות לראיונות

גלידה

קוד: ice_cream.py
זמן קריאה: 5 דקות

חם היום!
כמה חם? כל כך חם שהלכתי לחפש שאלת תכנות בנושא גלידה, והנה מה שמצאתי – 

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

הנחות:

  1. צילי וגילי תמיד מוציאות את כל הכסף שקיבלו על גלידה.
  2. תמיד קיים זוג גלידות יחיד שיתאים לסכום הכסף שצילי וגילי קיבלו.

אוקי, שאלה חמודה. הפעם, בניגוד למנהגי, גם השארתי את הפלאף של השאלה, אז אני אתחיל מלפרק אותה לתכל'ס שלה ולעשות דוגמא.

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

ice_cream_costs = [2, 5, 3, 1] money_sums = [3, 8] choose_ice_cream(ice_cream_costs, money_sums) = [[0,3], [1,2]]

אחלה, אפשר להתחיל.
כמו תמיד, אני אתחיל עם הפתרון הנאיבי. הפתרון הנאיבי לשאלה הזו הוא שימוש קלאסי של hash-tables.
נניח שיש לי סכום יחיד x ומערך מחירים. עבור כל מחיר במערך אני רוצה לבדוק האם ההפרש x-cost גם נמצא במערך – אני יכולה לעשות את זה בעזרת hash-table שימפה את כל ההפרשים.
אני אכתוב את האלגוריתם עבור סכום ספציפי – 

def choose_ice_cream_once(ice_cream_costs, money):
	diff_to_cost = {}
	for i in range(0, len(self.ice_cream_costs)):
		cost = self.ice_cream_costs[i]
		if cost in diff_to_cost:
			return diff_to_cost[cost], i
		else:
			diff = money - cost
			diff_to_cost = i

קול, נראה טוב.
אני אריץ דוגמא עם האלגוריתם שלי – 

choose_ice_cream_once([2, 5, 3, 1], 8): diff_to_cost = {} i=0 cost = 2 diff = 6 diff_to_cost = {6:0} i=1 cost = 5 diff = 3 diff_to_cost = {6:0, 3:1} i=2 cost = 3 return (1, 2)

יאי! יש תשובה נכונה.
מה הסיבוכיות של האלגוריתם הזה?
הסיבוכיות של מעבר יחיד הוא (O(N. כיוון שבשאלה התבקשתי לחפש זוג גלידות מתאים לכל יום, אז האלגוריתם ירוץ k פעמים, כאשר k הוא גודל מערך הסכומים. אז הסיבוכיות של האלגוריתם כולו תהיה (O(KN.

האם אני יכולה לשפר את הסיבוכיות הזו? שווה לבדוק.
בעבור מעבר יחיד התשובה שנתתי למעלה היא כאמור התשובה הקלאסית והיעילה ביותר, כנ"ל לגבי מספר זניח של מעברים, אבל מה אם הייתי יודעת שאני הולכת לחפש זוגות גלידות מספר רב של פעמים? אז הייתי יכולה להשקיע בקצת preprocessing שיעשה את האלגוריתם הכללי שלי יעיל יותר. 

אבל איזה preprocessing יעזור לי פה?

נניח והייתי עוברת מראש על כל זוגות המחירים ומכניסה את סכומי המחירים שלהם לטבלה – טבלה כזו תאפשר לי למצוא את זוג הגלידות המתאים לכל סכום ב-(O(1. מגניב, לא?
הסיבוכיות של יצירת טבלה כזו היא (O(N2 (כי צריך לעבור על כל הזוגות) – ולכן ההשקעה הזו תשתלם רק במקרה שבו K≥N.
אני אכתוב את האלגוריתם הזה – 

def preprocess_ice_cream_costs(ice_cream_costs):
	all_possible_costs_sums = {}
	for i in range(0, len(ice_cream_costs)):
   		for j in range(i + 1, len(ice_cream_costs)):
       			costs_sum = ice_cream_costs[i] + ice_cream_costs[j]
       			all_possible_costs_sums[costs_sum] = (i, j)
	return all_possible_costs_sums

def choose_ice_cream_once(all_possible_costs_sums, money):
	return all_possible_costs_sums[money]

האם יש פתרון עוד יותר יעיל במקרה שבו K≥N?
לא הצלחתי למצוא כזה, אבל אשמח מאוד לשמוע אם אתן מצאתן אחד.

עכשיו לכתוב קוד!

קוד בגיט – https://github.com/mgershovitz/maya_solves/blob/master/ice_cream.py

4 תגובות בנושא “גלידה

  1. בנוגע לפתרון יותר יעיל – אני לא בטוח, אבל מאחר ומדובר בלמצוא זוג מספרים שמגיע לסכום מסוים, אז יש את האפשרות למיין את הטעמים לפי המחיר (נגיד מקטן לגדול משמאל לימין) ולהחזיק שני מצביעים, אחד מימין ואחד משמאל, ואז:
    if(A[left] + A[right] == target)
    return left.right
    if (A[left] + A[right] target
    right–
    תחת ההבנה שאם עד כה לא מצאנו את הזוג שנותן את הסכום הנדרש, והסכום הנוכחי קטן מדי, אנחנו חייבים שהטעם הזול בזוג יהיה יותר יקר,
    ואם הסכום הנוכחי גדול מדי, אנחנו חייבים שהטעם היקר בסכום יהיה זול יותר
    כשכל שלב אנחנו יודעים שפסלנו את הטעמים שנמצאים מחוץ לתחום
    (הסבר ממש בנפנופי ידיים אבל חושב שהוא נכון, אשמח להרחיב במידת הצורך)
    ואז זה NlogN המיון ועוד N על כל בדיקה

  2. And of course I accidentally deleted part of the code, will use the opportunity to fix it a bit
    while (true)
    if (left > right) // no solution found
    throw exception // the assumption is that there is a solution, but otherwise – return the output that will show there’s no solution. maybe -1,-1
    if(A[left] + A[right] == target)
    return left, right
    if (A[left] + A[right] > target)
    right–
    else // if (A[left] + A[right] < target)
    left++

    1. היי, בהחלט שקלתי את הפתרון הזה, כי אני אוהבת להשתמש בשיטת שני הפוינטרים מתי שרק אפשר!
      בסוף לא הצגתי אותו כי הוא בסיבוכיות גרועה יותר מהפתרון שלי עם ה-hash table

  3. היי! איזה כיף לקרוא את הבלוג שלך 🙂
    רציתי לשאול, במקרה ונרצה לממש את הפתרון בשפת C, האם יש גם אפשרות להשתמש בסוג של Hash Table?
    כשראיתי לראשונה את השאלה, חשבתי גם על cost-x. אז בפתרון (הנאיבי) שלי עשיתי מערך של כל הסכומים המשלימים של המחירים, ואז עבור כל מחיר בדקתי אם המשלים שלו נמצא במערך המקורי (ע״י חיפוש בינארי). זמן הריצה יהיה O(nlogn) שהוא כמובן פחות טוב מO(n), אבל אני שואלת זאת מכיוון שלפי הקוד מחפשים לפי if cost in diff וכו׳.
    ובתקציר: האם מימוש בשפת סי יגרור זמן ריצה גדול יותר?

השאר תגובה