[Google Interview] כיצד למצוא את הקידומת הנפוצה הארוכה ביותר?

תגי החברה: גוגל, מיקרוסופט, אמזון, אפל, אדובי, בלומברג, e-Bay, פייסבוק

הצהרת בעיה

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

אילוצים:

1. 1 <= strs.length <= 200
2. 0 <= strs[i].length <= 200
3. strs[i] מורכב מאותיות אנגליות קטנות בלבד.

דוגמאות

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

דוגמה 1: קלט: strs = [“flower”, “flow”, “flight”] פלט: "fl" הסבר: הקידומת הנפוצה היא "fl" דוגמה 2: קלט: strs = [“dog”, “racecar”, “car”] פלט: "" הסבר: אין קידומת משותפת בין מחרוזות הקלט. דוגמה 3: קלט: strs = [“aabc”, “aabab”, “aab”, “aabbaabb”] פלט: "aab" הסבר: הקידומת הנפוצה היא "aab" דוגמה 4: קלט: strs = [“apple”, “aPP”] פלט: "א" הסבר: לא רואים בחשבון אותיות גדולות. דוגמה 5: קלט: strs = [“finxter”] פלט: "finxter" הסבר: יש רק מחרוזת קלט אחת.

כעת נצלול לשיטות שונות לפתרון הבעיה.

שיטה 1: גישת כוח ברוט

גִישָׁה: הגישה הנאיבית תהיה לבדוק כל מחרוזת ולהשוות את התווים בכל מחרוזת כדי למצוא את הקידומת הנפוצה.

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

1. אתחל את המחרוזת הראשונה ל- "curr”משתנה.
2. אם הרשימה ריקה, החזר מחרוזת ריקה.
3. אם הרשימה מכילה מחרוזת אחת בלבד, החזר מחרוזת זו.
4. לכל מחרוזת אחרת ברשימה- השווה את תו המחרוזת עם התו במשתנה "curr".
5. אם הדמויות שוות, המשך להשוות, אחרת שובר את הלולאה.
6. עדכן את "currמשתנה עם מחרוזת המשנה המותאמת.

פִּתָרוֹן:

def common_prefix(strs):
    curr = strs[0]
    if not strs:
        return " "
    if len(strs) == 1:
        return curr
    for i in range(1, len(strs)):
        if len(curr) == 0:
            break
        temp = ''
        for j in range(len(strs[i])):
            
            if j < len(curr) and curr[j] == strs[i][j]:
                temp = temp + curr[j]
            else:
                break
        
        curr = temp
    return curr  

ניתוח מקרה מבחן:

# דוגמה 1 strs = [“flower”, “flow”, “flight”] הדפסה (common_prefix (strs)) # fl # דוגמה 2 strs = [“dog”, “racecar”, “car”] הדפסה (common_prefix (strs)) # # דוגמה 3 strs = [“aabc”, “aabab”, “aab”, “aabbaabb”] הדפסה (common_prefix (strs)) # אאב # דוגמה 4 strs = [“apple”, “aPP”] הדפסה (common_prefix (strs)) # א # דוגמה 5 strs = [“finxter”] הדפסה (common_prefix (strs)) # finxter

כֵּן! זה עבר את כל מקרי הבדיקה.

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

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

שיטה 2: שימוש במיון

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

האיור הבא יעזור לך להבין את עקרון העבודה העומד מאחורי גישה זו:

בדוגמא לעיל המערך הנתון הוא [Flower, Flow, Flight]. לאחר מיון בעזרת שיטת sort () ב- Python הוא מאחסן את המיתרים בסדר הבא: [Fligth, Flow, Flower]. לאחר מיון המחרוזת, כל אלמנט/תו של המחרוזות הראשונות והאחרונות של המערך הממוין מושווים. כאשר מוצאת התאמה היא מאוחסנת במשתנה (temp). ברגע שההתאמה לא נמצאה, הלולאה נשברת והערך המאוחסן ב- temp משתנה מוחזר כפלט.

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

1. מיין את רשימת המחרוזות הנתונה.
2. אם הרשימה ריקה, החזר מחרוזת ריקה.
3. אם הרשימה מכילה מחרוזת אחת בלבד, החזר מחרוזת זו.
4. אחסן את המחרוזות הראשונות והאחרונות במשתנים "first"ו"last, "בהתאמה. גם לנתח את "tempמשתנה שיאחסן את הפלט.
5. השווה כל תו של שני המיתרים אחד אחד.
6. אם שווה, הוסף אותם למשתנה זמני, אחרת break מחוץ לעניינים.
7. לבסוף החזר את הטמפ '.

פִּתָרוֹן:

def common_prefix(strs):
    strs.sort()
    if not strs:
        return " "
    if len(strs) == 1:
        return strs[0]
    
    first = strs[0]
    last = strs[-1]
    temp = ""
    for i in range(len(first)):
        if first[i] == last[i]:
            temp = temp + first[i]
        else:
            break
    return temp

ניתוח מקרה מבחן:

# דוגמה 1 strs = [“flower”, “flow”, “flight”] הדפסה (common_prefix (strs)) # fl # דוגמה 2 strs = [“dog”, “racecar”, “car”] הדפסה (common_prefix (strs)) # # דוגמה 3 strs = [“aabc”, “aabab”, “aab”, “aabbaabb”] הדפסה (common_prefix (strs)) # אאב # דוגמה 4 strs = [“apple”, “aPP”] הדפסה (common_prefix (strs)) # א # דוגמה 5 strs = [“finxter”] הדפסה (common_prefix (strs)) # finxter

כֵּן! זה עבר את כל מקרי הבדיקה.

ניתוח מורכבות: מורכבות הזמן של שיטה זו היא O (k * n * כניסה), כאשר n הוא גודל המערך, k הוא גודל המחרוזת הארוכה ביותר, ו- log (n) הוא הזמן הנדרש למיון המערך.

פתרון אופטימלי: שימוש רוכסן וכן מַעֲרֶכֶת

גִישָׁה: זו הדרך/גישה הכי פיתונית לפתרון הבעיה הנתונה.

סיכום שיטת zip () ב- Python: ה zip() פונקציה לוקחת מספר שרירותי של iterables ומצברת אותם לאובייקט אחד חוזר, zip. הוא משלב את ערכי ה- i של כל טיעון חוזר לכדי סוג. מכאן שאם תעביר שני iterables, כל צמד מכיל שני ערכים. אם תעביר שלושה iterables, כל צמד מכיל שלושה ערכים. לדוגמה, רכז רשימות יחד [1, 2, 3] ו [4, 5, 6] ל [(1,4), (2,5), (3,6)].

קרא עוד על רוכסן() שיטה כאן!

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

1. אם הרשימה ריקה, החזר מחרוזת ריקה.
2. אם הרשימה מכילה מחרוזת אחת בלבד, החזר מחרוזת זו.
3. אתחל משתנה זמני שיאחסן מחרוזת ריקה בהתחלה.
4. עבור כל זוג בזרוע המחרוזות, השתמש בפונקציית הסט.
5. בדוק את אורך הסט. אם הוא גדול מ -1, שברו את הלולאה.
6. אחרת, עדכן את הטמפ 'לדמות הבאה.
7. טמפרטורת החזרה.

פִּתָרוֹן:

def common_prefix(strs):
    if not strs:
        return " "
    if len(strs) == 1:
        return strs[0]
    temp = ''
    for chr in zip(*strs):
        if len(set(chr)) > 1:
            break
        else:
            temp = temp + chr[0]
    return temp

ניתוח מקרה מבחן:

# דוגמה 1 strs = [“flower”, “flow”, “flight”] הדפסה (common_prefix (strs)) # fl # דוגמה 2 strs = [“dog”, “racecar”, “car”] הדפסה (common_prefix (strs)) # # דוגמה 3 strs = [“aabc”, “aabab”, “aab”, “aabbaabb”] הדפסה (common_prefix (strs)) # אאב # דוגמה 4 strs = [“apple”, “aPP”] הדפסה (common_prefix (strs)) # א # דוגמה 5 strs = [“finxter”] הדפסה (common_prefix (strs)) # finxter

כֵּן! זה עבר את כל מקרי הבדיקה.

ניתוח מורכבות: מורכבות הזמן של שיטה זו היא O (דקות (k) * n), כאשר n הוא גודל המערך ו- k הוא גודל המחרוזת הקצרה ביותר.

סיכום

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

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

---

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

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