[Powered by Google Translate] [Hội thảo: Phỏng vấn kỹ thuật] [Kenny Yu, Đại học Harvard] [Đây là CS50.] [CS50.TV] Chào tất cả mọi người, tôi là Kenny. Tôi hiện một cơ sở nghiên cứu khoa học máy tính. Tôi là một cựu CS TF, và tôi muốn tôi đã có khi tôi là một underclassman, và đó là lý do tại sao tôi cho hội thảo này. Vì vậy, tôi hy vọng bạn sẽ thích nó. Hội thảo này là phỏng vấn kỹ thuật, và tất cả các nguồn lực có thể được tìm thấy tại liên kết này, liên kết này ngay tại đây, một vài nguồn tài nguyên. Vì vậy, tôi đã thực hiện một danh sách các vấn đề, trên thực tế, khá một vài vấn đề. Cũng là một nguồn tài nguyên chung, nơi chúng ta có thể tìm thấy lời khuyên làm thế nào để chuẩn bị cho một cuộc phỏng vấn, lời khuyên về những gì bạn nên làm trong một cuộc phỏng vấn thực tế, cũng như làm thế nào để tiếp cận vấn đề và các nguồn lực để tham khảo trong tương lai. Đó là tất cả trực tuyến. Và chỉ để lời nói đầu buổi hội thảo này, một sự từ bỏ, như thế này không nên - chuẩn bị phỏng vấn không nên giới hạn danh sách này. Điều này chỉ có nghĩa là phải là hướng dẫn, và bạn chắc chắn nên tất cả những gì tôi nói với một hạt muối, nhưng cũng có thể sử dụng tất cả những gì tôi được sử dụng để giúp bạn trong việc chuẩn bị phỏng vấn của bạn. 

Tôi sẽ tăng tốc độ qua các slide tiếp theo vì vậy chúng tôi có thể nhận được các nghiên cứu trường hợp thực tế. Cấu trúc của một cuộc phỏng vấn cho một công nghệ phần mềm postion, thường là 30 đến 45 phút, nhiều viên đạn, tùy thuộc vào công ty. Thường thì bạn sẽ được mã hóa trên một bảng trắng. Vì vậy, một bảng trắng như thế này, nhưng thường trên một quy mô nhỏ hơn. Nếu bạn đang có một cuộc phỏng vấn qua điện thoại, có thể bạn sẽ được sử dụng hoặc collabedit hoặc Google Doc để họ có thể nhìn thấy bạn sống mã hóa trong khi bạn đang được phỏng vấn qua điện thoại. Một cuộc phỏng vấn riêng của mình thường là 2 hoặc 3 vấn đề kiểm tra kiến ​​thức khoa học máy tính của bạn. Và nó gần như chắc chắn sẽ liên quan đến mã hóa. Các loại câu hỏi mà bạn sẽ thấy thường cấu trúc dữ liệu và các thuật toán. Và làm các loại của các vấn đề, họ sẽ hỏi bạn, thích, không gian, thời gian và phức tạp O lớn là gì? Thường thì họ cũng yêu cầu các câu hỏi cấp cao hơn, như vậy, thiết kế một hệ thống, làm thế nào bạn sẽ đặt mã của bạn? Giao diện, những gì các lớp học, những mô-đun nào bạn có trong hệ thống của bạn, và làm thế nào để tương tác với nhau? Vì vậy, cấu trúc dữ liệu và các thuật toán cũng như các hệ thống thiết kế. 

Một số thủ thuật chung trước khi chúng tôi đi sâu vào nghiên cứu trường hợp của chúng tôi. Tôi nghĩ rằng các quy tắc quan trọng nhất là luôn luôn nghĩ lớn. Cuộc phỏng vấn được coi là cơ hội của bạn để hiển thị quá trình suy nghĩ của bạn. Điểm của cuộc phỏng vấn là cho người phỏng vấn để đánh giá bạn nghĩ như thế nào và làm thế nào bạn đi qua một vấn đề. Điều tồi tệ nhất bạn có thể làm là im lặng trong suốt cuộc phỏng vấn. Đó chỉ là không tốt. Khi bạn đưa ra một câu hỏi, bạn cũng muốn chắc chắn rằng bạn hiểu câu hỏi. Vì vậy, lặp lại các câu hỏi theo cách của bạn và cố gắng để làm việc qua một trường hợp thử nghiệm đơn giản để chắc chắn rằng bạn hiểu câu hỏi. Làm việc thông qua một vài trường hợp thử nghiệm cũng sẽ cung cấp cho bạn một trực giác về việc làm thế nào để giải quyết vấn đề này. Bạn thậm chí có thể phát hiện ra một vài mẫu để giúp bạn giải quyết vấn đề. Tip lớn của họ là không được nản lòng. Không được nản lòng. Phỏng vấn là thách thức, nhưng điều tồi tệ nhất bạn có thể làm, Ngoài im lặng là để được thấy thất vọng. Bạn không muốn cung cấp cho rằng ấn tượng với người phỏng vấn. Một điều mà bạn - vì vậy, nhiều người, khi họ đi vào một cuộc phỏng vấn, họ cố gắng để cố gắng tìm giải pháp tốt nhất đầu tiên, khi thực sự, thường có một giải pháp rất rõ ràng. Nó có thể được làm chậm, nó có thể là không hiệu quả, nhưng bạn chỉ cần nêu, chỉ để bạn có một điểm khởi đầu mà từ đó để làm việc tốt hơn. Ngoài ra, chỉ ra các giải pháp là chậm, trong điều khoản của O lớn thời gian phức tạp hay phức tạp không gian, sẽ chứng minh cho người phỏng vấn rằng bạn hiểu những vấn đề này khi viết mã. Vì vậy, không sợ để đến với các thuật toán đơn giản đầu tiên và sau đó làm việc tốt hơn từ đó. Bất kỳ câu hỏi nào cho đến nay? Okay. 

Vì vậy, hãy đi sâu vào vấn đề đầu tiên của chúng tôi. "Với một mảng các số nguyên n, viết một chức năng mà shuffles các mảng ở vị trí như vậy mà tất cả các hoán vị của các số nguyên n đều có khả năng. " Và giả sử bạn đã có sẵn một máy phát điện số nguyên ngẫu nhiên mà tạo ra một số nguyên trong phạm vi từ 0 đến tôi, một nửa phạm vi. Có tất cả mọi người hiểu câu hỏi này? Tôi cung cấp cho bạn một mảng các số nguyên n, và tôi muốn bạn xào bài. Trong thư mục của tôi, tôi đã viết một vài chương trình để chứng minh những gì tôi có ý nghĩa. Tôi sẽ để shuffle một mảng có 20 phần tử, từ -10 đến +9, và tôi muốn bạn xuất ra một danh sách như thế này. Vì vậy, đây là sắp xếp mảng đầu vào của tôi, và tôi muốn bạn xào bài. Chúng tôi sẽ làm điều đó một lần nữa. Có tất cả mọi người hiểu câu hỏi? Okay. Vì vậy, nó tùy thuộc vào bạn. Một số ý tưởng là gì? Bạn có thể làm điều đó như n ^ 2, n log n, n? Mở để gợi ý. Okay. Vì vậy, một ý tưởng, đề xuất bởi Emmy, là lần đầu tiên tính toán một số ngẫu nhiên, ngẫu nhiên số nguyên, trong một phạm vi từ 0 đến 20. Vì vậy, giả sử mảng của chúng tôi có chiều dài là 20. Trong sơ đồ của chúng tôi có 20 phần tử, đây là mảng đầu vào của chúng tôi. Và bây giờ, đề nghị của cô là tạo ra một mảng mới, vì vậy đây sẽ là mảng đầu ra. Và dựa trên trả về bởi rand vì vậy nếu tôi là, hãy nói, 17, sao chép các phần tử 17 vào vị trí đầu tiên. Bây giờ chúng ta cần phải xóa - chúng ta cần phải thay đổi tất cả các yếu tố ở đây hơn để chúng tôi có một khoảng cách ở cuối và không có lỗ ở giữa. Và bây giờ chúng ta lặp lại quá trình. Bây giờ chúng ta chọn một số nguyên ngẫu nhiên giữa 0 và 19. Chúng tôi có một i mới ở đây, và chúng tôi sao chép phần tử vào vị trí này. Sau đó, chúng ta thay đổi mặt hàng hơn và chúng ta lặp lại quá trình cho đến khi chúng tôi có mảng mới của chúng tôi. Thời gian chạy của thuật toán này là gì? Vâng, chúng ta hãy xem xét tác động của điều này. Chúng tôi đang thay đổi từng yếu tố. Khi chúng tôi loại bỏ điều này tôi, chúng tôi đang thay đổi tất cả các yếu tố sau khi nó sang bên trái. Và đó là một chi phí O (n) bởi vì những gì nếu chúng ta loại bỏ các yếu tố đầu tiên? Vì vậy, đối với mỗi loại bỏ, chúng tôi loại bỏ - loại bỏ từng phải gánh chịu một O (n) hoạt động, và vì chúng ta có n ñuoåi, điều này dẫn đến một shuffle (n ^ 2) O. Okay. Vì vậy, khởi đầu tốt đẹp. Khởi đầu tốt đẹp. 

Đề nghị khác là sử dụng một cái gì đó được gọi là shuffle Knuth, hoặc shuffle Fisher-Yates. Và nó thực sự là một shuffle thời gian tuyến tính. Và ý tưởng là rất giống nhau. Một lần nữa, chúng ta có mảng đầu vào của chúng tôi, nhưng thay vì sử dụng hai mảng đầu vào / đầu ra của chúng tôi, chúng tôi sử dụng phần đầu tiên của mảng để theo dõi các phần xáo trộn của chúng tôi, và chúng tôi tiếp tục theo dõi, và sau đó chúng tôi rời khỏi phần còn lại của mảng của chúng tôi cho phần unshuffled. Vì vậy, đây là những gì tôi có ý nghĩa. Chúng tôi bắt đầu với chúng tôi chọn một i, một mảng từ 0 đến 20. Con trỏ hiện tại của chúng tôi là chỉ để chỉ số đầu tiên. Chúng tôi chọn một số ở đây tôi và bây giờ chúng tôi trao đổi. Vì vậy, nếu đây là 5 và điều này là 4, các mảng kết quả sẽ có 5 ở đây và 4 ở đây. Và bây giờ chúng tôi lưu ý một điểm đánh dấu ở đây. Tất cả mọi thứ ở bên trái được xáo trộn, và tất cả mọi thứ bên phải unshuffled. Và bây giờ chúng ta có thể lặp lại quá trình. Chúng tôi chọn một chỉ số ngẫu nhiên giữa 1 và 20. Vì vậy, giả mới của chúng tôi là ở đây. Bây giờ chúng ta trao đổi này tôi với vị trí mới của chúng tôi hiện tại ở đây. Vì vậy, chúng tôi trao đổi qua lại như thế này. Hãy để tôi đưa lên các mã để làm cho nó cụ thể hơn. Chúng tôi bắt đầu với sự lựa chọn của tôi - chúng tôi bắt đầu với tôi bằng 0, chúng tôi chọn một vị trí ngẫu nhiên j trong phần unshuffled của mảng, i đến n-1. Vì vậy, nếu tôi ở đây, hãy chọn một chỉ số ngẫu nhiên từ đây và phần còn lại của mảng, và chúng tôi trao đổi. Đây là tất cả các mã cần thiết để shuffle mảng của bạn. Bất kỳ câu hỏi nào? 

Vâng, một cần câu hỏi là, tại sao điều này là đúng? Tại sao là mỗi hoán vị đều có khả năng? Và tôi sẽ không đi qua các bằng chứng của điều này, nhưng nhiều vấn đề trong khoa học máy tính có thể được chứng minh thông qua cảm ứng. Có bao nhiêu bạn đã quen thuộc với cảm ứng? Okay. Cool. Vì vậy, bạn có thể chứng minh sự đúng đắn của thuật toán này bằng cảm ứng đơn giản, giả thuyết cảm ứng của bạn sẽ được, giả định rằng ngẫu nhiên của tôi trả về mọi khả năng hoán vị như nhau đến các yếu tố tôi lần đầu tiên. Bây giờ, hãy xem xét i + 1. Và bằng cách này chúng ta chọn j chỉ mục của chúng tôi để trao đổi, điều này dẫn đến - và sau đó bạn làm việc ra các chi tiết, ít nhất một bằng chứng đầy đủ về lý do tại sao thuật toán này trả về mỗi hoán vị với xác suất đều có khả năng. 

Tất cả các vấn đề, ngay bên cạnh. Vì vậy, "cho một mảng các số nguyên, postive, zero, tiêu cực, viết một chức năng mà tính toán số tiền tối đa của bất kỳ subarray continueous của mảng đầu vào ". Một ví dụ ở đây là, trong trường hợp tất cả các số là tích cực, sau đó hiện nay là lựa chọn tốt nhất là lấy toàn bộ mảng. 1, 2, 3, 4, tương đương với 10. Khi bạn có một số nhược điểm trong đó, trong trường hợp này, chúng tôi chỉ muốn lần đầu tiên hai bởi vì chọn -1 và / hoặc -3 sẽ mang lại tổng hợp của chúng tôi xuống. Đôi khi chúng ta có thể phải bắt đầu ở giữa của mảng. Đôi khi chúng ta muốn chọn không có gì cả, tốt nhất là không có bất cứ điều gì. Và đôi khi nó là tốt hơn để có mùa thu, bởi vì điều sau khi nó là siêu lớn. Vì vậy, bất kỳ ý tưởng? (Học ​​sinh, không thể hiểu được) >> Yeah. Giả sử tôi không dùng -1. Sau đó tôi chọn 1.000 và 20.000, hoặc tôi chỉ chọn các 3 tỷ đồng. Vâng, sự lựa chọn tốt nhất là để có tất cả các số. Này -1, mặc dù là tiêu cực, toàn bộ số tiền là tốt hơn so với tôi không để -1. Vì vậy, một trong những thủ thuật tôi đã đề cập trước đó là nhà nước rõ ràng rõ ràng và các giải pháp bạo lực đầu tiên. Giải pháp bạo lực trong vấn đề này là gì? Yeah? [Jane] Vâng, tôi nghĩ rằng giải pháp sức mạnh vũ phu sẽ được gắn lên tất cả các kết hợp có thể (không thể hiểu). [Yu] Okay. Vì vậy, ý tưởng của Jane là có thể tận dụng mọi - Tôi diễn giải là để có mỗi mảng con có thể liên tục, tính toán tổng hợp của nó, và sau đó lấy tối đa của tất cả các subarrays liên tục có thể. Điều gì xác định duy nhất một mảng con trong mảng đầu vào của tôi? Giống như, hai điều tôi cần? Yeah? (Học ​​sinh, không thể hiểu được) >> phải. Một hạn thấp hơn trên các chỉ số và một chỉ số trên ràng buộc duy nhất quyết định một subarray liên tục. [Nữ sinh viên] Chúng ta ước tính nó là một mảng của các con số duy nhất? [Yu] số Vì vậy, câu hỏi của cô, chúng ta giả sử mảng của chúng tôi - là mảng của chúng tôi tất cả các con số duy nhất, và câu trả lời là không. 

Nếu chúng ta sử dụng giải pháp bạo lực của chúng tôi, sau đó các chỉ số bắt đầu / kết thúc duy nhất quyết định subarray liên tục của chúng tôi. Vì vậy, nếu chúng ta lặp lại cho tất cả các mục bắt đầu có thể, và cho tất cả các mục cuối> hoặc = để bắt đầu, và <n, bạn tính toán số tiền, và sau đó chúng tôi lấy tổng tối đa chúng tôi đã nhìn thấy cho đến nay. Điều này rõ ràng không? O lớn của giải pháp này là gì? Timewise. Không khá n ^ 2. Lưu ý rằng chúng ta lặp đi lặp lại từ 0 đến n, vì vậy đó là một vòng lặp for. Chúng tôi lặp lại từ đầu đến cuối, một cho vòng lặp. Và bây giờ, trong đó, chúng ta phải tổng hợp tất cả các mục, vì vậy đó là một vòng lặp for. Vì vậy, chúng tôi có ba lồng nhau cho các vòng, n ^ 3. Okay. Điều này như là một điểm khởi đầu. Giải pháp của chúng tôi là không tồi tệ hơn n ^ 3. Có tất cả mọi người hiểu các giải pháp bạo lực? 

Okay. Một giải pháp tốt hơn là sử dụng một ý tưởng được gọi là lập trình năng động. Nếu bạn lấy CS124, đó là thuật toán và cấu trúc dữ liệu, bạn sẽ trở nên rất quen thuộc với kỹ thuật này. Và ý tưởng là, cố gắng để xây dựng các giải pháp cho các vấn đề nhỏ hơn đầu tiên. Những gì tôi có ý nghĩa bởi đây là, chúng tôi hiện đang phải lo lắng về hai điều: bắt đầu và kết thúc. Và đó là gây phiền nhiễu. Điều gì xảy ra nếu chúng ta có thể thoát khỏi một trong những thông số? Một ý tưởng là - chúng ta cho vấn đề ban đầu của chúng tôi, tìm số tiền tối đa của bất kỳ subarray trong một phạm vi [O, n-1]. Và bây giờ chúng tôi có một subproblem mới, nơi mà chúng tôi biết, chỉ số hiện tại của chúng tôi, chúng ta biết chúng ta phải kết thúc ở đó. Subarray của chúng ta phải kết thúc ở chỉ số hiện tại. Vì vậy, vấn đề còn lại là, chúng ta nên bắt đầu subarray của chúng tôi? Điều này có ý nghĩa? Okay. Vì vậy, tôi đã mã hoá này lên, và chúng ta hãy nhìn vào những gì điều này có nghĩa. Trong codirectory, có một chương trình được gọi là mảng con, và phải mất số hạng mục, và nó trả về tổng subarray tối đa trong danh sách xáo trộn của tôi. Vì vậy, trong trường hợp này, subarray tối đa của chúng tôi là 3. Và đó là thực hiện bằng cách chỉ sử dụng 2 và 1. Chúng ta hãy chạy nó một lần nữa. Đó cũng là 3. Nhưng lần này, lưu ý làm thế nào chúng ta có 3. Chúng tôi đã lấy chúng tôi chỉ mất 3 chính nó bởi vì nó được bao quanh bởi các tiêu cực trên cả hai mặt, mà sẽ mang lại một số tiền <3. Hãy để chạy trên 10 bản ghi. Lần này, nó là 7, chúng tôi mất hàng đầu 3 và 4. Thời gian này, 8, và chúng ta có được bằng cách lấy 1, 4 và 3. Vì vậy, để cung cấp cho bạn một trực giác về cách chúng tôi có thể giải quyết vấn đề này được chuyển đổi, chúng ta hãy nhìn vào subarray này. Chúng tôi đang cho mảng đầu vào này, và chúng tôi biết câu trả lời là 8. Chúng tôi có 1, 4, và 3. Nhưng chúng ta hãy xem làm thế nào chúng ta thực sự có câu trả lời. Hãy xem xét tại subarray tối đa mà kết thúc ở mỗi các chỉ số này. Subarray tối đa có kết thúc tại vị trí đầu tiên là gì? [Sinh viên] không. >> Zero. Chỉ cần không dưới với -5. Ở đây nó sẽ là 0 như. Yeah? (Học ​​sinh, khó hiểu) [Yu] Ồ, xin lỗi, nó là một -3. Vì vậy, đây là một 2, đây là một -3. Okay. Vì vậy, -4, subarray tối đa để kết thúc vị trí đó là những gì nơi -4 là tại? Zero. Một? 1, 5, 8. Bây giờ, tôi phải kết thúc ở vị trí -2 là tại. Vì vậy, 6, 5, 7, và là người cuối cùng là 4. Biết rằng đây là những mục của tôi cho các vấn đề chuyển đổi, nơi tôi phải kết thúc ở mỗi các chỉ số này, thì câu trả lời cuối cùng của tôi chỉ là một quá trình quét qua, và có số lượng tối đa. Vì vậy, trong trường hợp này đó là 8. Điều này ngụ ý rằng subarray tối đa kết thúc vào lúc chỉ số này, và bắt đầu một nơi nào đó trước khi nó. Có tất cả mọi người hiểu điều này subarray chuyển đổi? 

Okay. Vâng, chúng ta hãy tìm ra sự tái phát này. Hãy xem xét các mục đầu tiên. Vì vậy, ở đây nó là 0, 0, 0, 1, 5, 8. Và sau đó là một -2 ở đây, và mang nó xuống đến 6. Vì vậy, nếu tôi gọi là nhập cảnh tại vị trí subproblem (i), làm thế nào tôi có thể sử dụng câu trả lời một subproblem trước để trả lời subproblem này? Nếu tôi nhìn vào, chúng ta hãy nói rằng, cụm từ này. Làm thế nào tôi có thể tính toán các câu trả lời 6 bằng cách nhìn vào một sự kết hợp của các mảng này và các câu trả lời cho các vấn đề phụ trước trong mảng này? Vâng? [Nữ sinh viên] Bạn lấy mảng của các khoản tiền ở vị trí ngay trước khi nó, do đó, 8, và sau đó bạn thêm subproblem hiện tại. [Yu] Vì vậy, đề nghị của cô là nhìn vào hai con số, con số này và con số này. Vì vậy, đây 8 đề cập đến câu trả lời cho các subproblem (i - 1). Và chúng ta hãy gọi A. mảng đầu vào của tôi Để tìm ra một subarray tối đa kết thúc ở vị trí i, Tôi có hai lựa chọn: Tôi có thể tiếp tục subarray kết thúc ở chỉ số trước đó, hoặc bắt đầu một mảng mới. Nếu tôi được tiếp tục subarray bắt đầu tại chỉ mục trước, sau đó số tiền tối đa tôi có thể đạt được là câu trả lời đến subproblem trước cộng với các mục nhập mảng hiện hành. Nhưng, tôi cũng có sự lựa chọn bắt đầu một subarray mới, trong trường hợp số tiền là 0. Vì vậy, câu trả lời là tối đa từ 0, subproblem i - 1, cộng với mảng các mục nhập hiện tại. Điều này tái phát có ý nghĩa? Tái phát của chúng tôi, như chúng tôi chỉ phát hiện ra, là subproblem i bằng tối đa của subproblem trước cộng với nhập cảnh hiện mảng của tôi, có nghĩa là tiếp tục subarray trước đó, hoặc 0, bắt đầu một subarray mới tại chỉ số hiện tại của tôi. Và một khi chúng ta đã xây dựng được bảng của các giải pháp này, thì câu trả lời cuối cùng của chúng tôi, chỉ cần làm một quét tuyến tính trên mảng subproblem và có số lượng tối đa. Đây là một thực hiện chính xác những gì tôi vừa nói. Vì vậy, chúng tôi tạo ra một mảng subproblem mới, vấn đề phụ. Mục đầu tiên hoặc là 0 hoặc nhập cảnh đầu tiên, tối đa hai người. Và đối với phần còn lại của subproblems chúng tôi sử dụng chính xác sự tái phát, chúng tôi chỉ phát hiện ra. Bây giờ chúng ta tính toán tối đa của mảng subproblems của chúng tôi, và đó là câu trả lời cuối cùng của chúng tôi. 

Vì vậy, bao nhiêu không gian chúng ta sử dụng trong thuật toán này? Nếu bạn chỉ lấy CS50, sau đó bạn có thể không đã thảo luận không gian rất nhiều. Vâng, có một điều cần lưu ý mà tôi gọi là malloc đây với kích thước n. Điều đó không có đề nghị gì với bạn? Thuật toán này sử dụng không gian tuyến tính. Chúng ta có thể làm tốt hơn? Có bất cứ điều gì mà bạn thấy là không cần thiết để tính toán các câu trả lời cuối cùng? Tôi đoán một câu hỏi tốt hơn, những thông tin sao chúng ta không cần phải mang theo tất cả các cách thông qua vào cuối? Bây giờ, nếu chúng ta nhìn vào hai dòng, chúng tôi chỉ quan tâm về subproblem trước, và chúng tôi chỉ quan tâm về tối đa mà chúng tôi từng thấy cho đến nay. Để tính toán câu trả lời cuối cùng của chúng tôi, chúng tôi không cần toàn bộ mảng. Chúng tôi chỉ cần số cuối cùng, hai con số cuối cùng. Số cuối cùng cho các mảng subproblem, và số cuối cùng cho tối đa. Vì vậy, trong thực tế, chúng ta có thể hợp những vòng lặp với nhau và đi từ không gian tuyến tính hằng số không gian. Hiện tại số tiền cho đến nay, ở đây, thay thế vai trò của subproblem, mảng subproblem của chúng tôi. Tóm lại, vì vậy hiện tại cho đến nay, là câu trả lời đến subproblem trước. Và số tiền đó, cho đến nay, có những nơi tối đa của chúng tôi. Chúng tôi tính toán tối đa khi chúng ta đi. Và do đó, chúng tôi đi từ không gian tuyến tính không gian liên tục, và chúng tôi cũng có một giải pháp tuyến tính cho vấn đề subarray của chúng tôi. 

Những loại câu hỏi này, bạn sẽ nhận được trong một cuộc phỏng vấn. Sự phức tạp thời gian là gì, sự phức tạp không gian là những gì? Bạn có thể làm tốt hơn? Có những thứ không cần thiết để giữ cho xung quanh không? Tôi đã làm điều này để làm nổi bật các phân tích mà bạn nên dùng trên của riêng bạn như bạn đang làm việc thông qua những vấn đề này. Luôn luôn tự hỏi, "Tôi có thể làm tốt hơn?" Trong thực tế, chúng ta có thể làm tốt hơn thế này? Sắp xếp của một câu hỏi trick. Bạn không thể, bởi vì bạn cần ít nhất là đọc các đầu vào cho vấn đề này. Vì vậy, thực tế là bạn cần phải ít nhất là đọc đầu vào cho vấn đề này có nghĩa là bạn không thể làm tốt hơn so với thời gian tuyến tính, và bạn không thể làm tốt hơn so với hằng số không gian. Vì vậy, đây là, trên thực tế, giải pháp tốt nhất cho vấn đề này. Câu hỏi? Okay. 

Vấn đề thị trường chứng khoán: "Cho một mảng các số nguyên n, tích cực, bằng không, hay tiêu cực, đại diện cho giá của một cổ phiếu so với ngày n, viết một hàm để tính toán lợi nhuận tối đa mà bạn có thể làm cho cho rằng bạn mua và bán đúng 1 cổ phiếu trong những ngày n. " Về cơ bản, chúng tôi muốn mua thấp, bán cao. Và chúng tôi muốn tìm ra lợi nhuận tốt nhất chúng tôi có thể làm cho. Trở lại với tip của tôi, là những gì, câu trả lời đơn giản ngay lập tức rõ ràng, nhưng nó chậm? Vâng? (Học ​​sinh, không thể hiểu được) >>. >> Vì vậy, bạn sẽ chỉ đi mặc dù và nhìn vào giá cổ phiếu tại mỗi điểm trong thời gian, (khó hiểu). [Yu] Được rồi, vì vậy cô giải pháp đề nghị của máy tính thấp nhất và tính toán cao nhất không nhất thiết phải làm việc bởi vì cao nhất có thể xảy ra trước khi mức thấp nhất. Vì vậy, giải pháp bạo lực cho vấn đề này là gì? Hai điều mà tôi cần để xác định lợi nhuận thực hiện là gì? Đúng. Các giải pháp bạo lực - oh, vì vậy, đề nghị của George là chúng ta chỉ cần hai ngày để xác định lợi nhuận của hai ngày. Vì vậy, chúng tôi tính toán mỗi cặp, như mua / bán, tính toán lợi nhuận, mà có thể là tiêu cực hay tích cực hoặc không. Tính lợi nhuận tối đa mà chúng tôi thực hiện sau khi iterating trên tất cả các cặp ngày. Đó sẽ là câu trả lời cuối cùng của chúng tôi. Và giải pháp đó sẽ là O (n ^ 2), bởi vì có n chọn hai cặp - ngày mà bạn có thể lựa chọn trong số các ngày cuối. Được rồi, vì vậy tôi sẽ không đi qua các giải pháp bạo lực ở đây. Tôi sẽ để cho bạn biết rằng có một giải pháp log n n. Những thuật toán nào bạn đang biết đó là n log n? Nó không phải là một câu hỏi trick. 

Kết hợp các phân loại. Kết hợp các loại n log n, và trong thực tế, một cách giải quyết vấn đề này là sử dụng một loại sắp xếp hợp nhất của ý tưởng được gọi là, nói chung, phân chia và chinh phục. Và ý tưởng là như sau. Bạn muốn tính toán mua / bán cặp trong nửa trái. Tìm lợi nhuận tốt nhất bạn có thể làm, chỉ cần với n đầu tiên trong hai ngày. Sau đó, bạn muốn oompute mua / bán cặp trên nửa bên phải, n cuối cùng trong hai ngày. Và bây giờ, câu hỏi là, làm thế nào để chúng ta hợp nhất các giải pháp trở lại với nhau? Vâng? (Học ​​sinh, khó hiểu) >> Okay. Vì vậy, hãy để tôi vẽ một bức tranh. Vâng? (George, khó hiểu) >> Chính xác. Giải pháp của George là chính xác. Vì vậy, đề nghị của ông là, lần đầu tiên tính toán các cặp mua / bán hàng tốt nhất, và xảy ra ở nửa bên trái, do đó, chúng ta hãy gọi đó là bên trái, bên trái. Tốt nhất mua / bán cặp xảy ra trong nửa bên phải. Nhưng nếu chúng ta chỉ so sánh hai con số này, chúng tôi đang thiếu trường hợp nơi chúng tôi mua và bán một nơi nào đó trong nửa bên phải. Chúng tôi mua ở nửa bên trái, bán trong nửa bên phải. Và cách tốt nhất để tính toán các cặp mua / bán hàng tốt nhất mà kéo dài cả hai nửa là để tính toán tối thiểu ở đây và tính toán tối đa ở đây và có sự khác biệt của họ. Vì vậy, hai trường hợp nơi mà các cặp mua / bán chỉ xảy ra ở đây, chỉ ở đây, hoặc trên cả hai nửa được xác định bởi ba con số. Vì vậy, thuật toán của chúng tôi kết hợp các giải pháp của chúng tôi trở lại với nhau, chúng tôi muốn để tính toán các cặp mua / bán hàng tốt nhất nơi mà chúng tôi mua nửa trái và bán trên nửa bên phải. Và cách tốt nhất để làm điều đó là để tính toán mức giá thấp nhất trong nửa đầu, mức giá cao nhất trong nửa bên phải, và sự khác biệt của họ. Ba lợi nhuận kết quả, ba con số này, bạn nên tận dụng tối đa trong ba, và đó là lợi nhuận tốt nhất bạn có thể làm trong những ngày đầu tiên và kết thúc. Những dòng quan trọng trong màu đỏ. Đây là một cuộc gọi đệ quy để tính toán các câu trả lời trong nửa trái. Đây là một cuộc gọi đệ quy để tính toán các câu trả lời trong nửa bên phải. Hai cho các vòng tính toán min và max trên nửa bên trái và bên phải, tương ứng. Bây giờ tôi tính toán lợi nhuận mà kéo dài cả hai nửa, và câu trả lời cuối cùng là tối đa của ba. Okay. 

Vì vậy, chắc chắn, chúng tôi có một thuật toán, nhưng câu hỏi lớn hơn là, phức tạp thời gian của việc này là gì? Và lý do tại sao tôi đã đề cập hợp nhất loại là hình thức phân chia các câu trả lời thành hai và sau đó sáp nhập các giải pháp của chúng tôi trở lại với nhau chính là hình thức của loại hợp nhất. Vì vậy, hãy để tôi đi qua thời gian. Nếu chúng ta định nghĩa một t chức năng (n) là số lượng các bước n ngày, hai cuộc gọi đệ quy của chúng tôi mỗi chi phí t (n / 2), và có hai trong số các cuộc gọi. Bây giờ tôi cần phải tính toán tối thiểu là nửa trái, mà tôi có thể làm trong n / thời gian 2, cộng thêm tối đa là nửa bên phải. Vì vậy, đây chỉ là n. Và sau đó cộng với một số công việc liên tục. Và phương trình này tái phát chính là phương trình tái phát cho loại hợp nhất. Và tất cả chúng ta đều biết rằng loại hợp nhất là n log n thời gian. Do đó, thuật toán của chúng tôi cũng n log n thời gian. Điều này lặp đi lặp lại làm cho tinh thần? Chỉ cần một bản tóm tắt ngắn gọn về điều này: T (n) là số lượng các bước để tính toán lợi nhuận tối đa trong quá trình ngày n. Cách chúng tôi chia tay cuộc gọi đệ quy của chúng tôi là bằng cách gọi giải pháp của chúng tôi trong những ngày đầu tiên của n / 2, vì vậy đó là một cuộc gọi, và sau đó chúng tôi gọi lại vào nửa thứ hai. Vì vậy, đó là hai cuộc gọi. Và sau đó chúng tôi tìm thấy một tối thiểu trên nửa bên trái, mà chúng tôi có thể làm trong thời gian tuyến tính, tìm tối đa của nửa bên phải, mà chúng tôi có thể làm trong thời gian tuyến tính. Vì vậy, n / 2 + n / 2 chỉ là n. Sau đó, chúng tôi có một số công việc liên tục, mà là giống như làm số học. Phương trình này tái phát là chính xác phương trình tái phát cho loại hợp nhất. Do đó, thuật toán shuffle của chúng tôi cũng là n log n. Vì vậy, bao nhiêu không gian chúng ta đang sử dụng? Hãy để quay trở lại với các mã. 

Một câu hỏi tốt hơn, có bao nhiêu khung stack chúng ta đã từng có tại bất kỳ thời điểm nào? Vì chúng ta đang sử dụng đệ quy, số lượng các khung stack quyết định sử dụng không gian của chúng tôi. Hãy xem xét n = 8. Chúng tôi kêu gọi shuffle vào ngày 8, mà sẽ gọi shuffle trên bốn mục đầu tiên, mà sẽ gọi một shuffle trên hai mục đầu tiên. Vì vậy, ngăn xếp của chúng tôi là - điều này là chồng của chúng tôi. Và sau đó chúng tôi gọi ngẫu nhiên một lần nữa vào ngày 1, và đó là trường hợp cơ sở của chúng tôi là gì, vì vậy chúng tôi trở lại ngay lập tức. Chúng ta có bao giờ có nhiều hơn nhiều các khung stack? Số Bởi vì mỗi lần chúng ta làm một lời gọi, một lời gọi đệ quy để shuffle, chúng tôi chia kích thước của chúng tôi một nửa. Vì vậy, số lượng tối đa của các khung stack, chúng tôi đã từng có tại bất kỳ thời điểm nào là thứ tự của khung log n ngăn xếp. Mỗi stack frame có không gian liên tục, và do đó tổng số tiền của không gian, số tiền tối đa không gian chúng ta bao giờ sử dụng là O (log n) không gian trong đó n là số ngày. 

Bây giờ, luôn luôn tự hỏi mình, "Chúng ta có thể làm tốt hơn?" Và đặc biệt, chúng ta có thể làm giảm đến một vấn đề chúng tôi đã giải quyết? Một gợi ý: chúng tôi chỉ thảo luận về hai vấn đề khác trước khi điều này, và nó sẽ không phải là ngẫu nhiên. Chúng tôi có thể chuyển đổi vấn đề này thị trường chứng khoán vào các vấn đề subarray tối đa. Làm thế nào chúng ta có thể làm điều này? Một trong các bạn? Emmy? (Emmy, khó hiểu) [Yu] Chính xác. Vì vậy, các vấn đề subarray tối đa, chúng tôi đang tìm kiếm một khoản tiền trong một subarray liên tục. Và Emmy đề nghị cho các vấn đề cổ phiếu, xem xét các thay đổi, hoặc các vùng đồng bằng. Và một bức hình của việc này là - điều này là giá của một cổ phiếu, nhưng nếu chúng ta mất sự khác biệt giữa mỗi ngày liên tiếp - vì vậy chúng tôi thấy rằng mức giá tối đa, tối đa lợi nhuận, chúng tôi có thể làm cho là nếu chúng tôi mua ở đây và bán ở đây. Nhưng chúng ta hãy nhìn vào liên tục - chúng ta hãy nhìn vào các vấn đề subarray. Vì vậy, ở đây, chúng ta có thể đi từ đây đến đây, chúng tôi có một sự thay đổi tích cực, và sau đó đi từ đây đến đây chúng ta có một sự thay đổi tiêu cực. Nhưng sau đó, đi từ đây đến đây chúng ta có một sự thay đổi lớn tích cực. Và đây là những thay đổi mà chúng tôi muốn tổng hợp để có được lợi nhuận cuối cùng của chúng tôi. Sau đó, chúng tôi có những thay đổi tiêu cực hơn ở đây. Chìa khóa để giảm thiểu vấn đề kho của chúng tôi vào vấn đề subarray tối đa của chúng tôi là để xem xét các vùng đồng bằng giữa ngày. Vì vậy, chúng tôi tạo ra một mảng mới được gọi là đồng bằng châu thổ, khởi tạo các mục nhập đầu tiên là 0, và sau đó cho mỗi đồng bằng (i), để điều đó là sự khác biệt mảng của tôi đầu vào (i), và mảng (i - 1). Sau đó, chúng ta gọi là thủ tục thường lệ của chúng tôi cho một subarray tối đa đi qua trong một mảng của đồng bằng. Và bởi vì tối đa subarray là tuyến tính thời gian, và điều này giảm, quá trình này tạo ra mảng này đồng bằng, cũng là tuyến tính thời gian, sau đó là giải pháp cuối cùng đối với cổ phiếu là O (n) làm việc cộng với O (n) làm việc, vẫn còn O (n) làm việc. Vì vậy, chúng tôi có một thời gian tuyến tính, giải pháp cho vấn đề của chúng tôi. Có tất cả mọi người hiểu điều này chuyển đổi? 

Nói chung, một ý tưởng tốt mà bạn nên luôn luôn có là cố gắng giảm bớt một vấn đề mới mà bạn đang nhìn thấy. Nếu nó có vẻ quen thuộc với một vấn đề cũ, hãy thử làm giảm nó một vấn đề cũ. Và nếu bạn có thể sử dụng tất cả các công cụ mà bạn đã sử dụng trên các vấn đề cũ để giải quyết vấn đề mới. Vì vậy, để kết thúc, các cuộc phỏng vấn kỹ thuật đang thách thức. Những vấn đề này có thể là một số trong những vấn đề khó khăn hơn mà bạn có thể nhìn thấy trong một cuộc phỏng vấn, do đó, nếu bạn không hiểu tất cả các vấn đề mà tôi chỉ được bảo hiểm, đó là okay. Đây là một số trong những vấn đề khó khăn hơn. Thực hành, thực hành, thực hành. Tôi đã đưa ra rất nhiều vấn đề trong tài liệu, vì vậy chắc chắn kiểm tra. Và may mắn trên các cuộc phỏng vấn của bạn. Tất cả các nguồn lực của tôi được đăng tại liên kết này, và một trong những người bạn cấp cao của tôi đã được cung cấp để làm cuộc phỏng vấn kỹ thuật mô hình, vì vậy nếu bạn quan tâm, email Will Yao tại địa chỉ email. Nếu bạn có một số câu hỏi, bạn có thể hỏi tôi. Bạn có câu hỏi cụ thể liên quan đến phỏng vấn kỹ thuật hoặc bất kỳ vấn đề chúng tôi đã nhìn thấy cho đến nay? Okay. Vâng, chúc may mắn trên các cuộc phỏng vấn của bạn. [CS50.TV]