Phỏng vấn cấu trúc dữ liệu Python

Tôi đã chuẩn bị cho một số cuộc phỏng vấn tại các công ty công nghệ/tài chính [Google, Goldman Sachs, v.v.]. Tôi là nghiên cứu sinh tiến sĩ khoa học máy tính năm cuối tại Đại học Quốc gia Singapore và bằng tiến sĩ của tôi không có nhiều thành phần lập trình với nó. Trong khi chuẩn bị, tôi đã thu thập một số gợi ý để xem đi xem lại trước cuộc phỏng vấn — vì vậy khi tôi nói “các mẹo chung”, ý tôi là các mẹo để tôi ghi nhớ. Hy vọng nó giúp

• Xem các mẹo phỏng vấn kỹ thuật xuất sắc từ các kỹ sư của Google và các mẹo phỏng vấn từ các nhà tuyển dụng của Google. Không có nhiều công ty nỗ lực nhiều như vậy để làm rõ quy trình phỏng vấn của họ
• Theo dõi khóa học của Udacity về chuẩn bị cho cuộc phỏng vấn kỹ thuật bằng Python. Khóa học này là phiên bản toàn diện về các chi tiết kỹ thuật mà chúng ta sẽ thảo luận ở đây
• Đọc các mẹo rất ngắn gọn của Philip J. Guo và có lẽ còn lang thang trên mạng nữa
• Không mở liên kết từ các bài báo mồi nhấp chuột [e. g. từ businessinsider và forbes]
• Hướng dẫn toàn diện nhất về thực hành lập trình là Google phỏng vấn đại học. Hãy coi nó như một tài liệu tham khảo, đừng để nó choáng ngợp. Tài nguyên cho các câu hỏi thiết kế hệ thống ở đó khá tốt
• Tôi đã sử dụng Python làm ưu tiên đầu tiên của mình. Một số nhân viên của Google đề xuất sử dụng C++/Java, nhưng quyết định nhất trí là. chọn ngôn ngữ mà bạn cảm thấy thoải mái nhất, trừ khi mô tả công việc có yêu cầu. Một huấn luyện viên phỏng vấn chính thức từ Google đảm bảo rằng Python ổn và thường giúp truyền đạt những hiểu biết cơ bản nhanh hơn trong một cuộc phỏng vấn
• Bám sát một nền tảng thực hành phỏng vấn và thực hiện các vấn đề một cách triệt để. Tôi đánh giá cao leetcode. Không sử dụng các nền tảng tập trung vào các cuộc thi lập trình. Nếu bạn đang thực hành phỏng vấn qua điện thoại, hãy sử dụng Google Tài liệu để thực hành rồi sao chép và dán vào nền tảng [hoặc trình chỉnh sửa cá nhân của bạn]. Đối với cuộc phỏng vấn trực tiếp [cả hangout và tại chỗ], hãy thực hành lập trình trên bảng trắng. Lúc đầu nó làm nản lòng, nhưng cũng giúp ích rất nhiều. Nếu bạn có một trình soạn thảo ưa thích với mã linting, tự động điền và những thứ không, đừng mở nó cho đến cuộc phỏng vấn
• Trong cuộc phỏng vấn, hãy đặt câu hỏi và làm rõ từng điều dù nhỏ nhất. Xác thực trước các giả định về cấu trúc dữ liệu và độ phức tạp. Trong tài liệu này, bất cứ khi nào bạn nhìn thấy 🙋, nó sẽ đưa ra một ví dụ về ngữ cảnh mà việc đặt câu hỏi cho người phỏng vấn là phổ biến
• Thực hành mọi vấn đề như thể nó là một cuộc phỏng vấn. Giải quyết chúng càng sớm càng tốt không phải là mục tiêu [trái ngược với các cuộc thi lập trình], giao tiếp mới là chìa khóa. Đừng từ bỏ chính mình. Xem các giải pháp của tôi cho một số vấn đề về leetcode, mỗi vấn đề được giải quyết như thể đó là một cuộc phỏng vấn. Mỗi tệp có các chi tiết được viết dưới dạng nhận xét
• Bắt đầu với việc liệt kê các ví dụ sẽ bao gồm hầu hết các trường hợp cạnh, cực đoan và phổ biến
• Một vài loại vấn đề phổ biến trên tất cả các nền tảng, sách và video liên quan đến phỏng vấn [điều này có thể ngụ ý rằng chúng cũng phổ biến trong các cuộc phỏng vấn]. Bốn loại vấn đề chính mà người ta nên tập trung là. 1. Thao tác chuỗi/mảng, 2. Cấu trúc cây, 3. Cấu trúc đồ thị, 4. thao tác số. Mỗi loại có nhiều loại phụ khác nhau, hãy tìm chúng bên dưới với 💡. Danh sách này là không toàn diện

Đây là lĩnh vực câu hỏi đa dạng nhất có thể và cũng là nguồn câu hỏi dễ. Thật dễ dàng để hỏi và giải thích các câu hỏi liên quan đến chuỗi/mảng qua điện thoại, vì vậy hãy chú ý đến phần này sẽ giúp

Người ta nên biết các thuật toán/cấu trúc sau, độ phức tạp của chúng, ví dụ về các ứng dụng và triển khai

• Sáp nhập từ dưới lên
• Sắp xếp nhanh chóng
• hàng đợi ưu tiên
• Hàng đợi kết thúc kép
• ngăn xếp
• Hoán vị/tổ hợp
• Mảng hậu tố [Manber và Meyers]
• Thuật toán Aho Corasick
• thuật toán KMP

Sau đây là một số loại kỹ thuật có thể sử dụng bất kỳ thuật toán/cấu trúc dữ liệu nào đã nói ở trên

💡 Các vấn đề liên quan đến phân lớp

Cho một mảng thường bao gồm các số nguyên [hiếm khi nó chỉ bao gồm các số nguyên không âm 🙋], một mảng con là một lát liền kề của mảng đó. Hiếm khi nó được phép để trống 🙋. Bạn có thể phải tìm mảng con có tổng lớn nhất [thuật toán Kadane] hoặc sản phẩm tối đa hoặc có thể là mảng con có kích thước tối thiểu có tổng lớn hơn mục tiêu đã cho

Hầu hết các vấn đề phỏng vấn trong thể loại này có thể được giải quyết trong thời gian tuyến tính mà không cần thêm không gian. Thủ thuật thường là giữ một cửa sổ của mảng con và tăng/thu nhỏ mảng con tùy thuộc vào ngữ cảnh. Có thể bạn sẽ phải

• bắt đầu mảng con với kích thước bằng 0 bắt đầu từ bên trái. Thông thường, khi mảng được sắp xếp [hoặc phải được sắp xếp], mảng con có thể bắt đầu dưới dạng mảng đầy đủ, với hai con trỏ ở đầu và cuối thu nhỏ mảng con tùy thuộc vào ngữ cảnh [một loại ví dụ hơi khác. trong một mảng đã sắp xếp, hãy tìm hai giá trị cộng thành một mục tiêu]
• Giữ một giá trị trả lại toàn cầu [e. g. tổng] và một cục bộ. Thường thì bạn có thể phải giữ hai biến cục bộ [e. g. sản phẩm tối thiểu và tối đa]

Nếu nó không có vẻ rõ ràng khi bắt đầu, rất có thể, nó cần giải pháp O[n²] và bạn nên bắt đầu với điều đó càng sớm càng tốt 🙋. Xem liệu bạn có thể sắp xếp mảng và sau đó giải quyết nó bằng các lượt O[n] hay không, do đó đưa ra giải pháp O[n log n] tốt hơn

💡 Các bài toán liên quan đến dãy con

Các dãy con không liền nhau nhưng thứ tự các phần tử trong mảng ban đầu được giữ nguyên. Tìm xem một chuỗi có phải là dãy con của một chuỗi khác hay không là dạng dễ nhất, nhưng bạn có thể phải tìm dãy con chung dài nhất [bài toán lập trình động mà mọi sách giáo khoa đều gặp phải], dãy con tăng dài nhất hoặc dãy con lắc lư dài nhất kỳ quặc. Những bài toán này thường chỉ yêu cầu bạn trả về độ dài của dãy con. Tuy nhiên, một câu hỏi tiếp theo hay là tìm chính dãy con đó. Có thể bạn sẽ phải

• Đầu tiên nêu rõ đệ quy của giải pháp
• Giữ một bộ đệm của các kết quả subarray nhỏ hơn [thuật ngữ ô. lập trình năng động]. Trong Python, bạn có thể sử dụng bộ đệm kiểu trang trí hoạt động cho nhiều vấn đề liên quan đến bộ đệm, nhưng trong các cuộc phỏng vấn, chỉ cần giữ một ma trận/danh sách. Xem một roundup xuất sắc
• Bạn nên mong đợi một giải pháp O[n²], mặc dù một số thuật toán thông minh có thể đạt được giải pháp O[n log n] bằng cách sử dụng các kỹ thuật tìm kiếm nhật ký
• Hãy thử xem các phương pháp tham lam có hoạt động không [chúng thường không hoạt động]

💡 Kỹ thuật tìm kiếm nhật ký

Kỹ thuật tìm kiếm nhật ký là một thuật ngữ tôi vừa tạo ra cho các vấn đề làm giảm ít nhất một O[n] thành O[log n] bằng cách duyệt qua một không gian tìm kiếm, cắt một nửa không gian tìm kiếm ở mỗi bước. Đối với một danh sách, không gian tìm kiếm có thể là tập hợp các chỉ mục hoặc thậm chí là phạm vi giá trị [e. g. nếu các giá trị tối thiểu và tối đa của mảng được biết]. Hình thức phổ biến nhất là tìm kiếm nhị phân trong một mảng được sắp xếp

💡 Các vấn đề liên quan đến khoảng thời gian

Đưa ra một tập hợp các khoảng, vấn đề thường liên quan đến việc hiểu các phần chồng chéo hoặc tìm kích thước tối ưu cho một tính năng nhất định. Hầu như lúc nào bạn cũng cần sắp xếp các khoảng thời gian dựa trên kết thúc [hoặc bắt đầu] của chúng, vì vậy trừ khi một vấn đề rất rõ ràng được hỏi, bạn có thể bắt đầu bằng cách thử giải pháp O[n log n] 🙋. Các cách tiếp cận tham lam thường hoạt động sau đó. Các vấn đề ví dụ bao gồm tìm số lượng khoảng cách tối thiểu cần loại bỏ để làm cho phần còn lại không chồng chéo và số lượng mũi tên tối thiểu cần thiết để làm nổ bóng bay ở chế độ 2D

Hầu hết các vấn đề liên quan đến số là từ toán học rời rạc hoặc thao tác bit

• số học mô-đun
• Nghịch đảo phép nhân mô-đun [khi mô-đun là số nguyên tố]
• Thao tác bit sử dụng toán tử

💡 Kỹ thuật thao tác bit

Trừ khi bạn là người bẩm sinh và/hoặc đã thực hành nhiều, còn không thì khá khó để thực hiện thao tác bit chính xác mà không có sự trợ giúp từ trình biên dịch. Tuy nhiên, ít nhất hãy biết các định nghĩa và thủ thuật rất cơ bản bằng cách sử dụng bit khôn ngoan [khác với thông thường] AND [&], OR [. ], và quan trọng nhất là XOR [^] và dịch chuyển bit [>]. Mẹo cơ bản nên biết [n là số] bao gồm

• n&[n-1] công tắc của bit thiết lập cuối cùng
• n^n hủy tất cả các bit theo cặp. Nó thường hữu ích khi hủy các bản sao [e. g. tìm số duy nhất]. Tuy nhiên, mánh khóe này thường có thể vượt khỏi tầm tay rất nhanh [e. g. tìm một số duy nhất khi mọi phần tử khác xuất hiện ba lần]
• Sử dụng giá trị mặt nạ để tìm bit đã đặt tại chỉ mục nhất định hoặc giới hạn số nguyên ở mức 32 bit [đặc biệt trong Python] 🙋
• Đặc biệt, n&1 là Đúng khi và chỉ khi n là số lẻ

Xem một roundup điên rồ ở đây

Các vấn đề liên quan đến xác suất cơ bản là khá phổ biến. Mặc dù hầu hết các cuộc phỏng vấn lập trình không yêu cầu các câu đố xác suất [các vị trí định lượng trong các tổ chức tài chính có thể yêu cầu], người ta nên biết lấy mẫu hồ chứa, bộ lọc nở hoa và các thuật toán xác suất định hướng cấu trúc dữ liệu tương tự