מדריך ליטקוד לראיונות תוכנה


ליטקוד לראיונות
page icon

פאטרנים בראיונות אלגוריתמים

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

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

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

שני פויינטרים - משני הצדדים פנימה

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

סרטון לפתוח איתו:

איך לחשוב על זה

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

איך לזהות

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

איפה נופלים

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

שאלות לתרגול

קל

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

    הפאטרן המועדף פה: שני פויינטרים מהקצוות פנימה.

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

    הפאטרן המועדף פה: שני פויינטרים מהקצוות פנימה.

    1. מתחילים מהקצוות ומתקדמים פנימה כל עוד התווים שווים.
    2. כשיש אי התאמה, לא מוחקים מיד סתם צד. מנסים שתי אפשרויות: לדלג על השמאלי או לדלג על הימני.
    3. בכל אחת מהאפשרויות בודקים אם החלק שנשאר הוא פלינדרום רגיל.
    4. אם אחת מהן עובדת, המחיקה היחידה הספיקה.

בינוני

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

    הפאטרן המועדף פה: שני פויינטרים מהקצוות פנימה.

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

    הפאטרן המועדף פה: מיון ואז שני פויינטרים.

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

קשה

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

    הפאטרן המועדף פה: מיון ואז שני פויינטרים.

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

    הפאטרן המועדף פה: שני פויינטרים עם גבולות משני הצדדים.

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

פויינטר איטי ומהיר

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

סרטון לפתוח איתו:

איך לחשוב על זה

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

איך לזהות

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

איפה נופלים

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

שאלות לתרגול

קל

  1. ליטקוד 202 - מספר שמח
    מקבלים מספר. בכל סיבוב לוקחים את הספרות שלו, מעלים כל ספרה בריבוע, מחברים, והסכום הזה הופך להיות המספר החדש. למשל, אם מתחילים מ-19, מגיעים ל-82, אחר כך ל-68, אחר כך ל-100, ואז ל-1. צריך לבדוק אם אחרי חזרות כאלה מגיעים בסוף למספר 1, או שנכנסים ללופ של מספרים שחוזרים על עצמם.
    הצג תשובה

    הפאטרן המועדף פה: פויינטר איטי ומהיר על רצף ערכים.

    1. מתייחסים לכל מספר כאילו הוא צומת, והחישוב הבא הוא החץ לצומת הבא.
    2. מריצים ערך איטי צעד אחד וערך מהיר שני צעדים.
    3. אם אחד הערכים במסלול נהיה 1, המספר שמח.
    4. אם האיטי והמהיר נפגשים בערך אחר, נכנסנו ללופ שלא יגיע ל-1.
  2. ליטקוד 234 - פלינדרום ברשימה מקושרת
    מקבלים רשימה מקושרת, וצריך לבדוק אם הערכים שלה נקראים אותו דבר מההתחלה ומהסוף. בגלל שזו רשימה מקושרת, אי אפשר פשוט לקפוץ לסוף כמו במערך.
    הצג תשובה

    הפאטרן המועדף פה: פויינטר איטי ומהיר עם שינוי חצים.

    1. משתמשים באיטי ומהיר כדי למצוא את האמצע.
    2. הופכים את החצי השני של הרשימה.
    3. משווים את החצי הראשון מול החצי ההפוך.
    4. אם כל הערכים תואמים, הרשימה מתנהגת כמו פלינדרום.

בינוני

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

    הפאטרן המועדף פה: פויינטר איטי ומהיר.

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

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

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

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

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

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

קשה

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

    הפאטרן המועדף פה: פויינטר איטי ומהיר עם בדיקת כיוון.

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

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

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

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

    1. בדוגמה [1, 3, 4, 2, 2] מתחילים עם קבוצה ריקה.
    2. רואים 1, 3, 4 ואז 2, וכל אחד מהם נכנס לקבוצה כי עוד לא ראינו אותו.
    3. כשמגיעים ל-2 בפעם השנייה, הוא כבר נמצא בקבוצה, ולכן מחזירים 2.
    4. זה פתרון בזמן לינארי, אבל הוא דורש זיכרון לינארי כי שומרים מספרים שכבר ראינו.

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

    1. בדוגמה [1, 3, 4, 2, 2], אינדקס 0 מכיל 1, אז הקפיצה הבאה היא לאינדקס 1.
    2. אינדקס 1 מכיל 3, אז עוברים לאינדקס 3. אינדקס 3 מכיל 2, אז עוברים לאינדקס 2.
    3. אינדקס 2 מכיל 4, אז עוברים לאינדקס 4. אינדקס 4 מכיל 2, אז חוזרים לאינדקס 2.
    4. המסלול נראה ככה: 0, 1, 3, 2, 4, 2, 4, 2. ברגע שחוזרים ל-2, נכנסנו למעגל.
    5. למה הכפילות יוצרת מעגל? כי שני אינדקסים שונים מובילים לאותו מקום. כאן גם אינדקס 3 וגם אינדקס 4 מובילים ל-2.

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

חלון זז

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

סרטון לפתוח איתו:

איך לחשוב על זה

  • שומרים חלון רציף: שמאל, ימין, והמידע הקטן שחייבים לדעת עליו.
  • ימין מרחיב, שמאל מנקה אחריו כשהחלון נהיה לא חוקי.
  • בחלון קבוע פשוט מוסיפים חדש ומחסירים ישן.
  • בחלון משתנה המשחק הוא למצוא את החלון הכי טוב שעדיין עומד בתנאים.
  • דוגמה 1: סכום מקסימלי של חלון בגודל K - נגיד שצריך למצוא את הסכום הכי גדול של שלושה איברים רצופים. מחשבים את החלון הראשון, ואז בכל צעד מוסיפים את האיבר החדש ומחסירים את האיבר שיצא. החלון זז צעד, אבל הראש לא מתחיל מאפס.
  • דוגמה 2: המחרוזת הכי ארוכה בלי תווים כפולים - הימין מרחיב את החלון. אם נכנס תו שכבר קיים בפנים, שמאל מתקדם עד שהחלון חוזר להיות חוקי. פה החלון לא בגודל קבוע, הוא בגודל "כמה שמותר כרגע".

איך לזהות

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

איפה נופלים

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

שאלות לתרגול

קל

  1. ליטקוד 1343 - מספר חלונות עם ממוצע מספיק גבוה
    מקבלים מערך, גודל חלון K וסף ממוצע, וצריך לספור כמה חלונות עומדים בסף.
    הצג תשובה

    הפאטרן המועדף פה: חלון זז קבוע.

    1. מחשבים סכום של חלון בגודל K.
    2. בכל תזוזה מוסיפים את הנכנס ומחסירים את היוצא.
    3. בודקים בכל חלון אם הסכום שלו מספיק גבוה ביחס לסף.
  2. ליטקוד 1456 - מספר תנועות מקסימלי בחלון
    מקבלים מחרוזת באנגלית ומספר K. צריך לבדוק כל רצף צמוד באורך K, כלומר כל חלון של K תווים אחד אחרי השני. בכל חלון סופרים רק אותיות תנועה באנגלית כמו a, e, i, o, u. התשובה היא מספר התנועות הכי גדול שמופיע באחד החלונות.
    הצג תשובה

    הפאטרן המועדף פה: חלון זז קבוע.

    1. בונים חלון ראשון באורך K, וסופרים כמה מתוך K התווים שלו הם a, e, i, o, u.
    2. מזיזים את החלון תו אחד ימינה. אם התו שיצא היה תנועה, מורידים אותו מהספירה. אם התו שנכנס הוא תנועה, מוסיפים אותו לספירה.
    3. אחרי כל הזזה שומרים את הספירה הכי גבוהה שנראתה.

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

בינוני

  1. ליטקוד 209 - תת-מערך מינימלי עם סכום יעד
    מקבלים מערך של מספרים חיוביים וסכום יעד. צריך למצוא את הרצף הצמוד הקצר ביותר שהסכום שלו מגיע לפחות ליעד.
    הצג תשובה

    הפאטרן המועדף פה: חלון זז משתנה.

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

    הפאטרן המועדף פה: חלון זז עם ספירות.

    1. שומרים ספירות של התווים בתוך החלון.
    2. בודקים כמה תווים צריך להחליף: אורך החלון פחות השכיחות הגבוהה ביותר.
    3. אם צריך יותר מ-K החלפות, מצמצמים משמאל.
    4. כל חלון שדורש לכל היותר K החלפות הוא מועמד לרצף הכי ארוך.

קשה

  1. ליטקוד 76 - חלון מינימלי שמכיל מחרוזת
    מקבלים שתי מחרוזות: מחרוזת גדולה ומחרוזת קטנה שצריך "לכסות". צריך למצוא את הרצף הקצר ביותר בתוך המחרוזת הגדולה שמכיל את כל התווים של המחרוזת הקטנה, כולל כפילויות אם יש.
    הצג תשובה

    הפאטרן המועדף פה: חלון זז משתנה עם ספירות.

    1. שומרים ספירות של התווים שצריך למצוא.
    2. מרחיבים את ימין עד שהחלון מכיל את כל הדרוש.
    3. אחר כך מצמצמים משמאל כל עוד החלון עדיין חוקי, כדי למצוא חלון קצר יותר.
  2. ליטקוד 239 - מקסימום בכל חלון זז
    מקבלים מערך וגודל K, וצריך להחזיר את הערך המקסימלי בכל חלון רציף באורך K.
    הצג תשובה

    הפאטרן המועדף פה: חלון זז עם תור מונוטוני.

    1. שומרים מועמדים למקסימום בסדר יורד.
    2. מסירים מהתור איברים שיצאו מהחלון.
    3. ראש התור הוא המקסימום של החלון הנוכחי.

חיפוש בינארי

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

סרטון לפתוח איתו:

איך לחשוב על זה

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

איך לזהות

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

איפה נופלים

  • להגיד "חיפוש בינארי" לפני שהוכחנו שיש בכלל מה לחצות.
  • לעצור על תשובה שעובדת, למרות שהשאלה ביקשה את הראשונה או הקטנה ביותר שעובדת.

שאלות לתרגול

קל

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

    הפאטרן המועדף פה: חיפוש בינארי על גבול.

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

    הפאטרן המועדף פה: חיפוש בינארי על גבול.

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

בינוני

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

    הפאטרן המועדף פה: חיפוש בינארי על תשובה.

    1. מגדירים טווח אפשרי לשורש.
    2. בודקים את האמצע לפי הריבוע שלו.
    3. אם הריבוע קטן או שווה למספר, אפשר לנסות תשובה גדולה יותר.
    4. אם הריבוע גדול מדי, צריך לחפש שמאלה.
  2. ליטקוד 153 - המינימום במערך ממוין שסובב
    מקבלים מערך שהיה ממוין מהקטן לגדול, אבל מישהו "חתך" אותו באמצע והעביר את החלק האחרון להתחלה. למשל, מערך רגיל שעולה כמו מדרגות:[2, 4, 6, 8, 10, 12]יכול להפוך אחרי סיבוב ל-[10, 12, 2, 4, 6, 8]. זה עדיין אותו מערך, רק שהסדר נשבר בדיוק במקום שבו חוזרים למספרים הקטנים. במקרה הזה צריך להחזיר 2, כי הוא הערך הקטן ביותר.
    הצג תשובה

    הפאטרן המועדף פה: חיפוש בינארי על נקודת סיבוב.

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

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

קשה

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

    הפאטרן המועדף פה: חיפוש בינארי על תשובה.

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

    דוגמה קטנה: נניח שהמשקלים הם [3, 2, 2, 4, 1, 4] ויש 3 ימים. בקיבולת 5 נקבל יום ראשון [3, 2], יום שני [2], יום שלישי [4, 1], ואז נשארת החבילה [4] ליום רביעי. כלומר 5 לא מספיק.

    בקיבולת 6 זה כבר עובד: יום ראשון [3, 2], יום שני [2, 4], יום שלישי [1, 4]. סיימנו ב-3 ימים, אז 6 היא קיבולת אפשרית.

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

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

    הפאטרן המועדף פה: חיפוש בינארי על תשובה.

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

חיפוש לרוחב

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

סרטון לפתוח איתו:

איך לחשוב על זה

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

איך לזהות

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

איפה נופלים

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

שאלות לתרגול

קל

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

    הפאטרן המועדף פה: חיפוש לרוחב לפי רמות.

    1. מתחילים מהשורש ומתקדמים רמה אחרי רמה.
    2. העלה הראשון שמגיעים אליו נמצא בעומק המינימלי.
    3. אין צורך להמשיך לענפים עמוקים יותר אחרי שמצאנו עלה ראשון.
  2. ליטקוד 559 - עומק מקסימלי של עץ עם כמה ילדים
    מקבלים עץ שבו לכל צומת יכולה להיות רשימת ילדים, לא רק שמאל וימין. צריך למצוא את המסלול הארוך ביותר מהשורש עד אחד העלים.
    הצג תשובה

    הפאטרן המועדף פה: חיפוש לרוחב או לעומק.

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

בינוני

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

    הפאטרן המועדף פה: חיפוש לרוחב.

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

    הפאטרן המועדף פה: חיפוש לרוחב מכמה מקורות.

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

קשה

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

    הפאטרן המועדף פה: חיפוש לרוחב בגרף לא מפורש.

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

    הפאטרן המועדף פה: חיפוש לרוחב על גרף לא מפורש.

    1. מתייחסים לכל קו אוטובוס כמעבר שמוביל להרבה תחנות.
    2. מתחילים מכל הקווים שנוגעים בתחנת ההתחלה.
    3. כל שכבה בחיפוש היא עוד אוטובוס שלקחנו.

חיפוש לעומק

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

סרטון לפתוח איתו:

איך לחשוב על זה

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

איך לזהות

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

איפה נופלים

  • להסתפק ב"כבר ראיתי" כשבעצם צריך לדעת "האם הוא במסלול הפעיל עכשיו".
  • לבדוק רק מהצומת הראשון ולשכוח שיש גרפים שלא מחוברים לחתיכה אחת יפה.

שאלות לתרגול

קל

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

    הפאטרן המועדף פה: חיפוש לעומק על עץ.

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

    הפאטרן המועדף פה: חיפוש לעומק.

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

בינוני

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

    הפאטרן המועדף פה: חיפוש לעומק.

    1. עוברים על כל עיר.
    2. אם העיר עוד לא בוקרו בה, מתחילים ממנה חקירה.
    3. החקירה מסמנת את כל הערים שנמצאות באותו רכיב.
    4. מספר החקירות החדשות הוא מספר המחוזות.
  2. ליטקוד 130 - אזורים מוקפים
    מקבלים לוח של תאים עם אותיות O ו-X. אזור של O צריך להפוך ל-X רק אם הוא מוקף לגמרי ב-X ולא נוגע בגבול הלוח. כל O שמחובר לגבול נשאר כמו שהוא.
    הצג תשובה

    הפאטרן המועדף פה: חיפוש לעומק מהגבולות.

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

קשה

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

    הפאטרן המועדף פה: חיפוש לעומק עם ערך חוזר וערך גלובלי.

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

    הפאטרן המועדף פה: חיפוש לעומק עם זיכרון תוצאות.

    1. מכל תא מנסים להמשיך רק לתאים גדולים יותר.
    2. שומרים לכל תא את אורך המסלול הטוב ביותר שמתחיל ממנו.
    3. בלי שמירה כזו, אותם מסלולים יחושבו שוב ושוב.

חזרה לאחור - לחזור אחורה כשצריך

חזרה לאחור זה חיפוש לעומק עם נימוסים. בוחרים משהו, ממשיכים, ואם הבחירה הרסה לנו את החיים - מבטלים אותה וחוזרים לנסות משהו אחר.
המשפט לזכור: מנסים, מסמנים, ממשיכים, ואז מבטלים. בלי הביטול אין פה קסם.

סרטון לפתוח איתו:

איך לחשוב על זה

  • בונים פתרון חלקי, לא קופצים ישר לסוף.
  • מנסים בחירה, נותנים לה צ'אנס, ואז מחזירים את המצב אחורה.
  • עוצרים כשיש פתרון מלא, או כשהענף כבר מסריח מכישלון.
  • הביטול הוא החלק שאסור לחפף בו. ענף אחד לא אמור ללכלך ענף אחר.
  • דוגמה 1: פרמוטציות ותתי-קבוצות - בכל שלב בוחרים איבר להכניס או לא להכניס. אחרי שמסיימים ענף אחד, מוציאים את הבחירה האחרונה וחוזרים לנסות ענף אחר.
  • דוגמה 2: בעיית המלכות - שמים מלכה שורה אחרי שורה. אם משבצת מתנגשת עם מלכה קיימת, לא ממשיכים משם. אם היא חוקית, ממשיכים לשורה הבאה. זה בדיוק גיזום של עץ אפשרויות ענק.

איך לזהות

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

איפה נופלים

  • לשכוח לבטל בחירה לפני שעוברים הלאה. זו הטעות הקלאסית.
  • לתת לכל ענף לרוץ עד הסוף גם כשכבר ברור שאין לו סיכוי.

שאלות לתרגול

קל

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

    הפאטרן המועדף פה: חזרה לאחור על בחירות.

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

    הפאטרן המועדף פה: חזרה לאחור עם שתי בחירות לכל אות.

    1. עוברים על התווים לפי סדר.
    2. אם התו הוא אות, מנסים גם צורה קטנה וגם צורה גדולה.
    3. אם הוא לא אות, ממשיכים איתו כמו שהוא.

בינוני

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

    הפאטרן המועדף פה: חזרה לאחור.

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

    הפאטרן המועדף פה: חזרה לאחור עם גיזום.

    1. בונים צירוף חלקי וסכום נוכחי.
    2. אם הסכום הגיע ליעד, שומרים את הצירוף.
    3. אם הסכום עבר את היעד, עוצרים את הענף.
    4. שומרים אינדקס התחלה כדי לא לייצר את אותם צירופים בסדר אחר.

קשה

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

    הפאטרן המועדף פה: חזרה לאחור על גריד.

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

    הפאטרן המועדף פה: חזרה לאחור עם בדיקת חוקיות.

    1. מחפשים תא ריק ומנסים בו מספרים חוקיים.
    2. אחרי מספר חוקי ממשיכים לתא הבא.
    3. אם נתקעים, מבטלים את הבחירה וחוזרים לנסות מספר אחר.

תור עדיפויות וערימה - מי הכי דחוף עכשיו

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

סרטון לפתוח איתו:

איך לחשוב על זה

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

איך לזהות

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

איפה נופלים

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

שאלות לתרגול

קל

  1. ליטקוד 703 - האיבר ה-K הכי גדול בזרם
    מקבלים זרם מספרים ומספר K, וצריך לדעת בכל שלב מהו האיבר ה-K הכי גדול.
    הצג תשובה

    הפאטרן המועדף פה: תור עדיפויות וערימה.

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

    הפאטרן המועדף פה: ערימה לשליפת הכי גדול.

    1. שומרים את כל האבנים בערימה שמחזירה את הכבדה ביותר.
    2. בכל צעד מוציאים שתי אבנים.
    3. אם נשאר הפרש ביניהן, מחזירים את ההפרש לערימה.

בינוני

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

    הפאטרן המועדף פה: תור עדיפויות וערימה.

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

    הפאטרן המועדף פה: תור עדיפויות וערימה.

    1. העדיפות היא המרחק של נקודה מהראשית.
    2. אפשר להשתמש במרחק בריבוע כדי לא להתעסק עם שורש.
    3. שומרים ערימה בגודל K של הנקודות הכי קרובות.
    4. כל נקודה רחוקה יותר מהגבול הנוכחי לא מעניינת כרגע.

קשה

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

    הפאטרן המועדף פה: שתי ערימות.

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

    הפאטרן המועדף פה: מיון עם ערימה לשמירת הקבוצה הטובה ביותר.

    1. ממיינים לפי יחס השכר לאיכות.
    2. בכל רגע שומרים בערימה את K האיכויות הרלוונטיות ביותר.
    3. בודקים עלות מועמדת לפי היחס הנוכחי וסכום האיכויות.

תכנון דינמי - לזכור תוצאות בדרך

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

סרטון לפתוח איתו:

איך לחשוב על זה

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

איך לזהות

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

איפה נופלים

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

שאלות לתרגול

קל

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

    הפאטרן המועדף פה: תכנון דינמי.

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

    הפאטרן המועדף פה: תכנון דינמי בסיסי.

    1. כל ערך נבנה משלושת הערכים שלפניו.
    2. שומרים את הערכים שכבר חושבו במקום לחשב אותם מחדש.
    3. אפשר להחזיק רק שלושה ערכים אחרונים ולא את כל הטבלה.

בינוני

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

    הפאטרן המועדף פה: תכנון דינמי על סכומים.

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

    הפאטרן המועדף פה: תכנון דינמי דו-ממדי.

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

קשה

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

    הפאטרן המועדף פה: תכנון דינמי דו-ממדי.

    1. כל תא מייצג את המחיר להפוך תחילית אחת לתחילית אחרת.
    2. אם התווים שווים, ממשיכים בלי עלות חדשה.
    3. אם הם שונים, בוחרים את הטוב מבין הוספה, מחיקה והחלפה.
  2. ליטקוד 312 - פיצוץ בלונים
    מקבלים שורה של בלונים עם מספר על כל בלון. כשמפוצצים בלון, מקבלים מטבעות לפי הערך שלו והערכים של השכנים שנשארו לידו באותו רגע. צריך לבחור סדר פיצוץ שמביא את מספר המטבעות המקסימלי.
    הצג תשובה

    הפאטרן המועדף פה: תכנון דינמי על טווחים.

    1. חושבים מי הבלון האחרון שמתפוצץ בתוך טווח, לא הראשון.
    2. בחירה בבלון אחרון מחלקת את הטווח לשני טווחים קטנים יותר.
    3. שומרים תשובה לכל טווח כדי לא לחשב שוב את אותם חלקים.

שינוי חצים ברשימה מקושרת - לשנות חצים בלי לאבד את הרשימה

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

סרטון לפתוח איתו:

איך לחשוב על זה

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

איך לזהות

  • תחפשו שאלות על רשימה מקושרת, היפוך, מחיקה, הזזה של צמתים, או שינוי של החץ הבא.
  • תמיד תבדקו מקרי קצה: רשימה ריקה, צומת אחד, שני צמתים, והאם הראש עצמו משתנה.
  • אם אתם עומדים לשנות חץ, תשאלו קודם: האם שמרתי את הדרך להמשך הרשימה?

איפה נופלים

  • למחוק או להפוך צומת לפני ששמרנו איך מגיעים להמשך הרשימה.
  • לפתור את האמצע היפה ולשכוח רשימה ריקה, צומת אחד, או ראש שנמחק.

שאלות לתרגול

קל

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

    הפאטרן המועדף פה: בניית רשימה בעזרת חצים.

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

    הפאטרן המועדף פה: מעבר על רשימה מקושרת ושינוי חצים.

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

בינוני

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

    הפאטרן המועדף פה: שינוי חצים ברשימה מקושרת.

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

    הפאטרן המועדף פה: פויינטר איטי ומהיר עם שינוי חצים.

    1. מוצאים את אמצע הרשימה בעזרת איטי ומהיר.
    2. הופכים את החצי השני של הרשימה.
    3. משלבים צומת מהחצי הראשון ואז צומת מהחצי השני.
    4. שומרים את ההמשכים לפני כל שינוי חץ כדי לא לנתק את הרשימה.

קשה

  1. ליטקוד 25 - היפוך צמתים בקבוצות של K
    מקבלים רשימה מקושרת וגודל קבוצה K, וצריך להפוך כל קבוצה מלאה של K צמתים.
    הצג תשובה

    הפאטרן המועדף פה: שינוי חצים בקבוצות.

    1. בודקים שיש קבוצה מלאה לפני שמתחילים להפוך.
    2. הופכים את החצים רק בתוך הקבוצה הנוכחית.
    3. מחברים את סוף הקבוצה ההפוכה להמשך הרשימה ואת הקבוצה הקודמת להתחלה החדשה.
  2. ליטקוד 138 - העתקת רשימה עם פויינטר אקראי
    מקבלים רשימה מקושרת שבה לכל צומת יש פויינטר רגיל לצומת הבא וגם פויינטר אקראי שיכול להצביע לכל צומת אחר ברשימה או להיות ריק. צריך ליצור עותק מלא שבו גם הפויינטרים האקראיים מצביעים לעותקים, לא לצמתים המקוריים.
    הצג תשובה

    הפאטרן המועדף פה: מבנה עזר או שזירת צמתים.

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

בחירת מבני נתונים ושמירת חוקים - לבחור כלי ולשמור חוק

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

סרטון לפתוח איתו:

איך לחשוב על זה

  • קודם מזהים מה הפעולה שבאמת חוזרת: חיפוש, הכנסה, מחיקה, מיון, שכיחות או שמירת סדר.
  • אחר כך בוחרים כלי לפי המחיר שלו: זמן, זיכרון, יציבות והמקרה הגרוע.
  • בודקים איזה חוק אסור לשבור: גבולות בעץ חיפוש, פיזור ב-Hashtable, או כיוון בגרף.
  • בראיון, החלק שמרשים הוא דווקא להגיד מה הכלי לא מבטיח.
  • דוגמה 1: בחירה בין מיונים - כששואלים על מיון, לא מספיק להגיד אן כפול לוג אן ולנוח. צריך לדעת מתי חשוב המקרה הגרוע ביותר, מתי חשוב זיכרון, מתי צריך יציבות, ולמה מיון מהיר ו-מיון מיזוג לא נותנים בדיוק אותה עסקה.
  • דוגמה 2: התנגשויות ב-Hashtable - Hashtable נותן גישה מהירה בממוצע, אבל רק אם מבינים שיש התנגשויות. אפשר לפתור אותן עם שרשור, או עם חיפוש מקום פנוי בתוך הטבלה, אבל בכל מקרה זמן קבוע הוא לא קסם מוחלט אלא הבטחה שתלויה בפיזור טוב ובעומס סביר.

איך לזהות

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

איפה נופלים

  • להגיד ש-Hashtable תמיד עובד בזמן קבוע. זה לא קסם, יש התנגשויות ויש עומס.
  • לבדוק רק ילד ימני וילד שמאלי בעץ חיפוש, כאילו תת-העץ לא יכול להרוס לנו את החגיגה.

שאלות לתרגול

קל

  1. ליטקוד 217 - האם יש כפילויות
    מקבלים מערך מספרים, וצריך לבדוק אם יש מספר שכבר הופיע קודם. לא צריך למצוא את כל הכפילויות; מספיק לדעת אם קיימת לפחות אחת.
    הצג תשובה

    הפאטרן המועדף פה: Hashtable לשמירת ערכים שכבר ראינו.

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

    הפאטרן המועדף פה: טבלת ספירות.

    1. אם האורכים שונים, אי אפשר להיות אנגרמה.
    2. סופרים כמה פעמים כל אות מופיעה במחרוזת הראשונה.
    3. מורידים ספירות לפי המחרוזת השנייה.
    4. אם כל הספירות התאפסו בלי חריגות, זו אנגרמה.

בינוני

  1. ליטקוד 49 - קיבוץ אנגרמות
    מקבלים רשימת מילים, וצריך לקבץ יחד מילים שמורכבות מאותן אותיות באותן כמויות. למשל, מילים עם אותו "מלאי אותיות" אמורות להגיע לאותה קבוצה.
    הצג תשובה

    הפאטרן המועדף פה: Hashtable עם מפתח חכם.

    1. מחליטים איך לייצר מפתח לכל מילה: מיון אותיות או ספירת אותיות.
    2. מילים עם אותו מפתח נכנסות לאותה קבוצה.
    3. שומרים את הקבוצות ב-Hashtable לפי המפתח.
    4. בסוף מחזירים את כל הקבוצות שנוצרו.
  2. ליטקוד 98 - אימות עץ חיפוש בינארי
    מקבלים עץ בינארי, וצריך לבדוק אם הוא באמת עץ חיפוש בינארי. זה לא מספיק שכל צומת יהיה גדול מהילד השמאלי וקטן מהילד הימני שלו; כל תת-העץ השמאלי חייב להיות קטן ממנו, וכל תת-העץ הימני חייב להיות גדול ממנו.
    הצג תשובה

    הפאטרן המועדף פה: חוק של מבנה נתונים עם חיפוש לעומק.

    1. מעבירים לכל צומת גבול תחתון וגבול עליון שמותר לו להיות בתוכם.
    2. במעבר שמאלה מעדכנים את הגבול העליון.
    3. במעבר ימינה מעדכנים את הגבול התחתון.
    4. אם צומת יוצא מהגבולות שלו, העץ לא תקין.

קשה

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

    הפאטרן המועדף פה: חיפוש לעומק עם מצבי ביקור.

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

    הפאטרן המועדף פה: Hashtable עם רשימה מקושרת כפולה.

    1. ה-Hashtable נותן גישה מהירה לפי מפתח.
    2. הרשימה המקושרת שומרת את סדר השימוש.
    3. בכל גישה מזיזים פריט קדימה, וכשאין מקום מוחקים מהסוף.

תרגול אמיתי

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

חימום קצר

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

    הפאטרן המועדף פה: שני פויינטרים.

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

    הפאטרן המועדף פה: שני פויינטרים.

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

    הפאטרן המועדף פה: שני פויינטרים באותו כיוון.

    1. פויינטר אחד קורא את המערך, ופויינטר שני מסמן איפה צריך לשים את המספר הלא-אפס הבא.
    2. בתכלס אנחנו מפרידים בין "איפה אני מסתכל" לבין "איפה המקום התקין הבא".
  4. ליטקוד 643 - ממוצע מקסימלי של תת-מערך
    מקבלים מערך ומספר K, וצריך למצוא את הממוצע הגבוה ביותר של רצף באורך K.
    הצג תשובה

    הפאטרן המועדף פה: חלון זז קבוע.

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

    הפאטרן המועדף פה: חלון זז משתנה.

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

    הפאטרן המועדף פה: חלון זז משתנה.

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

    הפאטרן המועדף פה: חיפוש בינארי.

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

    הפאטרן המועדף פה: חיפוש בינארי על גבול.

    1. עושים חיפוש אחד לגבול השמאלי וחיפוש אחד לגבול הימני.
    2. זה לא "מצאתי ערך וסיימתי"; מחפשים את המקום הראשון שבו הערך מתחיל ואת המקום האחרון שבו הוא עדיין קיים.
  9. ליטקוד 1011 - קיבולת ספינה לשליחת חבילות
    מקבלים משקלי חבילות ומספר ימים. החבילות נשלחות לפי הסדר, וכל יום אפשר להעמיס עד קיבולת מסוימת. צריך למצוא את הקיבולת המינימלית שמספיקה לשלוח הכל בזמן.
    הצג תשובה

    הפאטרן המועדף פה: חיפוש בינארי על תשובה.

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

    למשל, במשקלים [3, 2, 2, 4, 1, 4] וב-3 ימים, קיבולת 5 דורשת 4 ימים, אבל קיבולת 6 מסדרת את זה ככה: [3, 2], [2, 4], [1, 4].

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

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

    הפאטרן המועדף פה: חיפוש לרוחב.

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

כבר צריך לחשוב

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

    הפאטרן המועדף פה: חיפוש לרוחב מכמה מקורות.

    1. מכניסים לתור את כל התפוזים הרקובים כבר בהתחלה.
    2. כל שכבה בתור היא דקה שעברה.
    3. זה חשוב כי ההדבקה לא יוצאת ממקום אחד, אלא מכמה מקומות במקביל.
  2. ליטקוד 102 - מעבר בעץ לפי רמות
    מקבלים עץ בינארי, וצריך להחזיר את הערכים שלו לפי שכבות: קודם השורש, אחר כך הילדים שלו, אחר כך הנכדים, וכן הלאה.
    הצג תשובה

    הפאטרן המועדף פה: חיפוש לרוחב.

    1. התור שומר לנו יפה את הסדר של רמה אחרי רמה.
    2. אפשר לעשות חיפוש לעומק עם עומק ולבנות רשימות לפי עומק, אבל אם השאלה עצמה אומרת "רמות", חיפוש לרוחב הוא הפתרון הכי ישר.
  3. ליטקוד 200 - מספר איים
    מקבלים גריד של מים ואדמה. אי הוא קבוצת תאי אדמה שמחוברים אחד לשני למעלה, למטה, ימינה או שמאלה. צריך לספור כמה איים נפרדים יש.
    הצג תשובה

    הפאטרן המועדף פה: חיפוש לעומק, ואפשר גם חיפוש לרוחב.

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

    הפאטרן המועדף פה: חיפוש לעומק עם סימון המסלול הנוכחי.

    1. ביקור רגיל לא מספיק. צומת שראינו בעבר לא אומר שהוא נמצא כרגע במסלול שלנו.
    2. אם חזרנו לצומת שנמצא במסלול הפעיל, מצאנו מעגל.
  5. ליטקוד 133 - שכפול גרף
    מקבלים צומת אחד מתוך גרף מחובר, וצריך ליצור עותק מלא של כל הגרף שאפשר להגיע אליו ממנו. כל צומת וכל חיבור צריכים להיות משוכפלים, בלי להשתמש בצמתים המקוריים.
    הצג תשובה

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

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

    הפאטרן המועדף פה: חזרה לאחור.

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

    הפאטרן המועדף פה: חזרה לאחור עם חיפוש לעומק.

    1. מנסים להתחיל מכל תא מתאים, מסמנים אותו כמשומש, הולכים לשכנים, ואז מבטלים סימון כשחוזרים.
    2. הביטול הוא מה שמונע מענף אחד להרוס את הבא אחריו.
  8. ליטקוד 51 - בעיית המלכות
    מקבלים גודל לוח שחמט, וצריך להחזיר את כל הדרכים לשים עליו מלכות כך שאף שתי מלכות לא נמצאות באותה שורה, עמודה או אלכסון.
    הצג תשובה

    הפאטרן המועדף פה: חזרה לאחור.

    1. שמים מלכה במקום חוקי, עוברים לשורה הבאה, ואם נתקעים - חוזרים ומנסים מקום אחר.
    2. הדרך הנKה היא לשמור אילו עמודות ואלכסונים כבר תפוסים.
  9. ליטקוד 703 - האיבר ה-K הכי גדול בזרם
    מקבלים זרם מספרים ומספר K, וצריך לדעת בכל שלב מהו האיבר ה-K הכי גדול.
    הצג תשובה

    הפאטרן המועדף פה: תור עדיפויות וערימה.

    1. שומרים ערימה קטנה בגודל K, לא את כל הזרם.
    2. ראש הערימה הוא הגבול שלנו. מי שמתחתיו לא מעניין כרגע.
  10. ליטקוד 23 - מיזוג K רשימות ממוינות
    מקבלים כמה רשימות מקושרות שכבר ממוינות, וצריך למזג אותן לרשימה אחת ממוינת. האתגר הוא לבחור בכל רגע את הראש הכי קטן מבין כל הרשימות.
    הצג תשובה

    הפאטרן המועדף פה: ערימה.

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

כמו בראיון

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

    הפאטרן המועדף פה: Hashtable וערימה.

    1. קודם עושים ספירת שכיחויות ב-Hashtable.
    2. אחר כך הערימה שומרת רק את K המועמדות שבאמת רלוונטיות.
    3. אם צריך סדר מדויק לפי שכיחות ואז מילון, צריך להגדיר את העדיפות בהתאם.
  2. ליטקוד 70 - טיפוס במדרגות
    מקבלים מספר מדרגות, ובכל פעם אפשר לעלות מדרגה אחת או שתיים. צריך לחשב בכמה דרכים שונות אפשר להגיע בדיוק למעלה.
    הצג תשובה

    הפאטרן המועדף פה: תכנון דינמי.

    1. למדרגה הנוכחית אפשר להגיע מאחת לפני או משתיים לפני, אז מחברים את שתי התשובות האלה.
    2. זה לא קסם. זו פשוט תשובה גדולה שנבנית מתשובות קטנות.
  3. ליטקוד 198 - שוד בתים
    מקבלים שורת בתים עם סכום כסף בכל בית, ואסור לבחור שני בתים צמודים. צריך למצוא את הסכום המקסימלי שאפשר לקחת.
    הצג תשובה

    הפאטרן המועדף פה: תכנון דינמי.

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

    הפאטרן המועדף פה: תכנון דינמי דו-ממדי.

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

    הפאטרן המועדף פה: שינוי חצים ברשימה מקושרת.

    1. שומרים את הבא, משנים את החץ של הנוכחי לקודם, ואז מתקדמים.
    2. מקרי קצה שצריך להגיד בקול: רשימה ריקה ורשימה עם צומת אחד.
  6. ליטקוד 19 - מחיקת צומת לפי מרחק מהסוף
    מקבלים רשימה מקושרת ומרחק מהסוף. אם המרחק הוא 2, למשל, צריך למחוק את הצומת השני מהסוף בלי להפוך את הרשימה.
    הצג תשובה

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

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

    הפאטרן המועדף פה: פויינטר מהיר ואיטי.

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

    הפאטרן המועדף פה: בחירת מבני נתונים והבנת מחירים.

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

    הפאטרן המועדף פה: בחירת מבני נתונים והבנת מחירים.

    1. מסבירים שיש פונקציית גיבוב שממפה מפתח לאינדקס, אבל כמה מפתחות יכולים להגיע לאותו מקום.
    2. פתרונות קלאסיים הם שרשור או חיפוש מקום פנוי בתוך הטבלה.
    3. זמן קבוע הוא ממוצע יפה, לא הבטחה מהשמיים.
  10. ליטקוד 98 - אימות עץ חיפוש בינארי
    מקבלים עץ בינארי, וצריך לבדוק אם הוא באמת עץ חיפוש בינארי תקין. כל הערכים בצד שמאל של צומת צריכים להיות קטנים ממנו, וכל הערכים בצד ימין צריכים להיות גדולים ממנו.
    הצג תשובה

    הפאטרן המועדף פה: חוק של מבנה נתונים עם חיפוש לעומק.

    1. הדרך הכי נKה היא להעביר לכל צומת גבול מינימום ומקסימום שמותר לו להיות בתוכם.
    2. גישה נוספת היא מעבר לפי סדר פנימי ולבדוק שהערכים עולים, אבל גבולות מינימום ומקסימום מסבירים טוב יותר את החוק של כל תת-עץ.

רגע לפני ראיון

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

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

אין תגובות

"הבעיה הגדולה ביותר בתקשורת היא האשליה שהיא התקיימה" - ג'ורג' ברנרד שו.

הירשם ל- רשומות (Atom)