Trở lại năm 2017, tôi đã trải qua một số cuộc phỏng vấn về mã hóa và nhận được lời mời từ một số công ty công nghệ lớn. Vì vậy, tại thời điểm đó, tôi quyết định chia sẻ những gì tôi đã học được trong bài viết này
Và tôi vừa cập nhật nó cho năm 2022 nên nó sẽ cực kỳ hữu ích và phù hợp nếu bạn đang tìm việc ngay bây giờ
Mặc dù đạt điểm khá trong cả lớp Thuật toán CS101 và lớp Cấu trúc dữ liệu ở trường đại học, tôi rùng mình khi nghĩ đến việc trải qua một cuộc phỏng vấn mã hóa tập trung vào thuật toán
Do đó, tôi đã dành ba tháng qua để tìm cách cải thiện kỹ năng phỏng vấn mã hóa của mình và cuối cùng đã nhận được lời mời từ các công ty công nghệ lớn như Google, Facebook, Airbnb, Lyft, Dropbox, v.v.
Trong bài đăng này, tôi sẽ chia sẻ những hiểu biết và mẹo mà tôi đã thu được trong quá trình thực hiện. Các ứng viên có kinh nghiệm cũng có thể mong đợi các câu hỏi về Thiết kế hệ thống, nhưng điều đó nằm ngoài phạm vi của bài đăng này
Nhiều khái niệm thuật toán được thử nghiệm trong các cuộc phỏng vấn mã hóa không phải là những gì tôi thường sử dụng tại nơi làm việc, nơi tôi là Kỹ sư giao diện người dùng [web]. Đương nhiên, tôi đã quên khá nhiều về các thuật toán và cấu trúc dữ liệu này, những thứ mà tôi đã học chủ yếu trong thời gian sinh viên năm nhất và năm thứ hai đại học
Thật căng thẳng khi phải tạo mã [đang hoạt động] trong một cuộc phỏng vấn, trong khi ai đó xem xét kỹ lưỡng từng thao tác gõ phím mà bạn thực hiện. Điều tồi tệ hơn là với tư cách là một người được phỏng vấn, bạn được khuyến khích nói to quá trình suy nghĩ của mình với người phỏng vấn
Tôi từng nghĩ rằng có thể suy nghĩ, viết mã và giao tiếp đồng thời là một điều bất khả thi, cho đến khi tôi nhận ra rằng hầu hết mọi người không giỏi trong các cuộc phỏng vấn viết mã khi họ mới bắt đầu. Phỏng vấn là một kỹ năng mà bạn có thể trở nên giỏi hơn bằng cách nghiên cứu, chuẩn bị và thực hành
Quá trình tìm việc gần đây của tôi đã đưa tôi vào hành trình cải thiện kỹ năng phỏng vấn lập trình của mình. Các kỹ sư Front End thích phàn nàn về quy trình tuyển dụng hiện tại bị phá vỡ như thế nào vì các cuộc phỏng vấn kỹ thuật có thể bao gồm các kỹ năng không liên quan đến phát triển front-end. Ví dụ: viết thuật toán giải mê cung và hợp nhất hai danh sách số đã sắp xếp. Bản thân là một Front End Engineer, tôi có thể đồng cảm với họ
Giao diện người dùng là một miền chuyên biệt mà các kỹ sư phải quan tâm đến nhiều vấn đề liên quan đến khả năng tương thích của trình duyệt, Mô hình đối tượng tài liệu, hiệu suất JavaScript, bố cục CSS, v.v. Việc các kỹ sư front-end triển khai một số thuật toán phức tạp được thử nghiệm trong các cuộc phỏng vấn là điều không bình thường
Tại các công ty như Facebook và Google, mọi người trước tiên là kỹ sư phần mềm, sau đó là chuyên gia tên miền
Thật không may, các quy tắc được đặt ra bởi các công ty, không phải các ứng cử viên. Có sự nhấn mạnh cao vào các khái niệm khoa học máy tính nói chung như thuật toán, mẫu thiết kế, cấu trúc dữ liệu; . Nếu bạn muốn có công việc đó, bạn phải chơi theo luật do người điều hành trò chơi đặt ra — cải thiện kỹ năng phỏng vấn lập trình của bạn
Bài đăng này được cấu trúc thành hai phần sau. Vui lòng bỏ qua phần mà bạn quan tâm
- Phân tích các cuộc phỏng vấn mã hóa và cách chuẩn bị cho chúng
- Các mẹo và gợi ý hữu ích cho từng chủ đề thuật toán [mảng, cây, lập trình động, v.v. ], cùng với các câu hỏi thực hành LeetCode được đề xuất để xem lại các khái niệm cốt lõi và cải thiện các chủ đề đó
Nội dung cho bài viết này có thể được tìm thấy ở đây. Tôi sẽ cập nhật ở đó khi cần thiết
Nếu bạn quan tâm đến nội dung Front End, hãy xem sổ tay phỏng vấn front end của tôi tại đây
Lựa chọn ngôn ngữ lập trình
Trước bất cứ điều gì khác, bạn cần chọn một ngôn ngữ lập trình cho cuộc phỏng vấn mã hóa thuật toán của mình
Hầu hết các công ty sẽ cho phép bạn viết mã bằng ngôn ngữ bạn chọn. Ngoại lệ duy nhất tôi biết là Google. Họ cho phép các ứng viên của mình chỉ chọn Java, C ++, Python, Go hoặc JavaScript
Phần lớn, tôi khuyên bạn nên sử dụng ngôn ngữ mà bạn cực kỳ quen thuộc, thay vì ngôn ngữ mới đối với bạn nhưng công ty sử dụng rộng rãi
Có một số ngôn ngữ phù hợp hơn những ngôn ngữ khác cho các cuộc phỏng vấn mã hóa. Sau đó, có một số mà bạn hoàn toàn muốn tránh
Theo kinh nghiệm của tôi với tư cách là một người phỏng vấn, hầu hết các ứng viên chọn Python hoặc Java. Các ngôn ngữ khác thường được chọn bao gồm JavaScript, Ruby và C++. Tôi tuyệt đối sẽ tránh các ngôn ngữ cấp thấp hơn như C hoặc Go, đơn giản vì chúng thiếu các chức năng thư viện và cấu trúc dữ liệu tiêu chuẩn
Cá nhân tôi, Python là lựa chọn thực tế của tôi cho các thuật toán mã hóa trong các cuộc phỏng vấn. Nó ngắn gọn và có một thư viện hàm và cấu trúc dữ liệu khổng lồ
Một trong những lý do hàng đầu mà tôi khuyên dùng Python là nó sử dụng các API nhất quán hoạt động trên các cấu trúc dữ liệu khác nhau, chẳng hạn như
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]Java cũng là một lựa chọn hợp lý. Nhưng vì bạn sẽ phải liên tục khai báo các loại trong mã của mình, điều đó có nghĩa là bạn phải nhập thêm các lần nhấn phím. Điều này sẽ làm chậm tốc độ bạn viết mã và nhập liệu. Vấn đề này sẽ rõ ràng hơn khi bạn phải viết trên bảng trắng trong các cuộc phỏng vấn tại chỗ
Lý do chọn hay không chọn C++ cũng giống Java. Cuối cùng, Python, Java và C ++ là những lựa chọn phù hợp. Nếu bạn đã sử dụng Java một thời gian và không có thời gian để làm quen với ngôn ngữ khác, tôi khuyên bạn nên sử dụng Java thay vì học Python từ đầu. Điều này giúp bạn tránh phải sử dụng một ngôn ngữ cho công việc và một ngôn ngữ khác cho các cuộc phỏng vấn. Hầu hết thời gian, nút cổ chai là ở suy nghĩ chứ không phải ở văn bản
Một ngoại lệ đối với quy ước cho phép ứng viên “chọn bất kỳ ngôn ngữ lập trình nào họ muốn” là khi cuộc phỏng vấn dành cho một vị trí cụ thể theo miền, chẳng hạn như vai trò kỹ sư giao diện người dùng, iOS hoặc Android. Bạn cần làm quen với các thuật toán mã hóa trong JavaScript, Objective-C, Swift và Java tương ứng
Nếu bạn cần sử dụng cấu trúc dữ liệu mà ngôn ngữ đó không hỗ trợ, chẳng hạn như hàng đợi hoặc đống trong JavaScript, hãy hỏi người phỏng vấn xem bạn có thể cho rằng mình có cấu trúc dữ liệu triển khai các phương thức nhất định với độ phức tạp về thời gian được chỉ định không. Nếu việc triển khai cấu trúc dữ liệu đó không quan trọng để giải quyết vấn đề, người phỏng vấn thường sẽ cho phép nó
Trên thực tế, nhận thức được các cấu trúc dữ liệu hiện có và chọn những cấu trúc phù hợp để giải quyết vấn đề hiện tại quan trọng hơn là biết các chi tiết triển khai phức tạp
Xem lại CS101 của bạn
Nếu bạn đã tốt nghiệp đại học một thời gian, bạn nên xem lại các nguyên tắc cơ bản của CS. Tôi thích xem lại nó khi tôi thực hành. Tôi lướt qua các ghi chú của mình từ trường đại học và sửa lại các thuật toán khác nhau khi tôi giải quyết các vấn đề về thuật toán từ LeetCode và Cracking the Coding Interview
Nếu bạn quan tâm đến cách triển khai cấu trúc dữ liệu, hãy xem Lago, kho lưu trữ GitHub chứa các ví dụ về Cấu trúc dữ liệu và thuật toán trong JavaScript
GitHub - yangshun/lago. 📕 Thư viện Cấu trúc dữ liệu và thuật toán trong TypeScript
📕 Thư viện thuật toán và cấu trúc dữ liệu trong TypeScript - GitHub - yangshun/lago. 📕 Thư viện Cấu trúc dữ liệu và thuật toán trong TypeScript
Làm chủ thông qua thực hành
Tiếp theo, làm quen và thành thạo các thuật toán và cấu trúc dữ liệu trong ngôn ngữ lập trình bạn đã chọn
Thực hành và giải các câu hỏi thuật toán bằng ngôn ngữ bạn chọn. Mặc dù Cracking the Coding Interview là một nguồn tài nguyên tốt, nhưng tôi thích giải quyết vấn đề bằng cách nhập mã, để mã chạy và nhận phản hồi ngay lập tức
Có nhiều Thẩm phán trực tuyến khác nhau, chẳng hạn như LeetCode, HackerRank và CodeForces để bạn thực hành các câu hỏi trực tuyến và làm quen với ngôn ngữ. Theo kinh nghiệm của tôi, các câu hỏi LeetCode gần giống nhất với các câu hỏi được hỏi trong các cuộc phỏng vấn. Các câu hỏi của HackerRank và CodeForces giống với các câu hỏi trong lập trình cạnh tranh hơn
Nếu bạn thực hành đủ các câu hỏi LeetCode, rất có thể bạn sẽ xem hoặc hoàn thành một trong những câu hỏi phỏng vấn thực tế của mình [hoặc một số biến thể của nó]
Tìm hiểu và hiểu sự phức tạp về thời gian và không gian của các hoạt động phổ biến bằng ngôn ngữ bạn đã chọn. Đối với Python, trang này sẽ có ích. Ngoài ra, hãy tìm hiểu về thuật toán sắp xếp cơ bản đang được sử dụng trong hàm
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]Sau khi hoàn thành một câu hỏi trên LeetCode, tôi thường thêm độ phức tạp về thời gian và không gian của mã được viết dưới dạng nhận xét phía trên thân hàm. Tôi sử dụng các nhận xét để nhắc nhở bản thân truyền đạt phân tích về thuật toán sau khi tôi đã hoàn thành việc triển khai
Đọc về phong cách mã hóa được đề xuất cho ngôn ngữ của bạn và tuân theo nó. Nếu bạn chọn Python, hãy tham khảo PEP 8 Style Guide. Nếu bạn chọn Java, hãy tham khảo Google’s Java Style Guide
Tìm hiểu và làm quen với những cạm bẫy và cảnh báo phổ biến của ngôn ngữ. Nếu bạn chỉ ra chúng trong cuộc phỏng vấn và tránh rơi vào chúng, bạn sẽ kiếm được điểm thưởng và gây ấn tượng với người phỏng vấn, bất kể người phỏng vấn có quen thuộc với ngôn ngữ đó hay không
Có được sự tiếp xúc rộng rãi với các câu hỏi từ các chủ đề khác nhau. Trong nửa sau của bài viết, tôi đề cập đến các chủ đề thuật toán và các câu hỏi hữu ích cho mỗi chủ đề để thực hành. Làm khoảng 100 đến 200 câu hỏi LeetCode và bạn sẽ giỏi
Nếu bạn thích các khóa học có cấu trúc hơn, đây là một số đề xuất. Không có cách nào để tham gia các khóa học trực tuyến để vượt qua các cuộc phỏng vấn
- AlgoMonster nhằm mục đích giúp bạn vượt qua cuộc phỏng vấn kỹ thuật trong thời gian ngắn nhất có thể. Bởi các kỹ sư của Google, AlgoMonster sử dụng phương pháp tiếp cận dựa trên dữ liệu để dạy cho bạn các mẫu câu hỏi quan trọng hữu ích nhất và có nội dung giúp bạn nhanh chóng sửa đổi các thuật toán và cấu trúc dữ liệu cơ bản. Trên hết, AlgoMonster không dựa trên đăng ký - trả phí một lần và có quyền truy cập trọn đời
- Grokking cuộc phỏng vấn viết mã. Các mẫu cho câu hỏi viết mã của Educative mở rộng các câu hỏi thực hành được đề xuất trong bài viết này nhưng tiếp cận việc thực hành từ góc độ mẫu câu hỏi, đây là cách tiếp cận mà tôi cũng đồng ý với việc học và cá nhân đã sử dụng để cải thiện các cuộc phỏng vấn viết mã. Khóa học cho phép bạn thực hành các câu hỏi được chọn bằng Java, Python, C ++, JavaScript và cũng cung cấp các giải pháp mẫu bằng các ngôn ngữ đó. Học và hiểu các mẫu, không ghi nhớ câu trả lời
Và tất nhiên, luyện tập, luyện tập và luyện tập nhiều hơn nữa
Các giai đoạn của một cuộc phỏng vấn mã hóa
Xin chúc mừng, bạn đã sẵn sàng để thực hành các kỹ năng của mình. Trong một cuộc phỏng vấn viết mã, bạn sẽ được người phỏng vấn đưa ra một câu hỏi kỹ thuật. Bạn sẽ viết mã trong thời gian thực, trình chỉnh sửa cộng tác [màn hình điện thoại] hoặc trên bảng trắng [tại chỗ] và có 30 đến 45 phút để giải quyết vấn đề. Đây là nơi niềm vui thực sự bắt đầu
Người phỏng vấn của bạn sẽ muốn thấy rằng bạn đáp ứng các yêu cầu của vai trò. Việc cho họ thấy rằng bạn có những kỹ năng là tùy thuộc vào bạn. Ban đầu, bạn có thể cảm thấy lạ khi vừa nói vừa viết mã, vì hầu hết các lập trình viên không có thói quen giải thích thành tiếng những suy nghĩ của họ khi họ đang gõ mã.
Tuy nhiên, người phỏng vấn khó có thể biết bạn đang nghĩ gì nếu chỉ nhìn vào mã của bạn. Nếu bạn truyền đạt cách tiếp cận của mình cho người phỏng vấn ngay cả trước khi bạn bắt đầu viết mã, bạn có thể xác thực cách tiếp cận của mình với họ. Bằng cách này, hai bạn có thể đồng ý về một cách tiếp cận có thể chấp nhận được
Chuẩn bị cho một cuộc phỏng vấn từ xa
Đối với màn hình điện thoại và các cuộc phỏng vấn từ xa, hãy chuẩn bị sẵn giấy và bút hoặc bút chì để ghi lại bất kỳ ghi chú hoặc sơ đồ nào. Nếu bạn được đưa ra một câu hỏi về cây và biểu đồ, nó thường giúp ích nếu bạn vẽ các ví dụ về cấu trúc dữ liệu
sử dụng tai nghe. Hãy chắc chắn rằng bạn đang ở trong một môi trường yên tĩnh. Bạn không muốn cầm điện thoại bằng một tay và gõ bằng tay kia. Cố gắng tránh sử dụng loa. Nếu thông tin phản hồi là xấu, giao tiếp được thực hiện khó khăn hơn. Phải lặp lại chính mình sẽ chỉ làm mất thời gian quý báu
Phải làm gì khi bạn nhận được câu hỏi
Nhiều ứng viên bắt đầu code ngay khi nghe câu hỏi. Đó thường là một sai lầm lớn. Đầu tiên, hãy dành một chút thời gian và lặp lại câu hỏi cho người phỏng vấn để đảm bảo rằng bạn hiểu câu hỏi. Nếu bạn hiểu sai câu hỏi, thì người phỏng vấn có thể làm rõ
Luôn tìm cách giải thích rõ ràng về câu hỏi khi nghe nó, ngay cả khi bạn nghĩ rằng nó đã rõ ràng. Bạn có thể phát hiện ra rằng bạn đã bỏ lỡ điều gì đó. Nó cũng cho người phỏng vấn biết rằng bạn chú ý đến chi tiết
Cân nhắc hỏi những câu hỏi sau
- Kích thước của đầu vào lớn như thế nào?
- Phạm vi của các giá trị lớn như thế nào?
- Có những loại giá trị nào?
- Có trùng lặp trong đầu vào?
- một số trường hợp cực đoan của đầu vào là gì?
- Đầu vào được lưu trữ như thế nào?
Sau khi bạn đã làm rõ đầy đủ phạm vi và mục đích của vấn đề, hãy giải thích cách tiếp cận cấp cao của bạn cho người phỏng vấn, ngay cả khi đó là một giải pháp ngây thơ. Nếu bạn gặp khó khăn, hãy xem xét nhiều cách tiếp cận khác nhau và giải thích rõ ràng lý do tại sao nó có thể hiệu quả hoặc không hiệu quả. Đôi khi người phỏng vấn của bạn có thể đưa ra gợi ý và dẫn bạn đi đúng hướng
Bắt đầu với cách tiếp cận vũ phu. Truyền đạt nó cho người phỏng vấn. Giải thích sự phức tạp về thời gian và không gian và làm rõ lý do tại sao nó xấu. Không chắc rằng cách tiếp cận vũ phu sẽ là cách bạn sẽ viết mã. Tại thời điểm này, người phỏng vấn thường sẽ bật ra câu hỏi đáng sợ, "Chúng ta có thể làm tốt hơn không?" . Điều này có nghĩa là họ đang tìm kiếm một cách tiếp cận tối ưu hơn
Đây thường là phần khó nhất của cuộc phỏng vấn. Nói chung, hãy tìm công việc lặp đi lặp lại và cố gắng tối ưu hóa chúng bằng cách lưu trữ kết quả tính toán vào bộ nhớ cache ở đâu đó. Tham khảo nó sau, thay vì tính toán lại từ đầu. Tôi cung cấp một số mẹo để giải quyết các câu hỏi theo chủ đề cụ thể một cách chi tiết bên dưới
Chỉ bắt đầu viết mã sau khi bạn và người phỏng vấn của bạn đã đồng ý về cách tiếp cận và bạn đã được bật đèn xanh
Bắt đầu viết mã
Sử dụng một phong cách tốt để viết mã của bạn. Đọc mã do người khác viết thường không phải là một nhiệm vụ thú vị. Đọc mã được định dạng khủng khiếp do người khác viết thậm chí còn tệ hơn. Mục tiêu của bạn là làm cho người phỏng vấn hiểu mã của bạn để họ có thể nhanh chóng đánh giá xem mã của bạn có hoạt động như những gì nó được cho là không và liệu nó có giải quyết được một vấn đề nhất định hay không.
Sử dụng các tên biến rõ ràng và tránh các tên có các chữ cái đơn lẻ, trừ khi chúng dùng để lặp lại. Tuy nhiên, nếu bạn đang viết mã trên bảng trắng, hãy tránh sử dụng tên biến dài dòng. Điều này làm giảm số lượng văn bản bạn sẽ phải làm
Luôn giải thích cho người phỏng vấn những gì bạn đang viết hoặc đánh máy. Đây không phải là việc đọc, nguyên văn, cho người phỏng vấn mã bạn đang sản xuất. Nói về phần mã bạn hiện đang triển khai ở cấp độ cao hơn. Giải thích tại sao nó được viết như vậy, và nó đang cố gắng đạt được điều gì
Khi bạn sao chép và dán mã, hãy cân nhắc xem có cần thiết không. Đôi khi nó được, đôi khi nó không. Nếu bạn thấy mình đang sao chép và dán một đoạn mã lớn trải rộng trên nhiều dòng, thì đó có thể là dấu hiệu cho thấy bạn có thể cấu trúc lại mã bằng cách trích xuất các dòng đó thành một hàm. Nếu nó chỉ là một dòng bạn đã sao chép, thường thì không sao cả
Tuy nhiên, hãy nhớ thay đổi các biến tương ứng trong dòng mã được sao chép của bạn khi có liên quan. Lỗi sao chép và dán là một nguồn lỗi phổ biến, ngay cả trong mã hóa hàng ngày
Sau khi mã hóa
Sau khi bạn mã hóa xong, đừng thông báo ngay với người phỏng vấn rằng bạn đã hoàn thành. Trong hầu hết các trường hợp, mã của bạn thường không hoàn hảo. Nó có thể chứa lỗi hoặc lỗi cú pháp. Điều bạn cần làm là xem lại mã của mình
Đầu tiên, xem qua mã của bạn từ đầu đến cuối. Hãy nhìn nó như thể nó được viết bởi người khác, và bạn đang nhìn thấy nó lần đầu tiên và cố gắng phát hiện lỗi trong đó. Đó chính xác là những gì người phỏng vấn của bạn sẽ làm. Xem xét và khắc phục mọi vấn đề bạn có thể tìm thấy
Tiếp theo, hãy đưa ra các trường hợp thử nghiệm nhỏ và xem qua mã [không phải thuật toán của bạn] với các đầu vào mẫu đó
Người phỏng vấn thích nó khi bạn đọc được suy nghĩ của họ. Điều họ thường làm sau khi bạn viết mã xong là yêu cầu bạn viết bài kiểm tra. Sẽ là một điểm cộng rất lớn nếu bạn viết các bài kiểm tra cho mã của mình ngay cả trước khi họ nhắc bạn làm như vậy. Bạn nên mô phỏng trình gỡ lỗi khi xem qua mã của mình. Ghi lại hoặc cho họ biết giá trị của một số biến nhất định khi bạn hướng dẫn người phỏng vấn qua các dòng mã
Nếu có nhiều đoạn mã trùng lặp lớn trong giải pháp của bạn, hãy cấu trúc lại mã để cho người phỏng vấn thấy rằng bạn đánh giá cao chất lượng mã hóa. Ngoài ra, hãy tìm những nơi bạn có thể thực hiện đánh giá ngắn mạch
Cuối cùng, hãy đưa ra độ phức tạp về thời gian và không gian của mã của bạn và giải thích tại sao nó lại như vậy. Bạn có thể chú thích các đoạn mã của mình với độ phức tạp về thời gian và không gian khác nhau của chúng để thể hiện sự hiểu biết của bạn về mã. Bạn thậm chí có thể cung cấp API của ngôn ngữ lập trình bạn đã chọn. Giải thích bất kỳ sự đánh đổi nào trong cách tiếp cận hiện tại của bạn so với các cách tiếp cận thay thế, có thể về mặt thời gian và không gian
Nếu người phỏng vấn của bạn hài lòng với giải pháp, cuộc phỏng vấn thường kết thúc tại đây. Người phỏng vấn cũng thường hỏi bạn các câu hỏi mở rộng, chẳng hạn như bạn sẽ xử lý vấn đề như thế nào nếu toàn bộ thông tin đầu vào quá lớn để vừa với bộ nhớ hoặc nếu thông tin đầu vào đến dưới dạng một luồng. Đây là một câu hỏi tiếp theo phổ biến tại Google, nơi họ quan tâm rất nhiều đến quy mô
Câu trả lời thường là cách tiếp cận chia để trị - thực hiện xử lý dữ liệu phân tán và chỉ đọc một số đoạn nhất định của đầu vào từ đĩa vào bộ nhớ, ghi đầu ra trở lại đĩa và kết hợp chúng sau.
Thực hành với các cuộc phỏng vấn giả
Các bước được đề cập ở trên có thể được lặp đi lặp lại nhiều lần cho đến khi bạn hoàn toàn tiếp thu chúng và chúng trở thành bản chất thứ hai đối với bạn. Một cách tốt để thực hành là hợp tác với một người bạn và thay phiên nhau phỏng vấn lẫn nhau
Một nguồn tuyệt vời để chuẩn bị cho các cuộc phỏng vấn mã hóa là phỏng vấn. io. Nền tảng này cung cấp các cuộc phỏng vấn thực hành miễn phí và ẩn danh với các kỹ sư của Google và Facebook, điều này có thể dẫn đến các công việc thực tế và cơ hội thực tập
Nhờ ẩn danh trong cuộc phỏng vấn, quá trình phỏng vấn toàn diện là không thiên vị và rủi ro thấp. Vào cuối cuộc phỏng vấn, cả người phỏng vấn và người được phỏng vấn có thể cung cấp phản hồi cho nhau nhằm mục đích giúp nhau cải thiện
Làm tốt các cuộc phỏng vấn giả sẽ mở khóa trang việc làm cho các ứng viên và cho phép họ đặt lịch phỏng vấn [cũng ẩn danh] với các công ty hàng đầu như Uber, Lyft, Quora, Asana, v.v. Đối với những người chưa quen với các cuộc phỏng vấn mã hóa, có thể xem một cuộc phỏng vấn demo trên trang web này. Lưu ý rằng trang web này yêu cầu người dùng đăng nhập
Tôi đã sử dụng phỏng vấn. io, cả với tư cách là người phỏng vấn và người được phỏng vấn. Trải nghiệm thật tuyệt. Aline Lerner, CEO và đồng sáng lập phỏng vấn. io và nhóm của cô ấy đam mê cách mạng hóa quy trình phỏng vấn mã hóa và giúp các ứng viên cải thiện kỹ năng phỏng vấn của họ
Cô ấy cũng đã xuất bản một số bài báo liên quan đến phỏng vấn mã hóa trên cuộc phỏng vấn. blog io. Tôi khuyên bạn nên đăng ký càng sớm càng tốt với cuộc phỏng vấn. io, mặc dù đang trong giai đoạn thử nghiệm, để tăng khả năng nhận được lời mời
Một nền tảng khác cho phép bạn thực hành các cuộc phỏng vấn mã hóa là Pramp. phỏng vấn ở đâu. io phù hợp với những người tìm việc tiềm năng với những người phỏng vấn lập trình dày dạn kinh nghiệm, Pramp có một cách tiếp cận khác. Pramp ghép bạn với một đồng nghiệp khác cũng đang tìm việc. Hai bạn lần lượt đóng vai người phỏng vấn và người được phỏng vấn. Pramp cũng chuẩn bị các câu hỏi, cung cấp các giải pháp và lời nhắc để hướng dẫn người được phỏng vấn
Tiến lên và chinh phục
Sau khi thực hiện khá nhiều câu hỏi trên LeetCode và có đủ thực hành phỏng vấn giả, hãy tiếp tục và thử nghiệm các kỹ năng phỏng vấn mới tìm được của bạn
Ứng tuyển vào các công ty yêu thích của bạn hoặc tốt hơn nữa là nhận được sự giới thiệu từ bạn bè của bạn đang làm việc cho các công ty đó. Người được giới thiệu có xu hướng được chú ý sớm hơn và có tỷ lệ phản hồi nhanh hơn so với việc nộp đơn mà không có người giới thiệu. Chúc may mắn
Mẹo thiết thực cho câu hỏi mã hóa
Phần này đi sâu vào các mẹo thực tế cho các chủ đề cụ thể về thuật toán và cấu trúc dữ liệu, thường xuất hiện trong các câu hỏi viết mã. Nhiều câu hỏi về thuật toán liên quan đến các kỹ thuật có thể áp dụng cho các câu hỏi có tính chất tương tự
Bạn càng có nhiều kỹ thuật trong kho vũ khí của mình, cơ hội vượt qua cuộc phỏng vấn của bạn càng cao. Đối với mỗi chủ đề, cũng có một danh sách các câu hỏi được đề xuất, rất có giá trị để nắm vững các khái niệm cốt lõi. Một số câu hỏi chỉ có sẵn khi đăng ký LeetCode trả phí, theo tôi, điều này hoàn toàn xứng đáng với số tiền bỏ ra nếu nó mang lại cho bạn một công việc
Mẹo chung
Luôn xác thực đầu vào trước. Kiểm tra các đầu vào không hợp lệ, trống, phủ định hoặc khác. Đừng bao giờ cho rằng bạn được cung cấp các thông số hợp lệ. Ngoài ra, hãy làm rõ với người phỏng vấn liệu bạn có thể cho rằng đầu vào hợp lệ hay không [thường là có], điều này có thể giúp bạn tiết kiệm thời gian viết mã xác thực đầu vào
Có bất kỳ yêu cầu hoặc hạn chế nào về độ phức tạp về thời gian và không gian không?
Kiểm tra lỗi từng cái một
Trong các ngôn ngữ không có ép kiểu tự động, hãy kiểm tra xem việc nối các giá trị có cùng kiểu không.
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]Sau khi bạn hoàn thành mã của mình, hãy sử dụng một vài ví dụ đầu vào để kiểm tra giải pháp của bạn
Thuật toán có phải chạy nhiều lần không, có lẽ trên máy chủ web?
Sử dụng kết hợp các mô hình lập trình chức năng và mệnh lệnh
- Viết các hàm thuần túy càng thường xuyên càng tốt
- Sử dụng các hàm thuần túy vì chúng dễ lập luận hơn và có thể giúp giảm lỗi trong quá trình triển khai của bạn
- Tránh thay đổi các tham số được truyền vào hàm của bạn, đặc biệt nếu chúng được truyền theo tham chiếu, trừ khi bạn chắc chắn về những gì mình đang làm
- Đạt được sự cân bằng giữa độ chính xác và hiệu quả. Sử dụng đúng số lượng mã chức năng và mệnh lệnh khi thích hợp. Lập trình chức năng thường tốn kém về độ phức tạp không gian do không đột biến và phân bổ lặp lại các đối tượng mới. Mặt khác, mã mệnh lệnh nhanh hơn vì bạn thao tác trên các đối tượng hiện có
- Tránh dựa vào các biến toàn cục đột biến. Biến toàn cầu giới thiệu trạng thái
- Đảm bảo rằng bạn không vô tình thay đổi các biến toàn cục, đặc biệt nếu bạn phải dựa vào chúng
Nói chung, để cải thiện tốc độ của chương trình, chúng ta có thể chọn sử dụng cấu trúc dữ liệu hoặc thuật toán thích hợp hoặc sử dụng nhiều bộ nhớ hơn. Đó là một sự đánh đổi không gian và thời gian cổ điển
Cấu trúc dữ liệu là vũ khí của bạn. Chọn vũ khí phù hợp cho trận chiến phù hợp là chìa khóa để chiến thắng. Biết điểm mạnh của từng cấu trúc dữ liệu và độ phức tạp về thời gian cho các hoạt động khác nhau của nó
Cấu trúc dữ liệu có thể được tăng cường để đạt được độ phức tạp về thời gian hiệu quả trong các hoạt động khác nhau. Ví dụ: HashMap có thể được sử dụng cùng với danh sách liên kết kép để đạt được độ phức tạp thời gian O[1] cho cả hoạt động
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]HashMaps có lẽ là cấu trúc dữ liệu được sử dụng phổ biến nhất cho các câu hỏi về thuật toán. Nếu bạn gặp khó khăn trong một câu hỏi, giải pháp cuối cùng của bạn có thể là liệt kê các cấu trúc dữ liệu có thể [rất may là không có nhiều] và xem xét liệu từng cấu trúc trong số chúng có thể được áp dụng cho vấn đề hay không. Điều này đã làm việc cho tôi vào những thời điểm
Nếu bạn đang cắt xén mã của mình, hãy nói to điều đó với người phỏng vấn và giải thích cho họ những gì bạn sẽ làm bên ngoài môi trường phỏng vấn [không giới hạn thời gian]. Ví dụ: giải thích rằng bạn sẽ viết biểu thức chính quy để phân tích chuỗi thay vì sử dụng
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]Sự nối tiếp
ghi chú
Mảng và chuỗi được coi là chuỗi [một chuỗi là một chuỗi các ký tự]. Có các mẹo để xử lý cả mảng và chuỗi, sẽ được đề cập ở đây
Có các giá trị trùng lặp trong chuỗi không?
Kiểm tra trình tự ngoài giới hạn
Hãy chú ý đến việc cắt hoặc nối các chuỗi trong mã của bạn. Thông thường, các chuỗi cắt và nối yêu cầu thời gian O[n]. Sử dụng các chỉ số bắt đầu và kết thúc để phân định một mảng con hoặc chuỗi con nếu có thể
Đôi khi bạn đi qua trình tự từ phía bên phải chứ không phải từ bên trái
Nắm vững kỹ thuật cửa sổ trượt áp dụng cho nhiều bài toán về chuỗi con hoặc mảng con
Khi bạn được cung cấp hai chuỗi để xử lý, thông thường sẽ có một chỉ mục cho mỗi chuỗi để duyệt qua. Ví dụ: chúng tôi sử dụng cùng một cách tiếp cận để hợp nhất hai mảng đã sắp xếp
Trường hợp góc
- trình tự trống
- Dãy có 1 hoặc 2 phần tử
- Trình tự có các phần tử lặp lại
Mảng
ghi chú
Là mảng được sắp xếp hoặc sắp xếp một phần? . Điều này thường có nghĩa là người phỏng vấn đang tìm kiếm một giải pháp nhanh hơn O[n]
Bạn có thể sắp xếp mảng không? . Đảm bảo rằng thứ tự của các phần tử mảng không cần phải được giữ nguyên trước khi cố gắng sắp xếp nó
Đối với các câu hỏi liên quan đến tổng hoặc nhân của một mảng con, việc tính toán trước bằng cách sử dụng hàm băm hoặc tiền tố, tổng hậu tố hoặc tích có thể hữu ích
Nếu bạn được cung cấp một dãy và người phỏng vấn yêu cầu khoảng trống O[1], thì có thể sử dụng chính mảng đó làm bảng băm. Ví dụ: nếu mảng chỉ có các giá trị từ 1 đến N, trong đó N là độ dài của mảng, hãy phủ định giá trị tại chỉ mục đó [trừ một] để biểu thị sự hiện diện của số đó
câu hỏi thực hành
- hai tổng
- Thời điểm tốt nhất để mua và bán cổ phiếu
- Chứa trùng lặp
- Sản phẩm của mảng trừ tự
- Phân đoạn tối đa
- Phân nhóm sản phẩm tối đa
- Tìm giá trị nhỏ nhất trong mảng được sắp xếp xoay
- Tìm kiếm trong mảng được sắp xếp xoay
- 3Sum
- Thùng chứa nhiều nước nhất
nhị phân
liên kết nghiên cứu
- Bit, Byte, Xây dựng Với Nhị phân
ghi chú
Các câu hỏi liên quan đến biểu diễn nhị phân và hoạt động bitwise đôi khi được hỏi. Bạn phải biết cách chuyển đổi một số từ dạng thập phân sang dạng nhị phân và ngược lại, bằng ngôn ngữ lập trình bạn đã chọn
Một số đoạn tiện ích hữu ích
- Bit kiểm tra thứ k được thiết lập.
6def is_overlap[a, b]: return a[0] < b[1] and b[0] < a[1] def merge_overlapping_intervals[a, b]: return [min[a[0], b[0]], max[a[1], b[1]]] - Đặt bit thứ k.
7def is_overlap[a, b]: return a[0] < b[1] and b[0] < a[1] def merge_overlapping_intervals[a, b]: return [min[a[0], b[0]], max[a[1], b[1]]] - Tắt bit thứ k.
8def is_overlap[a, b]: return a[0] < b[1] and b[0] < a[1] def merge_overlapping_intervals[a, b]: return [min[a[0], b[0]], max[a[1], b[1]]] - Chuyển đổi bit thứ k.
9def is_overlap[a, b]: return a[0] < b[1] and b[0] < a[1] def merge_overlapping_intervals[a, b]: return [min[a[0], b[0]], max[a[1], b[1]]] - Để kiểm tra xem một số có phải là lũy thừa của 2 không.
00def is_overlap[a, b]: return a[0] < b[1] and b[0] < a[1] def merge_overlapping_intervals[a, b]: return [min[a[0], b[0]], max[a[1], b[1]]]
Trường hợp góc
- Kiểm tra tràn/tràn
- số âm
câu hỏi thực hành
- Tổng của hai số nguyên
- Số 1 bit
- Đếm Bit
- Thiếu số
- Bit đảo ngược
Lập trình năng động
liên kết nghiên cứu
- Làm sáng tỏ lập trình động
ghi chú
Quy hoạch động [DP] thường được sử dụng để giải các bài toán tối ưu. Alaina Kafkes đã viết một bài tuyệt vời về giải quyết các vấn đề về DP. Bạn nên đọc nó
Cách duy nhất để trở nên giỏi hơn ở DP là luyện tập. Phải thực hành rất nhiều để nhận ra rằng một vấn đề có thể được giải quyết bằng DP
Để tối ưu hóa không gian, đôi khi bạn không cần phải lưu trữ toàn bộ bảng DP trong bộ nhớ. Hai giá trị cuối cùng hoặc hai hàng cuối cùng của ma trận sẽ đủ
câu hỏi thực hành
- 0/1 Ba lô
- Leo cầu thang
- Đổi xu
- Dãy con tăng dài nhất
- Dãy con chung dài nhất
- Lời Break vấn đề
- Tổng kết hợp
- Cướp nhà và Cướp nhà II
- giải mã cách
- Đường dẫn duy nhất
- trò chơi nhảy
hình học
ghi chú
Khi so sánh khoảng cách Euclide giữa hai cặp điểm, sử dụng dx² + dy² là đủ. Không cần thiết phải căn bậc hai giá trị
Để biết hai đường tròn có trùng nhau không, hãy kiểm tra xem khoảng cách giữa hai tâm của hai đường tròn có nhỏ hơn tổng bán kính của chúng không
đồ thị
liên kết nghiên cứu
- Từ lý thuyết đến thực hành. Biểu diễn đồ thị
- Lặn sâu qua đồ thị. Truyền tải DFS
- Đi rộng trong một biểu đồ. Truyền tải BFS
ghi chú
Làm quen với các biểu diễn đồ thị khác nhau và các thuật toán tìm kiếm đồ thị cũng như độ phức tạp về thời gian và không gian của chúng
Bạn có thể được cung cấp một danh sách các cạnh và được giao nhiệm vụ xây dựng biểu đồ của riêng bạn từ các cạnh để thực hiện duyệt trên. Các biểu diễn đồ thị phổ biến là
- Ma trận kề
- danh sách liền kề
- HashMap của HashMaps
Một số đầu vào trông giống như cây, nhưng chúng thực sự là biểu đồ. Làm rõ điều này với người phỏng vấn của bạn. Trong trường hợp đó, bạn sẽ phải xử lý các chu kỳ và giữ một tập hợp các nút đã truy cập khi duyệt qua
Thuật toán tìm kiếm đồ thị
- Phổ thông. Tìm kiếm theo chiều rộng [BFS], tìm kiếm theo chiều sâu [DFS]
- không phổ biến. Sắp xếp tô pô, thuật toán Dijkstra
- Hiếm. Thuật toán Bellman-Ford, thuật toán Floyd-Warshall, thuật toán Prim và thuật toán Kruskal
Trong các cuộc phỏng vấn mã hóa, đồ thị thường được biểu diễn dưới dạng ma trận 2 chiều, trong đó các ô là các nút và mỗi ô có thể đi qua các ô liền kề của nó [lên, xuống, trái và phải]. Do đó, điều quan trọng là phải làm quen với việc duyệt qua ma trận 2 chiều
Khi di chuyển đệ quy qua ma trận, luôn đảm bảo rằng vị trí tiếp theo của bạn nằm trong ranh giới của ma trận. Bạn có thể tìm thêm các mẹo khác để thực hiện DFS trên ma trận tại đây. Một mẫu đơn giản để thực hiện DFS trên ma trận xuất hiện giống như thế này
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]Trường hợp góc
- biểu đồ trống
- Vẽ đồ thị với một hoặc hai nút
- Đồ thị rời rạc
- Vẽ đồ thị có chu kỳ
câu hỏi thực hành
- Nhân bản đồ thị
- Lịch học
- từ điển người ngoài hành tinh
- Dòng nước Thái Bình Dương Đại Tây Dương
- Số đảo
- Vẽ đồ thị cây hợp lệ
- Số lượng các thành phần được kết nối trong một đồ thị vô hướng
- Chuỗi liên tiếp dài nhất
khoảng thời gian
ghi chú
Câu hỏi khoảng là câu hỏi cho mảng gồm hai phần tử [một khoảng]. Hai giá trị đại diện cho một giá trị bắt đầu và một giá trị kết thúc. Các câu hỏi về khoảng thời gian được coi là một phần của họ mảng, nhưng chúng liên quan đến một số kỹ thuật phổ biến. Do đó, họ có phần đặc biệt của riêng mình
Một ví dụ về một mảng khoảng.
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]Các câu hỏi về khoảng thời gian có thể khó đối với những người không có kinh nghiệm với chúng. Điều này là do số lượng lớn các trường hợp cần xem xét khi các mảng khoảng chồng lên nhau
Làm rõ với người phỏng vấn liệu
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]Một thói quen phổ biến cho các câu hỏi về khoảng thời gian là sắp xếp mảng các khoảng thời gian theo giá trị bắt đầu của mỗi khoảng thời gian
Làm quen với việc viết mã để kiểm tra xem hai khoảng có trùng nhau không và hợp nhất hai khoảng trùng nhau
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]Trường hợp góc
- khoảng đơn
- Khoảng cách không chồng chéo
- Một khoảng thời gian hoàn toàn tiêu thụ trong khoảng thời gian khác
- Khoảng thời gian trùng lặp
câu hỏi thực hành
- Chèn khoảng thời gian
- Hợp nhất các khoảng thời gian
- Phòng họp và Phòng họp II
- Khoảng thời gian không chồng chéo
Danh sách liên kết
ghi chú
Giống như mảng, danh sách liên kết được sử dụng để biểu diễn dữ liệu tuần tự. Lợi ích của danh sách liên kết là việc chèn và xóa mã từ bất kỳ đâu trong danh sách là O[1], trong khi trong mảng, các phần tử phải được dịch chuyển
Thêm một nút giả ở đầu và/hoặc đuôi có thể giúp xử lý nhiều trường hợp cạnh trong đó các thao tác phải được thực hiện ở đầu hoặc đuôi. Sự hiện diện của các nút giả đảm bảo rằng các hoạt động sẽ không bao giờ được thực hiện trên đầu hoặc đuôi. Các nút giả loại bỏ sự đau đầu khi viết các kiểm tra có điều kiện để xử lý các con trỏ null. Hãy chắc chắn để loại bỏ chúng khi kết thúc hoạt động
Đôi khi vấn đề danh sách được liên kết có thể được giải quyết mà không cần lưu trữ bổ sung. Thử mượn ý tưởng từ bài toán đảo ngược danh sách liên kết
Để xóa trong danh sách liên kết, bạn có thể sửa đổi giá trị nút hoặc thay đổi con trỏ nút. Bạn có thể cần giữ một tham chiếu đến phần tử trước đó
Để phân vùng danh sách được liên kết, hãy tạo hai danh sách được liên kết riêng biệt và nối chúng lại với nhau
Bài toán danh sách liên kết có những điểm tương đồng với bài toán mảng. Hãy suy nghĩ về cách bạn sẽ giải một bài toán về mảng và áp dụng nó vào danh sách liên kết
Hai cách tiếp cận con trỏ cũng phổ biến cho các danh sách được liên kết
- Lấy thứ k từ nút cuối cùng. Có hai con trỏ, trong đó một con trỏ đi trước k nút. Khi nút phía trước về đích thì nút kia cách k nút phía sau
- Phát hiện chu kỳ. Có hai con trỏ, trong đó một con trỏ tăng gấp đôi so với con trỏ kia. Nếu hai con trỏ gặp nhau, điều đó có nghĩa là có một chu kỳ
- Lấy nút giữa. Có hai con trỏ. Một con trỏ tăng gấp đôi so với con trỏ kia. Khi nút nhanh hơn đến cuối danh sách, nút chậm hơn sẽ ở giữa
Làm quen với các quy trình sau vì nhiều câu hỏi về danh sách liên kết sử dụng một hoặc nhiều quy trình này trong giải pháp của chúng
- Đếm số nút trong danh sách liên kết
- Đảo ngược danh sách liên kết tại chỗ
- Tìm nút giữa của danh sách được liên kết bằng cách sử dụng con trỏ nhanh hoặc chậm
- Hợp nhất hai danh sách lại với nhau
Trường hợp góc
- nút đơn
- Hai nút
- Danh sách liên kết có chu kỳ. Làm rõ với người phỏng vấn liệu có thể có một chu kỳ trong danh sách. Thông thường câu trả lời là không
câu hỏi thực hành
- Đảo ngược danh sách liên kết
- Phát hiện chu kỳ trong danh sách được liên kết
- Hợp nhất hai danh sách được sắp xếp
- Hợp nhất danh sách được sắp xếp K
- Xóa nút thứ N khỏi cuối danh sách
- Sắp xếp lại danh sách
môn Toán
ghi chú
Nếu mã liên quan đến phép chia hoặc modulo, hãy nhớ kiểm tra phép chia hoặc modulo cho 0 trường hợp
Khi một câu hỏi liên quan đến “bội số của một số”, modulo có thể hữu ích
Kiểm tra và xử lý tràn và tràn nếu bạn đang sử dụng một ngôn ngữ đánh máy như Java và C++. Ít nhất, hãy đề cập rằng có thể tràn hoặc tràn và hỏi xem bạn có cần xử lý nó không
Xem xét số âm và số dấu phẩy động. Điều này nghe có vẻ hiển nhiên, nhưng khi bạn gặp áp lực trong một cuộc phỏng vấn, nhiều điểm rõ ràng sẽ không được chú ý
Nếu câu hỏi yêu cầu triển khai một toán tử như lũy thừa, căn bậc hai hoặc phép chia và nó nhanh hơn O[n], tìm kiếm nhị phân thường là cách tiếp cận
Một số công thức thông dụng
- Tổng của 1 đến N = [n+1] * n/2
- Tổng GP = 2⁰ + 2¹ + 2² + 2³ + … 2^n = 2^[n+1]-1
- Hoán vị của N = N. / [NK]
- Sự kết hợp của N = N. / [K. * [NK]. ]
Trường hợp góc
- chia cho 0
- Tràn và tràn số nguyên
câu hỏi thực hành
- Pow[x, n]
- bình phương[x]
- Số nguyên sang từ tiếng Anh
ma trận
ghi chú
Ma trận là một mảng 2 chiều. Các câu hỏi liên quan đến ma trận thường liên quan đến lập trình động hoặc duyệt đồ thị
Đối với các câu hỏi liên quan đến lập trình truyền tải hoặc động, hãy tạo một bản sao của ma trận có cùng kích thước được khởi tạo thành các giá trị trống. Sử dụng các giá trị này để lưu trữ trạng thái đã truy cập hoặc bảng lập trình động. Làm quen với thói quen này
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]- Nhiều trò chơi dựa trên lưới có thể được mô hình hóa dưới dạng ma trận. Ví dụ: Tic-Tac-Toe, Sudoku, Crossword, Connect 4 và Battleship. Không có gì lạ khi được yêu cầu xác minh điều kiện chiến thắng của trò chơi. Đối với các trò chơi như Tic-Tac-Toe, Connect 4 và Crosswords, việc xác minh phải được thực hiện theo chiều dọc và chiều ngang. Một mẹo nhỏ là viết mã để xác minh ma trận cho các ô ngang. Sau đó chuyển đổi vị trí ma trận, sử dụng lại logic được sử dụng để xác minh theo chiều ngang để xác minh các ô dọc ban đầu [hiện đang nằm ngang]
- Chuyển đổi một ma trận trong Python chỉ đơn giản là
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]Trường hợp góc
- ma trận rỗng. Kiểm tra xem không có mảng nào có độ dài bằng 0
- ma trận 1 x 1
- Ma trận chỉ có một hàng hoặc một cột
câu hỏi thực hành
- Đặt Zeroes ma trận
- Ma trận xoắn ốc
- Xoay hình ảnh
- Tìm từ
đệ quy
ghi chú
Đệ quy rất hữu ích cho hoán vị, bởi vì nó tạo ra tất cả các kết hợp và câu hỏi dựa trên cây. Bạn nên biết cách tạo tất cả các hoán vị của một chuỗi cũng như cách xử lý các bản sao
Hãy nhớ luôn xác định trường hợp cơ sở để đệ quy của bạn kết thúc
Đệ quy ngầm sử dụng ngăn xếp. Do đó, tất cả các cách tiếp cận đệ quy có thể được viết lại lặp đi lặp lại bằng cách sử dụng ngăn xếp
Cẩn thận với các trường hợp mức đệ quy quá sâu và gây tràn ngăn xếp [giới hạn mặc định trong Python là 1000]. Bạn có thể nhận được điểm thưởng khi chỉ ra điều này cho người phỏng vấn
Đệ quy sẽ không bao giờ có độ phức tạp không gian O[1] vì có liên quan đến ngăn xếp, trừ khi có tối ưu hóa cuộc gọi đuôi [TCO]. Tìm hiểu xem ngôn ngữ bạn chọn có hỗ trợ TCO không
câu hỏi thực hành
- Tập con và tập con II
- Strobogrammatic số II
Chuỗi
ghi chú
Vui lòng đọc các mẹo trên về trình tự. Chúng cũng áp dụng cho các chuỗi
Hỏi về bộ ký tự đầu vào và phân biệt chữ hoa chữ thường. Thông thường, các ký tự được giới hạn ở các ký tự Latinh viết thường, ví dụ a đến z
Khi bạn cần so sánh các chuỗi trong đó thứ tự không quan trọng [như đảo chữ cái], bạn có thể cân nhắc sử dụng HashMap làm bộ đếm. Nếu ngôn ngữ của bạn có lớp
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]Nếu bạn cần giữ một bộ đếm các ký tự, một lỗi phổ biến là nói rằng độ phức tạp không gian cần thiết cho bộ đếm là O[n]. Không gian cần thiết cho bộ đếm là O[1] chứ không phải O[n]. Điều này là do giới hạn trên là phạm vi ký tự, thường là hằng số cố định là 26. Bộ đầu vào chỉ là các ký tự Latinh viết thường
Các cấu trúc dữ liệu phổ biến để tra cứu chuỗi hiệu quả là
- Trie/Cây tiền tố
- cây hậu tố
Các thuật toán chuỗi phổ biến là
- Rabin Karp, tiến hành tìm kiếm hiệu quả các chuỗi con, sử dụng hàm băm lăn
- KMP, tiến hành tìm kiếm hiệu quả các chuỗi con
Ký tự không lặp lại
Sử dụng mặt nạ bit 26 bit để cho biết ký tự Latinh viết thường nào nằm trong chuỗi
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]Để xác định xem hai chuỗi có ký tự chung hay không, hãy thực hiện
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]đảo ngữ
Đảo ngữ là chuyển từ hoặc chơi chữ. Đó là kết quả của việc sắp xếp lại các chữ cái của một từ hoặc cụm từ để tạo ra một từ hoặc cụm từ mới, trong khi chỉ sử dụng tất cả các chữ cái gốc một lần. Trong các cuộc phỏng vấn, thông thường chúng ta chỉ quan tâm đến những từ không có dấu cách trong đó
Để xác định xem hai chuỗi có đảo chữ cái hay không, có một vài cách tiếp cận hợp lý
- Sắp xếp cả hai chuỗi sẽ tạo ra cùng một chuỗi kết quả. Điều này mất thời gian O[log n] và không gian O[logn]
- Nếu chúng ta ánh xạ từng ký tự thành một số nguyên tố và chúng ta nhân từng số được ánh xạ lại với nhau, đảo chữ cái sẽ có cùng bội số [phân tách thừa số nguyên tố]. Điều này mất O[n] thời gian và O[1] không gian
- Việc đếm tần số của các ký tự sẽ giúp xác định xem hai chuỗi có phải là đảo chữ cái hay không. Điều này cũng mất O[n] thời gian và O[1] không gian
Xuôi ngược đều giống nhau
Palindrome là một từ, cụm từ, số hoặc chuỗi ký tự khác đọc ngược và xuôi giống nhau, chẳng hạn như bà hoặc xe đua
Dưới đây là các cách để xác định xem một chuỗi có phải là một palindrome hay không
- Đảo ngược chuỗi và nó phải bằng chính nó
- Có hai con trỏ ở đầu và cuối chuỗi. Di chuyển các con trỏ vào trong cho đến khi chúng gặp nhau. Tại bất kỳ thời điểm nào, các ký tự ở cả hai con trỏ phải khớp với nhau
Thứ tự các ký tự trong chuỗi quan trọng, vì vậy HashMaps thường không hữu ích
Khi một câu hỏi về việc đếm số lượng palindrome, một thủ thuật phổ biến là có hai con trỏ di chuyển ra ngoài, cách xa phần giữa. Lưu ý rằng palindromes có thể có chiều dài chẵn hoặc lẻ. Đối với mỗi vị trí trục giữa, bạn cần kiểm tra hai lần. Một lần bao gồm ký tự và một lần không có ký tự
- Đối với chuỗi con, bạn có thể kết thúc sớm khi không có kết quả khớp
- Đối với các dãy con, hãy sử dụng quy hoạch động vì có các bài toán con chồng chéo. Kiểm tra câu hỏi này
Trường hợp góc
- chuỗi rỗng
- Chuỗi ký tự đơn
- Các chuỗi chỉ có một ký tự riêng biệt
câu hỏi thực hành
- Chuỗi con dài nhất không có ký tự lặp lại
- Thay thế ký tự lặp lại dài nhất
- Chuỗi con cửa sổ tối thiểu
- Mã hóa và giải mã chuỗi
- Đảo chữ hợp lệ
- đảo ngữ nhóm
- Dấu ngoặc đơn hợp lệ
- Bảng chữ cái hợp lệ
- Chuỗi con Palindrome dài nhất
- Chuỗi con Palindromic
Cây
liên kết nghiên cứu
- Lá nó lên cây nhị phân
ghi chú
Cây là đồ thị tuần hoàn vô hướng và liên thông
Đệ quy là một cách tiếp cận phổ biến cho cây. Khi bạn nhận thấy rằng vấn đề cây con có thể được sử dụng để giải quyết toàn bộ vấn đề, hãy thử sử dụng đệ quy
Khi sử dụng đệ quy, hãy luôn nhớ kiểm tra trường hợp cơ sở, thường là nơi nút là
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]Khi bạn được yêu cầu đi qua một cái cây theo cấp độ, hãy sử dụng tìm kiếm theo chiều sâu trước tiên
Đôi khi có thể hàm đệ quy của bạn cần trả về hai giá trị
Nếu câu hỏi liên quan đến tổng các nút trên đường đi, hãy đảm bảo kiểm tra xem các nút có thể âm hay không
Bạn hẳn đã rất quen thuộc với việc viết đệ quy trình duyệt theo thứ tự trước, theo thứ tự và sau khi đặt hàng. Là một phần mở rộng, hãy thử thách bản thân bằng cách viết chúng lặp đi lặp lại. Đôi khi người phỏng vấn hỏi ứng viên về cách tiếp cận lặp lại, đặc biệt nếu ứng viên viết xong cách tiếp cận đệ quy quá nhanh
Cây nhị phân
Duyệt theo thứ tự của cây nhị phân là không đủ để tuần tự hóa cây một cách duy nhất. Đặt hàng trước hoặc chuyển đổi sau khi đặt hàng cũng được yêu cầu
Cây tìm kiếm nhị phân [BST]
Truyền tải theo thứ tự BST sẽ cung cấp cho bạn tất cả các yếu tố theo thứ tự
Rất quen thuộc với các thuộc tính của BST. Xác thực rằng cây nhị phân là BST. Điều này xuất hiện thường xuyên hơn dự kiến
Khi một câu hỏi liên quan đến BST, người phỏng vấn thường tìm kiếm một giải pháp chạy nhanh hơn O[n]
Trường hợp góc
- cây rỗng
- nút đơn
- Hai nút
- Cây rất lệch [giống như một danh sách liên kết]
câu hỏi thực hành
- Độ sâu tối đa của cây nhị phân
- Cùng Cây
- Đảo ngược hoặc lật cây nhị phân
- Cây nhị phân Tổng đường dẫn tối đa
- Trình duyệt thứ tự cấp độ cây nhị phân
- Tuần tự hóa và giải tuần tự hóa cây nhị phân
- Cây con của cây khác
- Xây dựng cây nhị phân từ Preorder và Inorder Travers
- Xác thực cây tìm kiếm nhị phân
- Phần tử nhỏ thứ K trong BST
- Tổ tiên chung thấp nhất của BST
cố gắng
liên kết nghiên cứu
- Cố gắng hiểu Cố gắng
- Triển khai Trie [Cây tiền tố]
ghi chú
Tries là những cây đặc biệt [cây tiền tố] giúp cho việc tìm kiếm và lưu trữ chuỗi hiệu quả hơn. Tries có nhiều ứng dụng thực tế, chẳng hạn như tiến hành tìm kiếm và cung cấp tính năng tự động hoàn thành. Sẽ rất hữu ích khi biết những ứng dụng phổ biến này để bạn có thể dễ dàng xác định khi nào một vấn đề có thể được giải quyết hiệu quả bằng cách sử dụng bộ ba
Đôi khi tiền xử lý một từ điển các từ [được đưa ra trong một danh sách] thành một bộ ba, sẽ cải thiện hiệu quả của việc tìm kiếm một từ có độ dài k, trong số n từ. Tìm kiếm trở thành O[k] thay vì O[n]
Làm quen với việc triển khai, từ đầu, một lớp
def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]def is_overlap[a, b]:
return a[0] < b[1] and b[0] < a[1]
def merge_overlapping_intervals[a, b]:
return [min[a[0], b[0]], max[a[1], b[1]]]câu hỏi thực hành
- Triển khai Trie [Cây tiền tố]
- Thêm và tìm kiếm từ
- Tìm kiếm từ II
đống
liên kết nghiên cứu
- Học cách yêu đống
ghi chú
Nếu bạn thấy k cao nhất hoặc k thấp nhất được đề cập trong câu hỏi, thì đó thường là dấu hiệu cho thấy có thể sử dụng một đống để giải quyết vấn đề, chẳng hạn như trong Top K Phần tử thường gặp
Nếu bạn yêu cầu k phần tử hàng đầu, hãy sử dụng Heap tối thiểu có kích thước k. Lặp lại qua từng phần tử, đẩy nó vào heap. Bất cứ khi nào kích thước heap vượt quá k, hãy xóa phần tử tối thiểu. Điều đó sẽ đảm bảo rằng bạn có k phần tử lớn nhất
câu hỏi thực hành
- Hợp nhất danh sách được sắp xếp K
- Các phần tử phổ biến hàng đầu K
- Tìm trung vị từ luồng dữ liệu
Phần kết luận
Các cuộc phỏng vấn mã hóa là khó khăn. Nhưng may mắn thay, bạn có thể trở nên giỏi hơn bằng cách nghiên cứu và thực hành chúng, cũng như thực hiện các cuộc phỏng vấn giả
Tóm lại, để làm tốt trong các cuộc phỏng vấn mã hóa
- Quyết định ngôn ngữ lập trình
- Nghiên cứu các nguyên tắc cơ bản của CS
- Thực hành giải các câu hỏi thuật toán
- Tiếp thu những điều nên làm và không nên làm trong các cuộc phỏng vấn
- Thực hành bằng cách thực hiện các cuộc phỏng vấn kỹ thuật giả
- Phỏng vấn thành công để có được công việc
Bằng cách làm theo các bước này, bạn sẽ cải thiện kỹ năng phỏng vấn mã hóa của mình và tiến một bước gần hơn [hoặc có thể hơn thế nữa] để đạt được công việc mơ ước của mình
Tất cả tốt nhất
Nội dung cho bài viết này có thể được tìm thấy ở đây. Cập nhật trong tương lai sẽ được đăng ở đó. Yêu cầu kéo cho các đề xuất và chỉnh sửa được chào đón
Nếu bạn thích bài viết này, hãy chia sẻ nó với bạn bè của bạn
Bạn cũng có thể theo dõi tôi trên GitHub và Twitter
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
Full Front End Stack Engineer tại Meta/Facebook
Nếu bạn đọc đến đây, hãy tweet cho tác giả để cho họ thấy bạn quan tâm. Tweet một lời cảm ơn
Học cách viết mã miễn phí. Chương trình giảng dạy mã nguồn mở của freeCodeCamp đã giúp hơn 40.000 người có được việc làm với tư cách là nhà phát triển. Bắt đầu