בצע את הצעדים הבאים כדי לפתור כל בעיה בראיון לתכנות דינמי

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

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

תכנות דינמי - צפוי וניתן להכנה

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

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

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

7 שלבים לפתרון בעיית תכנות דינמית

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

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

דוגמא לבעיית DP

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

הצהרת בעיה:

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

להלן כללים:

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

ייצוג מערך לדוגמא:

2) קיבלת מהירות התחלה S. S הוא מספר שלם לא שלילי בכל נקודה נתונה, והוא מציין כמה תתקדם בקפיצה הבאה.

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

4) אתה רוצה לעצור בבטחה בכל מקום לאורך המסלול (לא צריך להיות בסוף המערך). אתה עוצר כאשר המהירות שלך הופכת ל 0. עם זאת, אם אתה נוחת על ספייק בשלב כלשהו, ​​הכדור המקפיץ המטורף שלך מתפרץ וזה נגמר.

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

שלב 1: כיצד לזהות בעיית תכנות דינמית

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

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

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

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

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

שלב 2: זיהוי משתני בעיה

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

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

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

בדוגמה שלנו, שני הפרמטרים שיכולים להשתנות עבור כל תת-בעיה הם:

1. עמדת מערך (P)
2. מהירות (S)

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

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

זהה את הפרמטרים המשתנים וקבע את מספר בעיות המשנה.

שלב 3: ביטוי ברור של יחס ההישנות

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

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

כך אנו חושבים על כך בבעיית המדגם שלנו:

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

באופן רשמי יותר, אם המהירות שלנו היא S, עמדה P, נוכל לעבור מ (S, P) ל:

1. (S, P + S) ; # אם לא נשנה את המהירות
2. (S - 1, P + S - 1) ; # אם נשנה את המהירות ב- -1
3. (S + 1, P + S + 1) ; # אם נשנה את המהירות ב- +1

אם אנו יכולים למצוא דרך לעצור בכל אחת מתתי בעיות המשנה לעיל, נוכל לעצור מ- (S, P). הסיבה לכך היא שאנחנו יכולים לעבור מ- (S, P) לכל אחת משלוש האפשרויות שלעיל.

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

canStop (S, P) = canStop (S, P + S) || canStop (S - 1, P + S - 1) || canStop (S + 1, P + S + 1)

וואו, נראה שיש לנו את יחס ההישנות שלנו!

יחס הישנות: בהנחה שחישבת את בעיות המשנה, כיצד תחשב את הבעיה העיקרית?

שלב 4: זיהוי מקרי הבסיס

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

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

בבעיית הדוגמה שלנו, יש לנו שני פרמטרים משתנים, S ו- P. בואו נחשוב אילו ערכים אפשריים של S ו- P אינם חוקיים:

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

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

בדוגמה שלנו:

1. P <0 || P> = אורך המסלול נראה כמו הדבר הנכון לעשות. אלטרנטיבה יכולה להיות לשקול איסוף P == קצה המסלול מקרה בסיס. עם זאת, יתכן כי בעיה מתפצלת לבעיית משנה החורגת מסוף המסלול, כך שאנו באמת צריכים לבדוק אי שוויון.
2. זה נראה די ברור. אנחנו יכולים פשוט לבדוק אם המסלול [P] אינו נכון .
3. בדומה למס '1, נוכל פשוט לבדוק אם S <0 ו- S == 0. עם זאת, כאן אנו יכולים לנמק שאי אפשר ש- S תהיה <0 מכיוון ש- S יורדת לכל היותר ב -1, ולכן יהיה עליה לעבור מקרה S == 0 מראש. Ther efore S == 0 הוא מקרה בסיס מספיק עבור הפרמטר S.

שלב 5: החלט אם ברצונך ליישם זאת באופן איטרטיבי או רקורסיבי

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

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

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

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

פתרון רקורסיבי: (קטעי קוד מקוריים ניתן למצוא כאן)

פתרון איטרטיבי: (קטעי קוד מקוריים ניתן למצוא כאן)

שלב 6: הוסף תזכורת

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

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

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

פירוש הדבר שעליך:

1. אחסן את תוצאת הפונקציה שלך בזיכרון לפני כל הצהרה חוזרת
2. חפש בזיכרון את תוצאת הפונקציה לפני שתתחיל לבצע חישוב אחר

הנה הקוד מלמעלה עם תוספת תזכורת (שורות שנוספו מודגשות): (קטעי קוד מקוריים ניתן למצוא כאן)

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

1. יצרתי מסלול באורך 1000 עם קוצים במקומות אקראיים (בחרתי שההסתברות של ספייק יהיה בכל נקודה נתונה תהיה 20%)
2. initSpeed ​​= 30
3. ניהלתי את כל הפונקציות 10 פעמים ומדדתי את זמן הביצוע הממוצע

להלן התוצאות (בשניות):

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

שלב 7: קביעת מורכבות הזמן

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

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

בבעיית הדוגמה שלנו, מספר המצבים הוא | P | * | S |, איפה

• P הוא קבוצת כל המיקומים (| P | מציין את מספר האלמנטים ב- P)
• S הוא הסט של כל המהירויות

העבודה שנעשתה בכל מדינה היא O (1) בבעיה זו מכיוון שלאור כל שאר המדינות, עלינו פשוט להסתכל על 3 בעיות משנה כדי לקבוע את המצב שנוצר.

כפי שציינו בקוד קודם, | S | מוגבל על ידי אורך המסלול (| P |), ולכן נוכל לומר שמספר המדינות הוא | P | ² ומכיוון שהעבודה שנעשתה בכל מדינה היא O (1), אז מורכבות הזמן הכוללת היא O (| P | ²).

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

אז בואו נראה כיצד נוכל לשים הדוק יותר על | S |. בואו נקרא למהירות מקסימלית S. נניח שאנחנו מתחילים ממצב 0. כמה מהר היינו יכולים לעצור אם ניסינו לעצור כמה שיותר מהר ואם נתעלם מקוצים פוטנציאליים?

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

למסלול באורך L צריך להחזיק את הדברים הבאים:

=> (S-1) + (S-2) + (S-3) + .... + 1 <L

=> S * (S-1) / 2 <L.

=> S² - S - 2L <0

אם אתה מוצא שורשים של הפונקציה הנ"ל, הם יהיו:

r1 = 1/2 + sqrt (1/4 + 2L) ו- r2 = 1/2 - sqrt (1/4 + 2L)

אנו יכולים לכתוב את אי השוויון שלנו כ:

(S - r1) * (S - r2) < ; 0

בהתחשב בכך ש- r2> 0 לכל S> 0 ו- L> 0, אנו צריכים את הדברים הבאים:

S - 1/2 - sqrt (1/4 + 2L) < ; 0

=> S <1/2 + sqrt (1/4 + 2L)

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

כלומר מורכבות הזמן הכוללת תלויה רק ​​באורך מסלול ההמראה L בצורה הבאה:

O (L * sqrt (L)) שהוא טוב יותר מ- O (L²)

O (L * sqrt (L)) הוא הגבול העליון במורכבות הזמן

מדהים, עשית את זה! :)

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

להלן מספר הצעדים הבאים שתוכל לבצע

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

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

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