[Powered by Google Translate] [סמינר: ראיונות טכניים] [הקנים יו, אוניברסיטת הרווארד] [זה CS50.] [CS50.TV] שלום לכולם, אני קנים. אני כרגע לומדים מדעי מחשב זוטרים. אני CS TF לשעבר, ולוואי שהיה זה כשהייתי underclassman, ובגלל זה אני נותן את הסמינר הזה. אז אני מקווה שאתה נהנה מזה. סמינר זה הוא על ראיונות טכניים, ואת כל המשאבים שלי ניתן למצוא בקישור הזה, קישור זה ממש כאן, כמה משאבים. אז עשתה רשימה של בעיות, למעשה, לא מעט בעיות. גם דף משאבים כללי שבו אנחנו יכולים למצוא טיפים כיצד להתכונן לראיון, טיפים על מה שאתה צריך לעשות במהלך ראיון בפועל, כמו גם איך לגשת לבעיות ומשאבים לשימוש עתידי. כל זה באינטרנט. ורק כדי להקדים סמינר זה, ויתור, ככה לא צריך - הכנת הראיון לא צריך להיות מוגבל לרשימה זו. זה אמור להיות מדריך, ואתה בהחלט צריך לקחת את כל מה שאני אומר בערבון מוגבל, אלא גם להשתמש בכל מה שהייתי עוזר לך בהכנת הראיון. 

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

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

אז בואו לצלול לתוך הבעיה הראשונה שלנו. "בהינתן מערך של מספרים שלמים n, לכתוב פונקציה המשתרכת המערך במקום כזה שכל התמורות של המספרים השלמים n סבירות באותה מידה. " ואניח שיש לך זמין במחולל מספר שלם אקראי שיוצר שלם בטווח שבין 0 ל i, מגוון חצי. האם כולם מבינים את השאלה הזאת? אני נותן לך מערך של מספרים שלמים n, ואני רוצה שזה דשדוש. בספרייה שלי, כתבתי לו כמה תוכניות שממחישות למה אני מתכוון. אני הולך לדשדוש מערך של 20 אלמנטים, מ-10 ל9, ואני רוצה שפלט רשימה כזאת. אז זה מערך הקלט מסודר שלי, ואני רוצה שזה דשדוש. אנחנו נעשה את זה שוב. האם כולם הבינו את השאלה? אוקיי. אז זה תלוי בך. מה הם כמה רעיונות? האם אתה יכול לעשות את זה כמו n ^ 2, n log n, n? פתוח להצעות. אוקיי. אז רעיון אחד, שהוצע על ידי אמי, הוא לחשב מספר אקראי, מספר שלם אקראי, בטווח הראשון 0-20. אז תניח המערך שלנו יש לו אורך של 20. בדיאגרמה של 20 אלמנטים שלנו, זה מערך הקלט שלנו. ועכשיו, הצעתה היא ליצור מערך חדש, אז זה יהיה מערך הפלט. ומבוסס על חזרתי ברנד - אז אם אני היה, אניח, 17, להעתיק את האלמנט 17 למקום הראשון. עכשיו אנחנו צריכים למחוק - אנו צריכים לשנות את כל האלמנטים כאן על כך שיש לנו פער בסוף ואין חורים באמצע. ועכשיו אנחנו חוזרים על התהליך. עכשיו אנחנו בוחרים מספר שלם אקראי חדש בין 0 ל 19. יש לנו אני חדש כאן, ואנחנו נעתיק את האלמנט הזה לעמדה זו. אז אנחנו מעבירים פריטים שוב ואנו חוזרים על התהליך עד שיש לנו המערך החדש המלא שלנו. מהו זמן הריצה של אלגוריתם זה? ובכן, הבה נבחן את ההשפעה של זה. אנחנו מעבירים לכל אלמנט. כאשר אנחנו מפנים את זה אני, אנחנו מעבירים את כל האלמנטים לאחר אותו לשמאל. וזה עלות O (n) כי מה אם תסירו את האלמנט הראשון? אז לכל סרה, אנו מסירים - כל סרה כרוכה פעולת O (n), ומאז יש לנו n הסרות, זה מוביל לדשדוש O (n ^ 2). אוקיי. אז התחלה טובה. התחלה טובה. 

הצעה נוספת היא להשתמש במשהו המכונה דשדוש הקנוט, או דשדוש הפישר ייטס. וזה בעצם דשדוש זמן ליניארי. והרעיון הוא מאוד דומה. שוב, יש לנו מערך הקלט שלנו, במקום להשתמש בשני מערכי הקלט / הפלט שלנו, אבל, אנו משתמשים בחלק הראשון של המערך כדי לעקוב אחר טרף החלק שלנו, ואנו עוקבים אחר, ואז להשאיר את שאר המערך שלנו לחלק unshuffled. אז הנה מה שאני מתכוון. אנחנו מתחילים עם - אנחנו בוחרים אני, מערך 0-20. המצביע הנוכחי שלנו מצביע על המדד הראשון. אנחנו בוחרים כמה אני כאן ועכשיו אנחנו מחליפים. אז אם זה היה 5 וזה היה 4, מערך התוצאה יהיה 5 כאן וכאן 4. ועכשיו אנחנו מציינים סמן כאן. הכל לשמאל דשדש, והכל לזכותו unshuffled. ועכשיו אנחנו יכולים לחזור על התהליך. אנחנו בוחרים ראשים אקראיים בין 1 ל 20 עכשיו. אז תניח החדש שלנו אני נמצא כאן. עכשיו אנחנו מחליפים לי את זה עם המיקום החדש הנוכחי שלנו כאן. אז אנחנו מחליפים הלוך ושוב כמו זה. בואו תביאו אותי את הקוד כדי לעשות את זה יותר קונקרטי. אנחנו מתחילים עם הבחירה שלי שלנו - אנחנו מתחילים עם אני שווה 0, אנחנו בוחרים j מיקום אקראי בחלק unshuffled של המערך, אני עד n-1. אז אם אני כבר כאן, בוחר ראשים אקראיים בין כאן והשאר במערך, ואנחנו מחליפים. זה כל הקוד הדרוש לדשדוש המערך שלך. יש שאלות? 

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

, כל הבעיה הבאה הנכונה. אז "נתון מערך של מספרים שלמים, postive, אפס, שלילי לכתוב פונקציה שמחשבה את הסכום המרבי כל subarray continueous של מערך הקלט. " דוגמה כאן היא, במקרה שבו כל המספרים הם חיוביים, אז כרגע הבחירה הטובה ביותר היא לקחת את כל המערך. 1, 2, 3, 4, שווה 10. כאשר יש לך כמה מילות מפתח שלילי לשם, במקרה הזה אנחנו רק רוצים את שני הראשונים בגלל בחירת -1 ו / או -3 תביא הסכום שלנו למטה. לפעמים אנו יכולים להתחיל באמצע של המערך. לפעמים אנחנו רוצים לבחור שום דבר, זה הכי טוב לא לקחת שום דבר. ולפעמים זה טוב יותר לקחת את הנפילה, כי הדבר אחרי הוא סופר גדול. אז כל רעיונות? (סטודנט, לא ברור) >> כן. אניח שאני לא לוקח -1. אז או שאני בוחר ו1000 20000, או פשוט לבחור 3 מליארד דולרים. ובכן, הבחירה הטובה ביותר היא לקחת את כל המספרים. זה -1, למרות היותו שלילי, כל הסכום הוא טוב יותר מאשר היו לי לא לקחת -1. אז אחת העצות שהזכרתי קודם לכן היה להגדיר בבירור את המובן מאליו ופתרון בכוח הזרוע הראשונה. מה הפתרון בכוח הזרוע בבעיה זו? כן? [ג'יין] ובכן, אני חושב שהפתרון בכוח הזרוע יהיה לסכם את כל הצירופים האפשריים (לא ברור). [יו] אוקיי. אז הרעיון של ג'יין הוא לקחת את כל האפשר - אני פרפרזה - הוא לקחת את כל subarray רציף אפשרי, חישוב הסכום שלו, ולאחר מכן לקחת את המקסימום של כל subarrays הרציף האפשרי. מה מזהה באופן ייחודי subarray במערך הקלט שלי? כאילו, מה שני דברים שאני צריך? כן? (סטודנט, לא ברור) ימני. >> חסם תחתון על המדד ומדד גבול עליון ייחודיים קובע subarray רציף. [סטודנטית] האם אנחנו מעריכים שזה מערך של מספרים ייחודיים? [יו] מס אז השאלה שלה, אנחנו בהנחת המערך שלנו - הוא המערך שלנו כל המספרים הייחודיים, והתשובה היא לא. 

אם אנו משתמשים בפתרון שלנו הזרוע בכח, ולאחר מכן את מדדי ההתחלה / סיום ייחודי קובע subarray המתמשך שלנו. אז אם אנחנו לחזר עבור כל ערכי ההתחלה האפשריים, ועבור כל ערכי הקצה> או = כדי להתחיל, ו< n, לחשבך את הסכום, ולאחר מכן אנחנו לוקחים את הסכום המקסימאלי שראינו עד כה. זה ברור? מה הוא הגדול O של פתרון זה? Timewise. לא n ^ 2 די. שים לב שנעמיק בין 0 ל n, אז זה אחד ללולאה. אנחנו נחזור שוב כמעט מההתחלה עד הסוף, אחרת ללולאה. ועכשיו, בתוך זה, אנחנו צריכים לסכם את כל כניסה, כך שעוד אחד ללולאה. אז יש לנו שלוש לקנן לולאות, n ^ 3. אוקיי. זה הולך כנקודת התחלה. הפתרון שלנו הוא לא יותר גרוע מn ^ 3. האם כולם מבינים את הפתרון בכוח הזרוע? 

אוקיי. פתרון טוב יותר הוא באמצעות מושג הנקרא תכנון דינמי. אם אתה לוקח CS124, שהוא אלגוריתמים ומבני נתונים, אתה תהיה מאוד מוכר בטכניקה זו. והרעיון הוא, נסה לבנות את הפתרונים לבעיות קטנות יותר קודם. מה שאני מתכוון זה, אנחנו כרגע צריכים לדאוג לשני דברים: התחלה וסיום. וזה מעצבן. מה אם היינו יכול להיפטר מאחד מהפרמטרים האלה? רעיון אחד הוא - אנחנו כבר קבלנו הבעיה המקורית שלנו, למצוא את הסכום המקסימאלי של כל subarray בטווח [O, n-1]. ועכשיו יש לנו subproblem חדש, שבו אנו יודעים, במדד הנוכחי שלנו אני, אנחנו יודעים שאנחנו חייבים להסיק שיש. subarray חייבת להסתיים במדד הנוכחי. כך שהבעיה שנותרה היא, שבו אנחנו צריכים להתחיל subarray? האם זה הגיוני? אוקיי. אז אני מקודד את זה, ובואו אסתכל על מה מדובר. בcodirectory, יש תכנית בשם subarray, וזה לוקח מספר הפריטים, וזה מחזיר את הסכום המקסימאלי ברשימת subarray דשדשה. אז במקרה הזה, subarray המקסימאלי שלנו הוא 3. וזה לקח רק על ידי שימוש 2 ו 1. בואו להפעיל אותו שוב. זה גם 3. אבל הפעם, שים לב איך הגיעו 3. לקחנו - אנחנו פשוט לקחת 3 עצמו כי זה מוקף בתשלילים בשני הצדדים, שיביא סכום <3. בואו לרוץ על 10 פריטים. הפעם זה 7, אנחנו לוקחים 3 מובילים ו4. הפעם זה 8, ונקבל שעל ידי לקיחת 1, 4 ו 3. אז לתת לך אינטואיציה על איך אנחנו יכולים לפתור את הבעיה הזו הפכה, בואו נסתכל subarray זה. אנחנו מקבלים מערך הקלט הזה, ואנחנו יודעים שהתשובה היא 8. אנחנו לוקחים את 1, 4, ו 3. אבל בואו נסתכל על איך אנחנו בעצם קבלנו את התשובה. בואו נסתכל על subarray המקסימאלי שהסתיים בכל אחד ממדדים אלו. מה subarray המקסימאלי שיש לסיים במקום הראשון? [סטודנטים] אפס. >> זירו. רק אל תיקחו -5. הנה זה הולך להיות 0 גם כן. כן? (סטודנט, לא ברור) [יו] אה, סליחה, זה -3. אז זה 2, זה -3. אוקיי. אז -4, מה subarray המקסימאלי לסיום עמדה כי בי -4 הם ב? אפס. אחד? 1, 5, 8. עכשיו, אני חייב לסיים במיקום שבו -2 הם בבית. אז 6, 5, 7, והאחרון הם 4. ידיעה כי אלו הם הערכים שלי לבעיה הפכה בו אני חייב לסיים בכל אחד ממדדים אלה, אז התשובה הסופית שלי היא פשוט, לקחת תנופה לרוחב, ולקחת את המספר המקסימאלי. אז במקרה הזה זה 8. משמעות הדבר הוא כי subarray המקסימאלי מסתיים במדד זה, והתחיל אי שם לפניו. האם כולם מבינים subarray שינה את זה? 

אוקיי. ובכן, בואו להבין את ההישנות לזה. הבה נבחן רק כמה הערכים הראשונים. אז הנה זה היה 0, 0, 0, 1, 5, 8. ואז היה -2 כאן, ושהביא אותו עד 6. אז אם אני קורא את הרשומה בעמדתי subproblem (ט), איך אני יכול להשתמש בתשובה לsubproblem הקודם כדי לענות subproblem זה? אם אני מסתכל על, אניח, ערך זה. איך אני יכול לחשב את התשובה 6 מלהסתכל שילוב של מערך זה ואת התשובות לsubproblems הקודם במערך הזה? כן? [תלמיד נקבה] אתה לוקח מערך של סכומים במצב נכון לפני זה, אז 8, ואז אתה מוסיף subproblem הנוכחי. [יו] אז הצעתה היא להסתכל על שני המספרים האלה, מספר זה ומספר זה. אז זה 8 מתייחס לתשובה לsubproblem (i - 1). ובואו נקראים א מערך הקלט שלי כדי למצוא subarray מקסימאלי שמסתיים בעמדתי, יש לי שתי אפשרויות: אני יכול להמשיך subarray שהסתיים במדד הקודם, או להתחיל מערך חדש. אם היינו ממשיך subarray שהחל במדד הקודם, אז הסכום המקסימאלי שאני יכול להשיג הוא התשובה לsubproblem הקודם בתוספת ערך המערך הנוכחי. אבל, יש לי גם את האפשרויות החל subarray חדש, ובמקרה זה הסכום הוא 0. אז התשובה היא מקסימום של 0, subproblem i - 1, בתוספת כניסת המערך הנוכחית. האם הישנות זה הגיוני? הישנות שלנו, כפי שאנו רק גילינו, היא subproblem שווה למקסימום של subproblem הקודם בתוספת כניסת המערך הנוכחית שלי, מה שאומר שימשיך subarray הקודם, או 0, להתחיל subarray חדש במדד הנוכחי שלי. וברגע שבנינו את הטבלה של פתרונות, אז התשובה הסופית שלנו, פשוט לעשות סריקה ליניארי על פני מערך subproblem ולקחת את המספר המקסימאלי. זהו יישום מדויק של מה שאמרתי עכשיו. אז אנחנו יוצרים מערך subproblem חדש, subproblems. הכניסה הראשונה היא 0 או הערך הראשון, למקסימום של שני אלה. ועבור שאר subproblems אנו משתמשים בהישנות המדויקת שרק התגליתי. כעת אנו מחשבים את המקסימום של מערך subproblems שלנו, וזו התשובה הסופית שלנו. 

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

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

בעיה בשוק מניות: "בהינתן מערך של מספרים שלמים n, חיוביים, אפס או שליליים, המייצג את המחיר של מנייה לאורך n ימים, לכתוב פונקציה כדי לחשב את הרווח המקסימאלי שאתה יכול לעשות בהתחשב בכך שאתה קונה ומוכר מניות בדיוק 1 בתוך n ימים אלה. " בעיקרו של דבר, אנחנו רוצים לקנות נמוכים, למכור גבוהים. ואנחנו רוצים להבין את הרווח הטוב ביותר שאנחנו יכולים לעשות. אם יחזרו לטיפ שלי, מה היא התשובה הברורה מייד, הפשוטה ביותר, אבל זה איטי? כן? (סטודנט, לא ברור) >> כן. >> אז היית פשוט ללכת על פי ומסתכל על מחירי המניות בכל נקודה בזמן, (לא ברור). [יו] אוקיי, אז הפתרון שלה - הצעתה של מחשוב הנמוך ביותר והגבוה ביותר שחישוב לא בהכרח עובד בגלל הגבוה ביותר עלול להתרחש לפני הנמוך ביותר. אז מה הוא הפתרון הכוחני לבעיה זו? מה הם שני דברים שאני צריך באופן ייחודי כדי לקבוע את הרווח אני עושה? נכון. הפתרון הוא בכוח הזרוע - הו, כן, הצעתו של ג'ורג' היא שאנחנו רק צריכים ימים באופן ייחודי כדי לקבוע את הרווח של הימים האלה. אז לחשב כל זוג, רוצה לקנות / למכור, לחשב את הרווח, אשר יכול להיות חיוביים או שלילי או אפס. לחשב את הרווח המקסימאלי שאנחנו עושים אחרי iterating על כל הזוגות של ימים. זו תהיה התשובה הסופית שלנו. ופתרון שיהיה O (n ^ 2), כי יש n לבחור שני זוגות - בימים שאתה יכול לבחור בין ימי קצה. אוקיי, אז אני לא הולך לעבור על הפתרון בכוח הזרוע כאן. אני הולך לספר לך שיש פתרון n log n. מה עושה כיום אלגוריתם אתה יודע שזה n log n? זה לא שאלה מכשילה. 

מיזוג כזה. סוג המיזוג הוא n log n, ולמעשה, דרך אחת לפתור את הבעיה הזו היא להשתמש סוג מעין מיזוג של רעיון שנקרא, באופן כללי, פרד ומשול. והרעיון הוא כדלקמן. אתה רוצה לחשב את הכי הטוב לקנות / למכור צמד במחצית השמאלית. מצא את הרווח הטוב ביותר שאתה יכול לעשות, רק עם n 1 במשך ימים. אז אתה רוצה oompute הכי הטוב לקנות / למכור זוג במחצית הימנית, כך n האחרון במשך ימים. ועכשיו השאלה היא, איך אנחנו למזג את הפתרונים הללו שוב ביחד? כן? (סטודנט, לא ברור) >> אוקיי. אז נתת לי לצייר תמונה. כן? (ג'ורג', לא ברור) >> בדיוק. פתרונו של ג'ורג' הוא בדיוק נכון. אז הצעתו היא, לחשב את צמד הקנייה / מכירה הכי הטוב ראשון, וזה מתרחש במחצית השמאלית, אז בואו נקראים שלשמאל, משמאל. הכי הטוב לקנות / למכור זוג המתרחש במחצית הימנית. אבל אם בהשוואת שני מספרים אלה בלבד, שאנחנו חסרי המקרה איפה שאנחנו קונים כאן ולמכור מתישהו במחצית הימנית. אנחנו קונים במחצית השמאלית, למכור במחצית הימנית. והדרך הטובה ביותר כדי לחשב את צמד הקנייה / מכירה הטוב ביותר החובק שני חצאים הוא לחשב את המינימום כאן ולחשב את המקסימום כאן ולקחת את ההבדל ביניהם. אז שני המקרים בם זוג הקנייה / מכירה קורה רק כאן, רק כאן, או בשני חצאים מוגדר על ידי שלושה המספרים האלה. אז האלגוריתם שלנו למזג את הפתרונים שלנו נחזור להיות ביחד, אנחנו רוצים לחשב את זוג הקנייה / מכירה הטוב ביותר איפה שאנחנו קונים בחלק השמאלי ולמכור במחצית הימנית. והדרך הטובה ביותר לעשות זאת היא לחשב את המחיר הנמוך ביותר במחצית הראשונה, את המחיר הגבוה ביותר במחצית הימנית, ולקחת את ההבדל ביניהם. השלושה הרווחים כתוצאה, השלושה המספרים האלה, אתה לוקח את המקסימום של שלושה, וזה הרווח הטוב ביותר שתוכל לעשות על הימים הראשונים וסופו של דבר אלה. הנה הקווים החשובים הם בצבע אדום. זוהי קריאה רקורסיבית כדי לחשב את התשובה בצד השמאל. זוהי קריאה רקורסיבית כדי לחשב את התשובה במחצית הימנית. שני אלה ללולאות לחשב את הדקות ואת המקסימום בחלק השמאלי וימני, בהתאמה. עכשיו אני מחשב את הרווח שמשתרע על פני שני החצאים, והתשובה הסופית היא מרבית של שלושה אלה. אוקיי. 

אז בטח, יש לנו אלגוריתם, אבל השאלה הגדולה היא, מה היא את המורכבות של הזמן זה? והסיבה שהזכרתי סוג המיזוג היא כי צורה זו של לחלק את התשובה לשתיים ולאחר מכן ממזג את הפתרונים שלנו שוב ביחד זה בדיוק הסוג של מיון מיזוג. אז תן לי ללכת דרך המשך. אם הגדרנו פונקציה t (n) להיות מספר הצעדים עבור n ימים, שתי שיחות רקורסיבית כל אחד מהם יעלה t (n / 2), ויש שתיים מהשיחות הללו. עכשיו אני צריך לחשב את המינימום של המחצית השמאלית, שאני יכול לעשות בn / 2 שעה, בתוספת המרבית של מחצית ימין. אז זה פשוט n. ואז בתוספת קצת עבודה קבועה. ומשוואה זו הישנות היא בדיוק משוואת ההישנות לסוג המיזוג. וכולנו יודעים שמיון המיזוג הוא log n זמן n. לכן, האלגוריתם שלנו הוא גם n log n זמן. האם איטרציה זה הגיוני? רק סיכום קצר של זה: T (n) הוא מספר הצעדים על מנת לחשב את הרווח המקסימאלי במשך n ימים. הדרך שנפרדנו השיחות רקורסיבית הוא על ידי קריאת הפתרון שלנו בימי n / 2 1, אז זה שיחת טלפון אחת, ואז אנו קוראים שוב למחצית השנייה. אז זה שתי שיחות. ואז אנחנו מוצאים את מינימום בחלק השמאלי, שאנחנו יכולים לעשות בזמן ליניארי, למצוא את המקסימום של מחצית ימין, שאנחנו יכולים לעשות בזמן ליניארי. אז n / 2 + n / 2 היא רק n. אז יש לנו קצת עבודה קבועה, שזה כמו לעשות את החישובים. משוואת הישנות זה בדיוק משוואת ההישנות לסוג המיזוג. לפיכך, אלגוריתם הדשדוש שלנו הוא גם n log n. אז כמה מקום אנחנו משתמשים? בואו נחזור לקוד. 

שאלה טובה יותר היא, כמה פריימי מחסנית אנחנו אי פעם יש בכל רגע נתון? מכיוון שאנו משתמשים ברקורסיה, מספר מסגרות מחסנית קובע השימוש בשטח שלנו. הבה נבחן n = 8. אנו קוראים לדשדוש ב8, שייקרא דשדוש בארבעת הערכים הראשונים, שייקרא דשדוש בשני הערכים הראשונים. אז המחסנית שלנו היא - זה המחסנית שלנו. ואז אנחנו קוראים דשדוש שוב על 1, וזה מה שהמקרה שלנו הוא הבסיס, ואנחנו חוזרים באופן מיידי. האם אי פעם יש לנו יותר ממסגרות מחסנית זה הרבה? לא, כי בכל פעם שאנחנו עושים תפילה, קריאה רקורסיבית לדשדוש, אנו מחלקים הגודל שלנו במחצית. אז את המספר המרבי של מסגרות מחסנית להיות לנו בכל רגע נתון הוא בסדר גודל של מסגרות יומן n מחסנית. כל מסגרת מחסנית יש מקום קבוע, ולכן הסכום הכולל של החלל, הכמות המרבית של שטח אנחנו משתמשים לפעמים היא מקום O (logn) כאשר n הוא מספר הימים. 

עכשיו, תמיד תשאל את עצמך, "אנחנו יכולים לעשות טובים יותר?" ובפרט, אנו יכולים לצמצם את זה לבעיה שכבר פתרו? רמז: אנחנו רק דנו בשתי בעיות אחרות לפני זה, וזה לא הולך להיות דשדוש. אנחנו יכולים להמיר בעיה זו לשוק מניות בעית subarray המקסימלי. איך אנחנו יכולים לעשות את זה? אחד מכם? אמי? (אמי, לא ברור) [יו] בדיוק. אז בעית subarray המקסימלי, אנחנו מחפשים סכום מעל subarray רציף. והצעתו של האמי על בעית המניות, תשקלו את השינויים, או deltas. ותמונה של זה - זה המחיר של מניות, אבל אם תיקח את ההבדל בין כל יום ברציפות - כך אנו רואים כי המחיר המרבי, רווח מקסימאלי שאנחנו יכולים לעשות הוא אם לקנות כאן ולמכור כאן. אבל בואו נסתכל מתמשך - בואו נסתכל על בעית subarray. אז הנה, אנחנו יכולים לעשות - ללכת מכאן לכאן, יש לנו שינוי חיובי, ואז הולך מכאן לכאן יש לנו שינוי שלילי. אבל אז, עוברים מכאן לכאן יש לנו שינוי חיובי עצום. ואלה הם שינויים שאנחנו רוצים לסכם כדי לקבל הרווח הסופי שלנו. אז יש לנו שינויים שליליים יותר כאן. המפתח לצמצום בעית המניות שלנו לבעית subarray המקסימלי שלנו הוא לשקול את הדלתא בין ימים. אז אנחנו יוצרים מערך חדש בשם דלתא, לאתחל את הכניסה הראשונה להיות 0, ולאחר מכן עבור כל דלתא (אני), לתת לזה להיות ההבדל המערך שלי הקלט (אני), והמערך (i - 1). אז אנחנו קוראים ההליך השגרתי שלנו לsubarray מקסימאלי עובר במערך של דלתא. ובגלל subarray המקסימאלי של הזמן ליניארי וירידה זו, תהליך זה של יצירת מערך דלתא זה, גם זמן ליניארי, אז הפתרון הסופי עבור מניות הוא עבודת עבודת O (n) בתוספת של O (n), הוא עדיין העבודה של O (n). אז יש לנו פתרון לבעיה של זמן ליניארי שלנו. האם כולם מבינים את השינוי הזה? 

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