[Powered by Google Translate] [სემინარი: ტექნიკური ინტერვიუები] [Kenny Yu, ჰარვარდის უნივერსიტეტი] [ეს არის CS50.] [CS50.TV] Hi ყველას, მე Kenny. მე გაკეთებული უმცროსი შესწავლას კომპიუტერულ მეცნიერებათა. მე ყოფილი CS TF, და მინდა მე მქონდა ამ როდესაც მე underclassman, და ამიტომაც მე ვაძლევთ ამ სემინარს. ამიტომ ვიმედოვნებ, რომ სარგებლობენ, ეს. ეს სემინარი ტექნიკურ ინტერვიუები, და ყველა ჩემი რესურსების შეგიძლიათ იხილოთ ამ ბმულზე, ამ ლინკები უფლება აქ, რამდენიმე რესურსი. ამიტომ მე მივიღე ჩამონათვალი პრობლემები, ფაქტობრივად, ძალიან ცოტა პრობლემები. ასევე ზოგადად რესურსების გვერდზე, სადაც შეგვიძლია მოვძებნოთ რჩევები თუ როგორ უნდა მოემზადოს ინტერვიუში, რჩევა, რაც თქვენ უნდა გავაკეთოთ დროს ფაქტობრივი ინტერვიუში, ასევე, თუ როგორ უნდა მივუდგეთ პრობლემებს და რესურსების მომავალი მითითება. ეს ყველაფერი ონლაინ. და მხოლოდ იმიტომ, რომ შესავალში ამ სემინარზე, პასუხისმგებლობის, მოსწონს ეს არ უნდა - თქვენი ინტერვიუ მომზადება არ უნდა შემოიფარგლოს ამ სიაში. ეს მხოლოდ ნიშნავს, რომ სახელმძღვანელო, და თქვენ უნდა აუცილებლად მიიღოს ყველაფერი ვამბობ ერთად მარცვალი მარილი, არამედ გამოიყენოს ყველაფერი მე რომ დაგეხმაროთ თქვენი ინტერვიუს მომზადება. 

მე ვაპირებ დაჩქარდეს მეშვეობით მომდევნო რამდენიმე სლაიდები ამიტომ ჩვენ შეუძლია მიიღოს ფაქტობრივი შემთხვევაში კვლევები. სტრუქტურა ინტერვიუ პროგრამული საინჟინრო postion, ჩვეულებრივ ეს არის 30 დან 45 წუთი, მრავალჯერადი რაუნდები, დამოკიდებულია კომპანიის. ხშირად თქვენ უნდა კოდირების თეთრ დაფაზე. ამიტომ თეთრ დაფაზე მოსწონს, მაგრამ ხშირად მცირე მასშტაბით. თუ თქვენ მქონე სატელეფონო ინტერვიუში, თქვენ ალბათ გამოყენებით ან collabedit ან Google Doc ასე ხედავენ თქვენ ცხოვრობთ კოდირების ხოლო თქვენ ინტერვიუს სატელეფონო. ინტერვიუ თავისთავად ჩვეულებრივ 2 ან 3 პრობლემებს ტესტირების თქვენს კომპიუტერში მეცნიერების ცოდნა. იგი ჩვენ თითქმის აუცილებლად ჩავრთოთ კოდირების. სახის კითხვებით, რომ თქვენ ნახავთ ჩვეულებრივ მონაცემები სტრუქტურებისა და ალგორითმები. და აკეთებს ამ სახის პრობლემები, ისინი გთხოვოთ, მინდა, რა არის დრო და სივრცე სირთულის, დიდი O? ხშირად ისინი ასევე ვთხოვთ უმაღლესი დონის კითხვები, ასე, დიზაინი სისტემა, როგორ იწვა თქვენი კოდი? რა ინტერფეისები, რა კლასი, რა მოდულები გაქვთ თქვენს სისტემაში, და როგორ გავაკეთოთ ეს ურთიერთქმედება ერთად? ასე რომ მონაცემები სტრუქტურებისა და ალგორითმები ასევე დიზაინის სისტემები. 

ზოგიერთი ზოგადი რჩევა, სანამ ჩვენ ჩაყვინთვის, რათა ჩვენს შემთხვევაში კვლევები. ვფიქრობ ყველაზე მნიშვნელოვანი წესი ყოველთვის ფიქრობს გარეთ ხმამაღალი. ინტერვიუ უნდა იყოს თქვენი შანსი რათა ნახოთ off თქვენი აზროვნების პროცესი. წერტილი ინტერვიუში არის ინტერვიუერს რომ ლიანდაგი როგორ ფიქრობთ და როგორ გავლა პრობლემა. ყველაზე უარესი, რაც შეგიძლიათ გააკეთოთ არის იყოს ჩუმად მთელ ინტერვიუში. ეს მხოლოდ კარგი. როდესაც თქვენ მოცემულია კითხვა, თქვენ ასევე გვინდა დავრწმუნდეთ გესმით კითხვაზე. ამიტომ ვიმეორებ კითხვას უკან საკუთარი სიტყვები და მცდელობა მუშაობა საფუძვლიანი რამოდენიმე მარტივი ტესტის რათა დარწმუნდეთ, რომ თქვენ გესმით კითხვაზე. სამუშაო მეშვეობით რამდენიმე ტესტის ასევე გაძლევთ ინტუიცია თუ როგორ გადავჭრათ ეს პრობლემა. ალბათ კი აღმოაჩენთ რამდენიმე ნიმუში, რათა დაგეხმაროთ ამ პრობლემის მოსაგვარებლად. მათი დიდი წვერი არის არ უნდა იმედგაცრუებული. ნუ იმედგაცრუებული. გასაუბრება რთული, მაგრამ ყველაზე უარესი, რაც შეგიძლიათ გააკეთოთ, გარდა იმისა ჩუმად, უნდა აშკარად იმედგაცრუებულია. თქვენ არ მინდა, რომ შთაბეჭდილება, რომ ინტერვიუერს. ერთი რამ, რომ თქვენ - ასე, ბევრი ადამიანი, როდესაც მათ წასვლას ინტერვიუში, ისინი ცდილობენ ცდილობენ იპოვონ საუკეთესო გადაწყვეტილება პირველი, როდესაც რეალურად, აქ არის როგორც წესი glaringly აშკარა გადაწყვეტა. ეს შეიძლება იყოს ნელი, ეს შესაძლოა არაეფექტური, მაგრამ თქვენ უნდა სამართლიანი სახელმწიფოს იგი, უბრალოდ ასე რომ თქვენ არ ამოსავალი წერტილი საიდანაც მუშაობა უკეთესი. ასევე, მიუთითებს გამოსავალი არის ნელი, თვალსაზრისით დიდი O დრო სირთულის ან ჰარით სირთულის, იქნება ვაჩვენოთ ინტერვიუერს, რომ გესმით ამ საკითხებზე, როდესაც წერა კოდი. ასე რომ არ შეგეშინდეთ, რათა ამუშავება მარტივი ალგორითმი პირველი და შემდეგ მუშაობა უკეთესი იქიდან. ნებისმიერი კითხვები აქამდე? Okay. 

მოდით ჩაყვინთვის შევიდა ჩვენი პირველი პრობლემა. "იმის გათვალისწინებით მასივი n რიცხვებით, დაწერეთ ფუნქცია, რომელიც shuffles მასივი ადგილზე ისეთი, რომ ყველა permutations of n რიცხვებით თანაბრად სავარაუდოა. " და თავის თავზე იღებს გაქვთ ხელმისაწვდომია შემთხვევითი რიცხვი გენერატორი რომელიც ამ რიცხვის წელს მერყეობს 0 I, ნახევარი სპექტრი. ამჯამად ყველას გვესმის ამ კითხვაზე? მე გაძლევთ მასივი n რიცხვებით, და მინდა shuffle იგი. ჩემი დირექტორია, მე დავწერე რამდენიმე პროგრამების იმისა, თუ რა ვგულისხმობ. მე ვაპირებ shuffle მასივი 20 ელემენტები, საწყისი -10 to +9, და მინდა დაბეჭდავს სია მოსწონს ეს. ასე რომ, ეს ჩემი დახარისხებული შეყვანის მასივი, და მინდა shuffle იგი. ჩვენ გავაკეთებთ ერთხელ. ამჯამად ყველას გვესმის კითხვა? Okay. ასე რომ თქვენი გადასაწყვეტია. რა იდეები? შეგიძლიათ ამის გაკეთება, როგორც N ^ 2, N შესვლა N, N? კონკურსში მონაწილეობა შეუძლიათ წინადადებები. Okay. ამიტომ ერთი იდეა, მიერ შემოთავაზებული ემის, არის პირველი გამოთვლაც შემთხვევითი ნომერი, შემთხვევითი რიცხვი, წელს მერყეობს 0 დან 20. ამიტომ ვივარაუდოთ ჩვენი array აქვს სიგრძეზე 20. ჩვენს დიაგრამის 20 ელემენტები, ეს არის ჩვენი შეყვანის მასივი. და ახლა, მისი წინადადება არის, რომ შევქმნათ ახალი მასივი, ასე რომ, ეს იქნება გამომავალი მასივი. საფუძველზე დავბრუნდი მიერ RAND - ასე რომ, თუ მე ვიყავი, ასე ვთქვათ, 17, კოპირება -17 ელემენტს შევიდა პირველი პოზიცია. ახლა ჩვენ გვჭირდება წაშლა - გვჭირდება გადაეტანა ყველა ელემენტები აქ მეტი ისე, რომ ჩვენ გვაქვს უფსკრული დასასრულს და არ ხვრელებს შუა. და ახლა ჩვენ ვიმეორებ პროცესში. ახლა ჩვენ აირჩიოთ ახალი შემთხვევითი რიცხვი შორის 0 და 19. ჩვენ გვყავს ახალი მე აქ, და ჩვენ გადააკოპირეთ ეს ელემენტს ამ თანამდებობაზე. მაშინ ჩვენ გადაეტანა ელემენტი მეტი და ჩვენ ვიმეორებთ პროცესს, სანამ ჩვენ გვაქვს სრული new მასივი. რა არის პერსპექტივაში დრო ამ ალგორითმი? ისე, განვიხილოთ გავლენა ამ. ჩვენ გადასვლის ყველა ელემენტს. როდესაც ჩვენ ამოიღონ ამ მე, ჩვენ გადავიდა ყველა ელემენტების შემდეგ მას მარცხენა. და ეს არის O (N) ღირებულება რადგან რა თუ ჩვენ ამოიღონ პირველ ელემენტს? ამიტომ თითოეული მოცილება, ჩვენ ამოიღონ - ყოველ მოცილება დარღვევა O (N) ოპერაცია, და რადგან ჩვენ არ n removals, ამ მივყავართ O (N ^ 2) shuffle. Okay. იმდენად კარგი დასაწყისია. კარგი დასაწყისია. 

კიდევ ერთი წინადადება, გამოვიყენოთ რაღაც ცნობილი როგორც Knuth shuffle, ან Fisher-Yates shuffle. და ეს რეალურად ხაზოვანი დრო shuffle. და იდეა ძალიან გავს. ერთხელ, ჩვენ გვაქვს ჩვენი შეყვანის მასივი, მაგრამ ნაცვლად გამოყენებით ორი კოლექტორები ჩვენი input / output, ჩვენ ვიყენებთ პირველი ნაწილი მასივი ტრეკზე ჩვენი აჩეხვა ნაწილი, და ჩვენ ტრეკზე, ხოლო შემდეგ ჩვენ დატოვონ დანარჩენი ჩვენი array ამისთვის unshuffled ნაწილი. ასე რომ აქ არის ის, რასაც ვგულისხმობ. ვიწყებთ off ერთად - ვირჩევთ მე, array საწყისი 0 დან 20. ჩვენი მიმდინარე მაჩვენებელი არის მიუთითებს პირველი ინდექსი. ვირჩევთ ზოგიერთი მე აქ და ახლა ჩვენ სვოპ. ასე რომ, თუ ეს იყო 5 და ეს იყო 4, შედეგად მასივი ექნება 5 აქ და 4 აქ. და ახლა ჩვენ აღვნიშნავთ, მარკერის აქ. ყველაფერი მარცხნივ აჩეხვა, და ყველაფერი უფლება unshuffled. და ახლა ჩვენ შეგვიძლია გავიმეოროთ პროცესში. ვირჩევთ შემთხვევითი ინდექსი შორის 1 და 20 არის. ამიტომ ვარაუდობენ, რომ ჩვენი ახალი მე აქ არის. ახლა ჩვენ სვოპ ამ მე ჩვენს მიმდინარე ახალ თანამდებობაზე აქ. ამიტომ ჩვენ შევცვალე უკან და მეოთხე მოსწონს ეს. ნება მომეცით ზრდიან კოდი რათა ის უფრო კონკრეტული. ჩვენ დავიწყებთ ჩვენი არჩევანი მე - ჩვენ დავიწყებთ მე გაუტოლდება 0, ჩვენ აირჩიოთ შემთხვევითი საიდან კ წელს unshuffled ნაწილი მასივი, მე რომ N-1. ასე რომ, თუ მე აქ, აირჩიოს შემთხვევითი ინდექსი შორის აქ და დანარჩენ მასივი, და ჩვენ სვოპ. ეს არის ყველა კოდი აუცილებელია shuffle თქვენი მასივი. ნებისმიერი კითხვები? 

ისე, ერთი საჭირო კითხვაზე, თუ რატომ არის ამ სწორი? რატომ არის ყველა permutation თანაბრად სავარაუდოდ? და მე არ გავლა მტკიცებულება, მაგრამ ბევრი პრობლემა კომპიუტერულ მეცნიერებაში შეიძლება დაადგინა მეშვეობით ინდუქციური. რამდენი თქვენგანი იცნობს ინდუქციური? Okay. ზემოთ. ასე რომ თქვენ შეგიძლიათ დაამტკიცოს სისწორეს ეს ალგორითმი უბრალო ინდუქციური, სადაც თქვენი ინდუქციური ჰიპოთეზა იქნებოდა, ვივარაუდოთ, რომ ჩემი shuffle ბრუნდება ყოველ permutation თანაბრად სავარაუდოდ მდე პირველი მე ელემენტებს. ახლა, განიხილოს i + 1. და სხვათა შორის, ავირჩიოთ ჩვენი ინდექსი j რომ სვოპ, ამ მივყავართ - და მაშინ შეიმუშაოს ინფორმაცია მინიმუმ სრული მტკიცებულება, ამიტომ ეს ალგორითმი ბრუნდება ყველა permutation ერთად თანაბრად სავარაუდოდ ალბათობა. 

ყველა უფლება, შემდეგი პრობლემა. ასე რომ "მოცემულ მასივი რიცხვებით, postive, ნულოვანი, უარყოფითი, დაწერეთ ფუნქცია, რომელიც ანგარიშობს მაქსიმალური თანხა ნებისმიერი continueous subarray of შეყვანის მასივი. " მაგალითად აქ არის, იმ შემთხვევაში, ყველა ნომრები პოზიტიური, შემდეგ გაკეთებული საუკეთესო არჩევანი მიიღოს მთელი მასივი. 1, 2, 3, 4, შეადგენს 10. როდესაც თქვენ გარკვეული ნეგატივები იქ, ამ შემთხვევაში ჩვენ გვსურს მხოლოდ პირველი ორი რადგან არჩევის -1 და / ან -3 მოუტანს ჩვენი თანხა ქვემოთ. ზოგჯერ შეიძლება უნდა დაიწყოს შუა მასივი. ზოგჯერ ჩვენ გვინდა აირჩიოს არაფერი მოხვედრა, ეს იმისათვის, რომ არ მიიღოს არაფერი. და ზოგჯერ უმჯობესია მიიღოს შემოდგომაზე, რადგან რამ შემდეგ ეს სუპერ დიდი. ასე რომ ნებისმიერი იდეები? (სტუდენტი, გაუგებარია) >> Yeah. დავუშვათ, მე არ მიიღოს -1. მაშინ არც მე აირჩიოს 1,000 და 20,000, ან უბრალოდ აირჩიონ 3 მილიარდი. ისე, საუკეთესო არჩევანი, არის მიიღოს ყველა ნომრები. ეს -1, მიუხედავად უარყოფითი, მთელი თანხა უკეთესია იყო მე არ მიიღოს -1. ასე რომ ერთი რჩევა ვთქვი ადრე იყო სახელმწიფო ნათლად აშკარა და უხეში ძალის გადაწყვეტა პირველი. რა არის უხეში ძალის გადაწყვეტა ამ პრობლემის? ჰო? [Jane] ვფიქრობ, უხეში ძალის გადაწყვეტა იქნება დაამატოთ მდე ყველა შესაძლო კომბინაციები (გაუგებარია). [Yu] Okay. ამიტომ Jane იდეა არის მიიღოს ყველა შესაძლო - მე მის პერეფრაზირებას ვახდენ - არის მიიღოს ყველა შესაძლო უწყვეტი subarray, გამოთვლაც მისი თანხა და შემდეგ მიიღოს მაქსიმუმ ყველა შესაძლო უწყვეტი subarrays. რა უნიკალურ იდენტიფიკაციას subarray ჩემი შეყვანის მასივი? მსგავსად, რა ორი რამ მჭირდება? ჰო? (სტუდენტი, გაუგებარია) >> მარჯვენა. ქვედა შეკრული on ინდექსი და ზედა ბლოკნოტის ინდექსი ცალსახად განსაზღვრავს უწყვეტი subarray. [ქალი სტუდენტი] ვართ შეფასებისას ეს მასივი უნიკალური ნომრები? [Yu] მდებარ ამიტომ მისი საკითხი, ჩვენ ვთქვათ ჩვენი მასივი - ჩვენი მასივი უნიკალური ნომრები და პასუხი არ არის. 

თუ ჩვენ გამოვიყენებთ ჩვენი უხეში ძალის გადაწყვეტა, მაშინ დაწყება / ბოლომდე მაჩვენებლების ცალსახად განსაზღვრავს ჩვენი უწყვეტი subarray. ასე რომ, თუ ჩვენ iterate ყველა შესაძლო დაწყების entries, და სამუდამოდ ბოლომდე შესვლის> ან = დაიწყოს, და <n, თქვენ გამოთვლაც თანხა და შემდეგ ჩვენ ვიღებთ მაქსიმალური თანხა ჩვენ ვნახეთ ჯერჯერობით. ეს ნათელი? რა არის დიდი O ამ გამოსავალი? Timewise. არ საკმაოდ N ^ 2. გაითვალისწინეთ, რომ ჩვენ iterate საწყისი 0 to n, ასე რომ ერთი მარყუჟი. ჩვენ iterate ერთხელ თითქმის თავიდან ბოლომდე, მეორე loop. და ახლა, შიგნით რომ, ჩვენ უნდა შეაჯამოს ყველა ჩანაწერი, ასე რომ მეორე loop. ასე რომ ჩვენ გვაქვს სამი წყობილი ამისთვის მარყუჟების, N ^ 3. Okay. ეს მიდის როგორც ამოსავალი წერტილი. ჩვენი გამოსავალი არის უარესი N ^ 3. ამჯამად ყველას გვესმის უხეში ძალის გამოსავალი? 

Okay. უკეთესი გამოსავალი იყენებს იდეა მოუწოდა დინამიური პროგრამირების. თუ თქვენ მიიღოს CS124, რომელიც ალგორითმები და მონაცემთა სტრუქტურები, თქვენ გახდება ძალიან ნაცნობია ეს ტექნიკა. და იდეა, ცდილობენ დაამყარონ გადაწყვეტილებების პატარა პრობლემები პირველი. რას ვგულისხმობ ამ არის, ჩვენ გაკეთებული აქვს ფიქრი ორი რამ: დაწყება და დასასრული. და ეს შემაშფოთებელი. რა მოხდება, თუ ჩვენ თავს დააღწევდა ერთ იმ პარამეტრების? ერთი იდეა იმაში მდგომარეობს, - we're მოცემული ჩვენი ორიგინალური პრობლემა, იპოვოს მაქსიმალური თანხა ნებისმიერი subarray in Range [O, N-1]. და ახლა ჩვენ გვაქვს ახალი subproblem, სადაც ჩვენ ვიცით, ჩვენი მიმდინარე ინდექსი i, ჩვენ ვიცით, ჩვენ უნდა დავასკვნათ არსებობს. ჩვენი subarray უნდა დასრულდეს მიმდინარე ინდექსი. ასე დარჩენილი პრობლემა ისაა, სადაც უნდა დაიწყოს ჩვენი subarray? ამჯამად ამ აზრი? Okay. ამიტომ მე ამ კოდირებული up, და მოდით შევხედოთ რას ნიშნავს. In 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 რომ უნდა დასრულდეს პირველი პოზიცია? [სტუდენტური] Zero. >> Zero. უბრალოდ არ მიიღოს -5. აქ იქნება 0 ისევე. ჰო? (სტუდენტი, გაუგებარია) [Yu] ოჰ, უკაცრავად, ეს არის -3. ასე რომ, ეს არის 2, ეს არის -3. Okay. ასე -4, რა მაქსიმალური subarray ბოლოში რომ თანამდებობა სად -4 არის? ნულოვანი. ერთი? 1, 5, 8. ახლა, მე უნდა დასრულდეს დროს ადგილი, სადაც -2 არის. ასე რომ, 6, 5, 7, და ბოლოს ერთი არის 4. იცის, რომ ეს არის ჩემი მასალა ამისთვის გარდაიქმნება პრობლემა, სადაც მე უნდა დასრულდეს ყოველ ამ მაჩვენებლების, მაშინ ჩემი საბოლოო პასუხი მხოლოდ, მიიღოს Sweep მასშტაბით, და მიიღოს მაქსიმალური რაოდენობა. ასე რომ ამ შემთხვევაში ეს 8. ეს გულისხმობს იმას, რომ მაქსიმალური subarray დამთავრდა ამ ინდექსი, და დაიწყო სადღაც სანამ. ამჯამად ყველას გვესმის ამ ტრანსფორმირებული subarray? 

Okay. კარგად, მოდით გაერკვნენ რეციდივი ამისათვის. განვიხილოთ მხოლოდ პირველი რამდენიმე entries. ასე რომ აქ იყო 0, 0, 0, 1, 5, 8. და მაშინ იყო -2 აქ, და რომ შემოიყვანა ქვემოთ 6. ასე რომ, თუ მოვუწოდებ შესვლის პოზიციაში მე subproblem (I), როგორ გამოვიყენო პასუხი წინა subproblem პასუხის გაცემა ამ subproblem? თუ გავითვალისწინებთ, ასე ვთქვათ, ამ ჩანაწერში. როგორ შემიძლია გამოთვლაც პასუხი 6 by ეძებს კომბინაცია ამ array და პასუხები წინა subproblems ამ მასივი? დიახ? [ქალი სტუდენტი] თქვენ მიიღოს მასივი თანხები წელს თანამდებობა უფლება ადრე, ასე რომ 8, და მაშინ დაამატოთ მიმდინარე subproblem. [Yu] ასე მისი წინადადება არის შევხედოთ ამ ორი ნომერი, ეს რაოდენობა და ეს რიცხვი. ასე რომ, ეს 8 ეხება პასუხს subproblem (I - 1). და მოდით მოვუწოდებთ ჩემი შეყვანის მასივი ა იმისათვის, რომ იპოვოს მაქსიმალური subarray რომ დამთავრდა პოზიციაში მე, მე ორი არჩევანი: შემიძლია ან გაგრძელდება subarray რომ დასრულდა წინა ინდექსი, დაიწყოს ახალი მასივი. მე რომ გააგრძელოს subarray რომ დაიწყო წინა ინდექსი, მაშინ მაქსიმალური თანხა შემიძლია მისაღწევად არის პასუხი წინა subproblem პლუს მიმდინარე მასივი ჩანაწერს. მაგრამ, მე ასევე აქვს არჩევანი დაწყებული ახალი subarray, ამ შემთხვევაში თანხა 0. ასე რომ პასუხი არის max სულ 0, subproblem i - 1, პლუს მიმდინარე მასივი ჩანაწერს. ამჯამად ამ რეციდივი აქვს აზრი? ჩვენი რეციდივი, როგორც ჩვენ უბრალოდ აღმოაჩინეს, არის subproblem მე უდრის მაქსიმუმ წინა subproblem პლუს ჩემი მიმდინარე მასივი შესვლის, რაც იმას ნიშნავს, გავაგრძელოთ წინა subarray, ან 0, დაიწყოს ახალი subarray ჩემს მიმდინარე ინდექსი. და კიდევ ავაშენეთ up ამ მაგიდასთან გადაწყვეტილებები, მაშინ ჩვენი საბოლოო პასუხი, უბრალოდ ხაზოვანი Sweep მასშტაბით subproblem მასივი და მიიღოს მაქსიმალური რაოდენობა. ეს არის ზუსტი განხორციელება, რაც მე უბრალოდ განაცხადა. ამიტომ, ჩვენ შევქმნათ ახალი subproblem მასივი, subproblems. პირველადი შემოსვლისათვის არის ან 0 ან პირველადი შემოსვლისათვის, მაქსიმუმ ორი. და დანარჩენი subproblems ჩვენ ვიყენებთ ზუსტი რეციდივი ჩვენ უბრალოდ აღმოაჩინეს. ახლა ჩვენ გამოთვლაც მაქსიმალური ჩვენი subproblems მასივი, და ეს ჩვენი საბოლოო პასუხი. 

ასე რომ რა ზომის არიან ჩვენ გამოყენებით ამ ალგორითმი? თუ თქვენ მხოლოდ მიღებული CS50, მაშინ თქვენ ალბათ არ უმსჯელია სივრცეში ძალიან. ისე, ერთი რამ აღვნიშნო არის ის, რომ დავურეკე malloc აქ ზომა n. რას გთავაზობთ თქვენ? ეს ალგორითმი იყენებს წრფივ სივრცეში. გავაკეთოთ უკეთესი? არის რამე რომ თქვენ შეამჩნევთ, რომ არის ზედმეტი გამოთვლაც საბოლოო პასუხი? ვფიქრობ უკეთესი კითხვაზე, თუ რა ინფორმაციას ჩვენ არ უნდა შეასრულოს ყველა გზა ბოლომდე? ახლა, თუ შევხედავთ ამ ორი ხაზი, ჩვენ მხოლოდ აინტერესებს წინა subproblem, და ჩვენ მხოლოდ აინტერესებს მაქსიმალური ჩვენ ოდესმე მინახავს აქამდე. გამოთვლაც ჩვენი საბოლოო პასუხი, ჩვენ არ გვჭირდება მთელი მასივი. ჩვენ მხოლოდ გვჭირდება ბოლო ნომერი, ბოლო ორი ნომერი. ბოლო ნომრის subproblem მასივი, და ბოლო ნომერი, მაქსიმუმ. ასე რომ, ფაქტობრივად, ჩვენ შეგვიძლია დაუკრავენ ამ მარყუჟების ერთად და აქედან ხაზოვანი სივრცეში მუდმივი სივრცეში. აქტუალური თანხა ჯერჯერობით, აქ, ცვლის როლი subproblem, ჩვენი subproblem მასივი. ასე რომ მიმდინარე თანხა, ჯერჯერობით, არის პასუხი წინა subproblem. და რომ თანხა, ჯერჯერობით, იღებს ადგილი ჩვენი მაქს. ჩვენ გამოთვლაც მაქსიმალური როგორც ჩვენ წავიდეთ ერთად. ამიტომ ჩვენ აქედან ხაზოვანი სივრცეში მუდმივი სივრცეში, და ჩვენ ასევე გვაქვს ხაზოვანი გადაწყვეტა ჩვენი subarray პრობლემა. 

ამ სახის კითხვებით მიიღებთ დროს ინტერვიუში. რა არის დრო სირთულის, რა არის სივრცე სირთულის? შეგიძლიათ უკეთესი? არსებობს რამ, რომ არიან ზედმეტი შენარჩუნება გარშემო? მე ამ ითვალისწინებდეს ანალიზი, რომ თქვენ უნდა მიიღოს საკუთარ როგორც თქვენ სამუშაო მეშვეობით ამ პრობლემების. ყოველთვის ეკითხება თავის "გავაკეთო უკეთესი?" ფაქტობრივად, გავაკეთოთ უკეთესი ვიდრე ეს? სახის ხრიკი კითხვა. თქვენ არ შეგიძლიათ, რადგან თქვენ უნდა მინიმუმ წაიკითხა შეყვანის პრობლემას. ასე რომ ის ფაქტი, რომ თქვენ უნდა მინიმუმ წაიკითხა შეყვანის პრობლემას ნიშნავს, რომ თქვენ ვერ უკეთესად ხაზოვანი დროს, და ვერ უკეთესად, ვიდრე მუდმივი სივრცეში. ასე რომ, ეს, ფაქტობრივად, საუკეთესო გამოსავალი ამ პრობლემას. კითხვები? Okay. 

საფონდო ბაზრის პრობლემა: "იმის გათვალისწინებით მასივი n რიცხვებით, დადებითი, ნულოვანი, ან უარყოფითი, რომ წარმოადგენენ ფასი საფონდო მეტი N დღით, წერენ ფუნქცია გამოთვლაც მაქსიმალური მოგება შეგიძლიათ იმის გათვალისწინებით, რომ თქვენ შეიძინოთ და გაყიდოს ზუსტად 1 საფონდო ფარგლებში ამ N დღის ვადაში. " არსებითად, ჩვენ გვინდა ყიდვა დაბალია, გაყიდოს მაღალი. და გვინდა გაერკვნენ საუკეთესო მოგება შეიძლება გავაკეთოთ. ბრუნდება ჩემი წვერი, რა არის მაშინვე ნათელი, მარტივი პასუხი, მაგრამ ნელი? დიახ? (სტუდენტი, გაუგებარია) >> დიახ. >> ასე რომ უბრალოდ თუმცა და შევხედოთ საფონდო ფასები ყოველ მომენტში, (გაუგებარია). [Yu] Okay, ასე რომ მისი გადაწყვეტა - მისი წინადადებით Computing ყველაზე დაბალი და კომპიუტერული უმაღლესი სულაც არ იმუშავებს რადგან უმაღლეს შეიძლება მოხდეს ადრე ყველაზე დაბალი. რა არის უხეში ძალის აღნიშნული პრობლემის მოსაგვარებლად? რა არის ორი რამ, რომ მე უნდა ცალსახად განსაზღვრავს მოგების მე? მარჯვენა. უხეში ძალის გამოსავალი - Oh, ამიტომ, გიორგის წინადადება არის ჩვენ მხოლოდ ორი დღის განმავლობაში to ცალსახად განსაზღვრავს მოგების იმ ორი დღის განმავლობაში. ამიტომ, ჩვენ გამოთვლაც ყველა წყვილი, როგორიცაა ყიდვა / გაყიდვის, გამოთვლაც მოგება, რომელიც შეიძლება უარყოფითი ან დადებითი ან ნულოვანი. გამოთვლაც მაქსიმალური მოგება რომ ჩვენ შემდეგ iterating ყველა წყვილი დღის განმავლობაში. ეს იქნება ჩვენი საბოლოო პასუხი. და რომ გამოსავალი იქნება O (N ^ 2), რადგან არ არსებობს N აირჩიოს ორი წყვილი - დღეში, რომ თქვენ შეგიძლიათ აირჩიოთ შორის დასასრულს დღის განმავლობაში. Okay, ასე არ ვაპირებ წასვლა მეტი უხეში ძალის გამოსავალი აქ. მე ვაპირებ გითხრათ, რომ არსებობს n შესვლა N გადაწყვეტა. რა ალგორითმი გაქვთ გაკეთებული ვიცი, რომ არის N შესვლა N? ეს არ შეასრულა კითხვაზე. 

შერწყმა ჯიშია. შერწყმა დალაგების არის N შესვლა N, და ფაქტობრივად, ერთი გზა პრობლემის მოსაგვარებლად არის გამოიყენოს შერწყმა დალაგების სახის იდეა მოუწოდა, ზოგადად, გათიშე და დაიპყროთ. და იდეა ასეთია. გსურთ გამოთვლაც საუკეთესო ყიდვა / გაყიდვის წყვილი მარცხენა ნახევარში. მოძებნა საუკეთესო მოგება შეგიძლიათ, მხოლოდ პირველი n ორი დღის განმავლობაში. მაშინ გსურთ oompute საუკეთესო ყიდვა / გაყიდვის წყვილი მარჯვენა ნახევარში, ასე ბოლო N ორი დღის განმავლობაში. და ახლა კითხვა არის, როგორ უნდა შერწყმა ამ გადაწყვეტილებების უკან ერთად? დიახ? (სტუდენტი, გაუგებარია) >> Okay. ნება მომეცით, შევაჩერო Picture. დიახ? (გიორგი, გაუგებარია) >> ზუსტად. გიორგის გამოსავალი არის სწორედ. ამიტომ მისი წინადადება არის, პირველ გამოთვლაც საუკეთესო ყიდვა / გაყიდვის წყვილი, და რომ ხდება მარცხენა ნახევარში, მოდით მოვუწოდებთ, რომ მარცხენა დატოვა. საუკეთესო ყიდვა / გაყიდვის წყვილი რომ გვხვდება მარჯვენა ნახევარში. მაგრამ თუ ჩვენ მხოლოდ შედარებით ეს ორი ნომერი, ჩვენ დაკარგული შემთხვევაში სად ვყიდულობთ აქ და გაყიდოს სადღაც მარჯვენა ნახევარში. ჩვენ ვყიდულობთ in მარცხენა ნახევარში, გაყიდვა მარჯვენა ნახევარში. და საუკეთესო გზა გამოთვლაც საუკეთესო ყიდვა / გაყიდვის წყვილი რომელიც მოიცავს ორივე halves არის გამოთვლაც მინიმალური აქ და გამოთვლაც მაქსიმალური აქ და მიიღოს მათი განსხვავება. ასე რომ ორ შემთხვევაში, როდესაც ყიდვა / გაყიდვის წყვილი ხდება მხოლოდ აქ, მარტო აქ, ან ორივე halves განისაზღვრება ამ სამი ნომრები. ასე რომ ჩვენი ალგორითმი შერწყმა ჩვენი გადაწყვეტილებები უკან ერთად, ჩვენ გვინდა გამოთვლაც საუკეთესო ყიდვა / გაყიდვის წყვილი სად ვყიდულობთ მარცხენა ნახევარში და გაყიდოს მარჯვენა ნახევარში. და საუკეთესო გზა ამის გაკეთება არის გამოთვლაც ყველაზე დაბალ ფასად წლის პირველ ნახევარში, უმაღლესი ფასი მარჯვენა ნახევარში, და მიიღოს მათი განსხვავება. შედეგად სამი მოგება, ამ სამი რიცხვი, თქვენ მიიღოს მაქსიმუმ სამი, და ეს საუკეთესო მოგება შეგიძლიათ ამ პირველი და ბოლოს დღის განმავლობაში. აქ მნიშვნელოვანი ხაზები წითელი. ეს არის რეკურსიული ზარის გამოთვლაც პასუხი მარცხენა ნახევარში. ეს არის რეკურსიული ზარის გამოთვლაც პასუხი მარჯვენა ნახევარში. ეს ორი მარყუჟების გამოთვლაც min და max მარცხენა და მარჯვენა ნახევარში, შესაბამისად. ახლა გამოთვლაც მოგება რომელიც მოიცავს ორივე halves, და საბოლოო პასუხი არის მაქსიმალური ამ სამი. Okay. 

ასე რომ, დარწმუნებული ვარ, რომ ჩვენ გვაქვს ალგორითმი, მაგრამ უფრო დიდი კითხვა არის, რა არის დრო სირთულის ამ? და მიზეზი, რის გამოც ვთქვი შერწყმა დალაგების ის არის, რომ ამ ფორმით დაყოფის პასუხი ორ და შემდეგ შერწყმის ჩვენი გადაწყვეტილებები უკან ერთად სწორედ ფორმით შერწყმა ჯიშია. ნება მომეცით გავლა ხანგრძლივობა. თუ ჩვენ განსაზღვრული ფუნქცია t (N) უნდა იყოს მთელი რიგი ზომების ამისთვის N დღით, ჩვენი ორი რეკურსიული მოუწოდებს მათ ყოველ აპირებს ეღირება T (n / 2), და არსებობს ორი მოუწოდებს. ახლა მე უნდა გამოთვლაც მინიმუმ მარცხენა ნახევარში, რაც შემიძლია in N / 2 ახლა, პლუს მაქსიმუმ მარჯვენა ნახევარში. ასე რომ, ეს უბრალოდ n. და მერე პლუს რამდენიმე მუდმივი მუშაობა. და ეს არ განმეორდეს განტოლება სწორედ რეციდივი განტოლება ამისთვის შერწყმა ჯიშია. და ჩვენ ყველამ ვიცით, რომ შერწყმა დალაგების არის N შესვლა N დრო. ამიტომ, ჩვენი ალგორითმი ასევე n შესვლა N დრო. ამჯამად ამ iteration აზრი? უბრალოდ მოკლე recap ამ: T (n) არის მთელი რიგი ზომების გამოთვლაც მაქსიმალური მოგება მეტი კურსი N დღით. გზა ჩვენ გაყოფილი up ჩვენი რეკურსიული მოუწოდებს არის დარეკვით ჩვენი გამოსავალი პირველ N / 2 დღე, ისე, რომ ერთი ზარი, და მაშინ ჩვენ მოვუწოდებთ კვლავ მეორე ნახევარში. ასე რომ ორი მოუწოდებს. და მაშინ ჩვენ მინიმალური მარცხენა ნახევარში, რომელიც ჩვენ შეგვიძლია გავაკეთოთ ხაზოვანი დროს, იპოვოს მაქსიმუმ მარჯვენა ნახევარში, რომელიც ჩვენ შეგვიძლია გავაკეთოთ ხაზოვანი დრო. ამიტომ N / 2 + N / 2 მხოლოდ n. მაშინ ჩვენ გვაქვს მუდმივი მუშაობა, რომელიც მოსწონს აკეთებს არითმეტიკული. ეს რეციდივი განტოლება არის ზუსტად რეციდივი განტოლება ამისთვის შერწყმა ჯიშია. აქედან გამომდინარე ჩვენი shuffle ალგორითმი ასევე N შეხვიდეთ n. ასე რომ რა ზომის არიან ჩვენ გამოყენებით? მოდით დავუბრუნდეთ კოდი. 

უკეთესი შეკითხვა, რამდენი დასტის ფარგლებში ჩვენ ოდესმე აქვს ნებისმიერ მოცემულ მომენტში? მას შემდეგ, რაც ჩვენ გამოყენებით უკან, პუნქტების დასტის ფარგლებში განსაზღვრავს ჩვენი სივრცის გამოყენება. განვიხილოთ n = 8. ჩვენ მოვუწოდებთ shuffle წლის 8, რომელიც მოვუწოდებთ shuffle წლის პირველი ოთხი entries, რომელიც მოვუწოდებთ shuffle პირველ ორ entries. ასე რომ ჩვენი დასტის არის - ეს არის ჩვენი Stack. და მაშინ ჩვენ მოვუწოდებთ shuffle კვლავ 1, და ეს რა არის ჩვენი ბაზის შემთხვევაში არის, ამიტომ ჩვენ დაბრუნებას დაუყოვნებლივ. ჩვენ ოდესმე მეტი გვაქვს ამ ბევრი დასტის ფარგლებში? პოსტები გამო ყოველ ჯერზე ჩვენ გავაკეთებთ invocation, რეკურსიული invocation to shuffle, ჩვენ ყოფს ჩვენს ზომა ნახევარ. ასე რომ მაქსიმალური რაოდენობის დასტის ფარგლებში ჩვენ ოდესმე აქვს ნებისმიერ მოცემულ მომენტში არის ბრძანებით შესვლა N დასტის ფარგლებში. თითოეული დასტის ჩარჩო აქვს მუდმივი სივრცეში, და ამიტომ საერთო რაოდენობის სივრცეში, მაქსიმალური თანხა სივრცეში ოდესმე გამოიყენოს არის O (log N) კოსმოსური სადაც n დღეების რაოდენობა. 

ახლა, ყოველთვის ჰკითხეთ საკუთარ თავს ", გავაკეთოთ უკეთესი?" კერძოდ, შეგვიძლია შეამციროს ეს პრობლემა ჩვენ უკვე მოგვარებული? მინიშნება: ჩვენ მხოლოდ განიხილეს ორ სხვა პრობლემების წინაშე ამ და ეს არ იქნება shuffle. ჩვენ შეგიძლიათ დააკონვერტიროთ ამ საფონდო პრობლემა შევიდა მაქსიმალური subarray პრობლემა. როგორ შეგვიძლია ამის გაკეთება? ერთი თქვენგანი? ემის? (ემის, გაუგებარია) [Yu] ზუსტად. ამიტომ მაქსიმალური subarray პრობლემა, ჩვენ ვეძებთ თანხა მეტი უწყვეტი subarray. და ემის წინადადება შეეხება აქციების პრობლემა, განიხილოს ცვლილებები, ან deltas. და სურათს ეს - ეს არის ფასი საფონდო, მაგრამ თუ ავიღეთ სხვაობა თითოეული ზედიზედ დღე - ამიტომ ჩვენ ვხედავთ, რომ მაქსიმალური ფასი, მაქსიმალური მოგება შეგვეძლო მიიღოს არის თუ ვყიდულობთ აქ და გაყიდოს აქ. მაგრამ მოდით შევხედოთ უწყვეტი - მოდით შევხედოთ subarray პრობლემა. ასე რომ, ჩვენ შეგვიძლია - აპირებს აქედან აქ, ჩვენ გვაქვს პოზიტიური ცვლილება, და შემდეგ აპირებს აქედან აქ გვაქვს უარყოფითი ცვლილება. თუმცა, შემდეგ აპირებს აქედან აქ ჩვენ გვაქვს უზარმაზარი პოზიტიური ცვლილება. და ეს ცვლილებები, რომ ჩვენ გვინდა შევაჯამოთ მისაღებად ჩვენი საბოლოო მოგება. შემდეგ ჩვენ უფრო მეტი უარყოფითი ცვლილებები აქ. გასაღები შემცირების ჩვენი საფონდო პრობლემა ჩვენს მაქსიმალური subarray პრობლემა არის განიხილოს deltas შორის დღით. ამიტომ, ჩვენ შევქმნით ახალ მასივი მოუწოდა deltas, ინიციალიზაცია პირველადი შემოსვლისათვის იყოს 0, და მაშინ თითოეული დელტა (I), ნება რომ იყოს სხვაობა ჩემი შეყვანის array (I), და array (I - 1). მაშინ ჩვენ მოვუწოდებთ ჩვენი რუტინული პროცედურა მაქსიმალური subarray გადადის დელტა ს მასივი. და რადგან მაქსიმალური subarray არის წრფივი დრო, და ეს შემცირება, ამ პროცესში შექმნის Delta მასივი, ასევე ხაზოვანი დროს, მაშინ საბოლოო გადაწყვეტილება აქციების არის O (N) მუშაობის Plus O (N) მუშაობა, ჯერ კიდევ O (N) მუშაობა. ამიტომ ხაზოვანი ახლა გადაწყვეტა ჩვენი პრობლემა. ამჯამად ყველას გვესმის ამ ტრანსფორმაციის? 

ზოგადად, კარგი იდეა, რომ თქვენ ყოველთვის უნდა ჰქონდეს არის ცდილობენ შეამციროს ახალი პრობლემა, რომ თქვენ ხედავს. თუ ეს გამოიყურება ნაცნობი ძველი პრობლემა, ვცდილობთ შემცირების მას ძველი პრობლემა. და თუ თქვენ შეგიძლიათ გამოიყენოთ ყველა ინსტრუმენტები, რომ თქვენ გამოიყენება ძველი პრობლემა გადაჭრის ახალი პრობლემა. ასე რომ გადაიტანოთ up, ტექნიკური გასაუბრება იწვევს. ეს პრობლემები ალბათ ზოგიერთი უფრო რთული პრობლემები რომ თქვენ შეიძლება ნახოთ ინტერვიუში, ასე რომ, თუ თქვენ არ მესმის ყველა პრობლემა, რომ მე უბრალოდ დაფარული, ეს okay. ეს არის ზოგიერთი უფრო რთული პრობლემები. პრაქტიკა, პრაქტიკა, პრაქტიკა. მივეცი ბევრი პრობლემები handout, ამიტომ აუცილებლად შეამოწმეთ იმ გარეთ. და წარმატებას გისურვებთ თქვენს ინტერვიუებს. ყველა ჩემი რესურსების განთავსებული იქნა ამ ბმულს და ერთი ჩემი უფროსი მეგობრები შესთავაზა გავაკეთოთ იმიტირებულ ტექნიკური ინტერვიუები, ასე რომ, თუ თქვენ დაინტერესებული, წერილში Yao იმ ელექტრონული ფოსტის მისამართი. თუ გაქვთ კითხვები, შეგიძლიათ შემეკითხებით. მიგაჩნიათ თუ არა ბიჭები გვყავს კონკრეტული შეკითხვები, რომელიც დაკავშირებულია ტექნიკური ინტერვიუები ან რაიმე სახის პრობლემები, ჩვენ ვხედავთ, ჯერჯერობით? Okay. ისე, წარმატებას გისურვებთ თქვენს ინტერვიუებს. [CS50.TV]