Stacks & Queues - Monotonic Stack, BFS
ראיון ב-Wix, 2023. שאלה: "Given a list of temperatures, find for each day how many days until a warmer temperature." מועמד ישב 20 דקות, כתב שתי לולאות מקוננות O(n^2). מועמד שני כתב 10 שורות עם Monotonic Stack ב-O(n). ההבדל: Pattern שנקרא Monotonic Stack - אחד ה-Patterns הפחות מוכרים, אבל שמשנה חלק ניכר מבעיות "מצא את ה-next greater element".
Stack ו-Queue נראים כמו Patterns "בסיסיים". ב-FAANG, "בסיסי" לא אומר שלא שואלים - אומר שמצפים שתדעו אותם לגמרי ותתמקדו ב-Patterns מתקדמים כמו Monotonic Stack ו-Multi-source BFS. בישראל, ב-Monday ו-Check Point, Stack ו-Queue מופיעים כחלק מבעיות Simulation - שם הביצוע הנקי חשוב לא פחות מהBig-O.
Stacks ו-Queues נראים בסיסיים, אבל הם הבסיס לפתרונות מתקדמים: BFS, Topological Sort, כל שאלות הסוגריים, ו-Monotonic Stack. מי שמכיר אותם לעומק מזהה מיד כשהם מתאימים.