Sliding Window Pattern
ראיון ב-Meta TLV, 2022. שאלה: "Given a string s and a string p, find all starting indices of p's anagrams in s." מועמד עם Brute Force: O(n * m * m) - בדיקת כל substring ומיון. מועמד עם Sliding Window: O(n + m) - חלון שנע על s עם Frequency Counter. מי עבר? ברור.
Sliding Window הוא Pattern שנראה "קסמי" בפעם הראשונה - איך עוברים מ-O(n*k) ל-O(n)? התשובה פשוטה: אנחנו לא מחשבים מחדש. אנחנו מעדכנים. זה ה-Insight שצריך לדעת לנסח בראיון כשנשאלים "למה זה O(n)?". לא "כי הקוד נראה כך" - אלא "כי כל אלמנט נכנס לחלון ויוצא ממנו בדיוק פעם אחת."
Sliding Window הוא ה-Pattern שהופך "כל תת-מערך/substring" מ-O(n^2) ל-O(n). הרעיון: במקום לחשב מחדש את כל מה שבתוך החלון בכל צעד, אנחנו מוסיפים איבר חדש מהימין ומורידים איבר ישן מהשמאל. O(1) לכל צעד.