[Google Interview] בעיית שני הסכומים

Share on facebook
Share on twitter
Share on linkedin
Share on telegram
Share on whatsapp
Share on email
פרסומת
MAGNEZIX מגנזיקס


🏗️ תגיות החברה: גוגל, פייסבוק, אֲמָזוֹנָה

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

לכן, אם שאלה זו נשאלה בראיון שלך, האם תוכל לפתור אותה בצורה אופטימלית?

ניסוח הבעיה

נָתוּן א רשימה של מספרים שלמים “nums"ומספר שלם"target”. מצא את הסכום של שני המספרים כך שהם מצטברים למספר היעד ומחזירים את המדדים שלהם.

⚠️ אילוצים:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • קיימת תשובה תקפה אחת בלבד ואינך יכול להשתמש באותו אלמנט פעמיים.

📖דוגמאות

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

✏️ דוגמה 1:
קלט: מספרים = [2, 7, 11, 15], יעד = 9
תְפוּקָה: [0, 1]
הסבר: המספרים במדדים 0 ו- 1 מסתכמים בערך היעד 9.

✏️ דוגמה 2:
קלט: מספרים = [5, 5], יעד = 10
תְפוּקָה: [0, 1]
הסבר: המספרים במדדים 0 ו- 1 מסתכמים בערך היעד 10.

✏️ דוגמה 3:
קלט: מספרים = [-2, -1, 0, 1], יעד = 0
תְפוּקָה: [1, 3]
הסבר: המספרים במדדים 1 ו -3 מסתכמים בערך היעד 0.

✏️ דוגמה 4:
קלט: מספרים = [2, 5, 6], יעד = 4
תְפוּקָה: []
הסבר: אין מספרים ברשימה שמסתכמים בערך היעד 4.

✏️ דוגמה 5:
קלט: מספרים = [ ], יעד = 5
תְפוּקָה: []
הסבר: רשימה ריקה (מקרה קצה).

🖊️ גישה נאיבית: אלגוריתם כוח הברוט

גִישָׁה:

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

כדי לקבל תמונה ברורה של הגישה שהוסברה לעיל, הבה נסתכל על דוגמא:

מערך נתון:

בואו נתאר לעצמנו כיצד האלגוריתם המוצע יחצה את המערך ונמצא את צמד המספרים המסתכם ב -9.

לפיכך, עבור כל ערך ב- ith אינדקס, אנו עוברים בין הערכים הנותרים ברשימה ובודקים אם הוא תואם לערך היעד. בדוגמה זו, ההתאמה נמצאת כאשר ה- nums[i=2]+nums[j=4] = 0 + 9.

עכשיו, בואו נסתכל על הקוד:

def two_sum(a, x):
    for i in range(0, len(a)):
        for j in range(i + 1, len(a)):
            if a[i] + a[j] == x:
                return [i, j]
    return []

מקרי מבחן: בואו נבצע קוד זה בדוגמאות שלנו כדי לבדוק אם הוא עובד:

# Example 2:
nums = [5, 5]
target = 10
print(two_sum(nums, target))
# [0, 1]

# Example 3:
nums = [-2, -1, 0, 1]
target = 0
print(two_sum(nums, target))
# [1, 3]

# Example 4:
nums = [2, 5, 6]
target = 4
print(two_sum(nums, target))
# []

# Example 5:
nums = []
target = 5
print(two_sum(nums, target))
# []

כן! 😃 זה עבר את כל מקרי המבחן.

ניתוח מורכבות

  • מורכבות זמן: בשיטה זו, לכל מספר ברשימה, היא מנסה למצוא את השלמתה על ידי חזרה דרך שאר הרשימה. זה לוקח עַל) הגיע הזמן לחזור פעם אחת. מכאן שכאשר אנו חוזרים כאן פעמיים, מורכבות הזמן הכוללת הופכת להיות O (n)2).
  • מורכבות חלל: לפתרון זה, המרחב המשמש נותר קבוע מכיוון שאין שימוש במבני נתונים נוספים (מילון, מערכים). פיתרון זה מתגלה כמועיל ביחס לחלל כמורכבות החלל O (1).

דִיוּן: אף על פי שגישה זו הניבה את התפוקה הצפויה, עם זאת, מורכבות הזמן היא ריבועית במקרה זה. לפיכך, לשיטה זו אולי לא תהיה השפעה רבה על תשומות קטנות, אך אין לה זמן ריצה אפשרי עבור תשומות גדולות. אז האם יש אפשרות לבצע אופטימיזציה לקוד? כן, תמיד יש דרך טובה יותר!😉

🖊️ פתרון אופטימיזציה: שימוש בטבלת Hash

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

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

קרא עוד על טבלאות חשיש פה.

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

אַלגוֹרִיתְם:

  1. אתחל מילון ריק. לאחר מכן, על כל מספר ברשימה, חישב את השלמת המספר.
    • Complement = target value-current number
  2. לאחר מכן, חפש את ההשלמה בטבלת החשיש.
  3. אם ההשלמה קיימת, החזר את צמד המדדים, כלומר את אינדקס המשלים ואת מדד הערך הנוכחי.
  4. אם המשלוח אינו קיים, אחסן את המספר הנוכחי במילון.

גִישָׁה:

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

  • רשימה נתונה:
  • ערך מטרה: 9

בדוגמה שלעיל כאשר המשכנו לאחסן את אינדקס הערכים תוך כדי חציית הרשימה במילון עד שנתקלנו בזוג שבו המחושב מַשׁלִים כבר היה קיים / נשמר במילון. כאן, ב 5ה איטרציה, ההשלמה של '9' (בְּ מדד 4), כלומר '0' נמצא נוכח ב 2נד אינדקס במילון. הנה תרשים נוסף המייצג את זרימת השליטה בגישה זו:

בואו נסתכל על הקוד:

def two_sum(nums, target):
    d = {}
    for i, val in enumerate(nums):
        comp = target - val
        if comp in d:
            return [d[comp], i]
        else:
            d[val] = i
    return []

💡 הערה
של פייתון מובנה enumerate(iterable) פונקציה מאפשרת לך לולאה על כל האלמנטים ב- iterable והדלפקים הקשורים אליהם. רשמית, זה לוקח iterable כטיעון קלט ו מחזיר איטרציה של צמרות (i, x)– לכל מרכיב שאפשר לחזור עליו x. הערך הכפול שלם שלם הוא המונה של האלמנט x בתוך ה iterable, מתחיל לספור מ 0. ערך הכפול השני הוא התייחסות לאלמנט x את עצמה. לדוגמה, enumerate(['a', 'b', 'c']) מחזיר איטרציה (0, 'a'), (1, 'b'), (2, 'c'). באפשרותך לשנות את ברירת המחדל התחל אינדקס של הדלפק על ידי הגדרת ה- ארגומנט מספר שלם שני אופציונלי enumerate(iterable, start).

קרא עוד על Python's לִמְנוֹת() שיטה פה.

בואו ננסה זאת במקרי הבדיקה שלנו:

# Example 1:
nums = [11, 2, 15, 7]
target = 9
print(two_sum(nums, target))
# [1, 3]

# Example 2:
nums = [5, 5]
target = 10
print(two_sum(nums, target))
# [0, 1]

# Example 3:
nums = [-2, -1, 0, 1]
target = 0
print(two_sum(nums, target))
# [1, 3]

# Example 4:
nums = [2, 5, 6]
target = 4
print(two_sum(nums, target))
# []

# Example 5:
nums = []
target = 5
print(two_sum(nums, target))
# []

הורא! זה עבר את כל מקרי המבחן.

ניתוח מורכבות

  • מורכבות זמן: באמצעות גישה זו, עליך לחצות את הרשימה פעם אחת בלבד. לפיכך מורכבות זמן הריצה נשארת ליניארית, כלומר עַל). ה מורכבות הזמן לחזור על מילון (טבלת hash) בפייתון גם כן עַל). לפיכך, הדבר מבטיח כי לגישה זו מורכבות זמן כוללת של עַל).
  • מורכבות חלל: במקרה של התרחיש הגרוע ביותר, נצטרך לעבור בסוף הרשימה, ולכן להוסיף את כל המספרים למילון. לפיכך, מורכבות החלל לפתרון זה היא O (N) (שטח שנלקח על ידי המילון).

Solution️ פתרון בונוס: גישת Two Pointer

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

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

בואו נסתכל על הקוד:

def two_sum(nums, x):
    a = sorted(nums)
    left, right = 0, len(a) - 1

    while left < right:
        if a[left] + a[right] == x:
            if a[left] == a[right]:
                return [nums.index(a[left]), nums.index(a[left]) + 1]
            else:
                return [nums.index(a[left]), nums.index(a[right])]

        elif a[left] + a[right] < x:
            left = left + 1
        else:
            right = right - 1

    return []

בואו ננסה זאת על הדוגמאות שלנו:

מספרים יַעַד תְפוּקָה
[2, 7, 11, 15] 9 [0,1]
[5, 5] 10 [0,1]
[-2, -1, 0, 1] 0 [1,3]
[2, 5, 6] 4 []
[] 5 []

זה עובר את כל מקרי המבחן.

ניתוח מורכבות

מכיוון שהמצביעים יעברו רק פעם אחת ברשימה, אך התקורה בשיטה זו היא שעליך למיין את הרשימה תחילה. לפיכך, מורכבות הזמן הכוללת לפתרון זה הופכת להיות O (nlogn).

סיכום

אני מקווה שנהנית משאלת ראיון קידוד זו. אנא השארו ו הירשם כמנוי לבעיות קידוד מעניינות יותר.

זיכויים לפרסום: שובאם סייון ורשי אגארוואל


מוּמלָץ: האקדמיה למדעי המחשב פינקסטר

  • האם אתה רוצה לשלוט במהירות ב- Python IDE הפופולרי ביותר?
  • קורס זה ייקח אותך ממתחיל למומחה ב- PyCharm תוך 90 דקות.
  • לכל מפתח תוכנה, חשוב לשלוט היטב ב- IDE, לכתוב, לבדוק ולבדוק קוד באיכות גבוהה במאמץ מועט.
המדריך השלם ל- PyCharm

הצטרפו לכיתת המאסטר של PyCharm עכשיו, ותשתלט על PyCharm עד מחר!

.



קישור לכתבת המקור – 2021-06-29 22:11:41

Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn
Share on telegram
Telegram
Share on whatsapp
WhatsApp
Share on email
Email
פרסומת
MAGNEZIX מגנזיקס

עוד מתחומי האתר