Tôi có thể sử dụng JavaScript cho cuộc phỏng vấn mã hóa Amazon không?

Back in 2017, I went through some coding interviews and got offers from several large tech companies. So at that point, I decided to share what I'd learned in this article

And I've just updated it for 2022 so it'll be super useful and relevant if you're job hunting now

Despite scoring decent grades in both my CS101 Algorithm class and my Data Structures class in university, I shudder at the thought of going through a coding interview that focuses on algorithms

Hence I spent the last three months figuring out how to improve my coding interview skills and eventually received offers from big tech companies like Google, Facebook, Airbnb, Lyft, Dropbox and more

In this post, I’ll be sharing the insights and tips I gained along the way. Experienced candidates can also expect System Design questions, but that is out of the scope of this post

Many of the algorithmic concepts tested in coding interviews are not what I usually use at work, where I am a Front End Engineer (web). Naturally, I have forgotten quite a bit about these algorithms and data structures, which I learned mostly during my freshmen and sophomore years of college

It’s stressful to have to produce (working) code in an interview, while someone scrutinizes every keystroke that you make. What’s worse is that as an interviewee, you’re encouraged to communicate your thought process out loud to the interviewer

I used to think that being able to think, code, and communicate simultaneously was an impossible feat, until I realized that most people are just not good at coding interviews when they first start out. Interviewing is a skill that you can get better at by studying, preparing, and practicing for it

My recent job search has led me on a journey to improve my coding interview skills. Front End Engineers like to rant about how the current hiring process is broken because technical interviews can include skills not related to front-end development. For example, writing a maze solving algorithm and merging two sorted lists of numbers. Bản thân là một Front End Engineer, tôi có thể đồng cảm với họ

Front end is a specialized domain where engineers have to care about many issues related to browser compatibilities, the Document Object Model, JavaScript performance, CSS layouts, and so on. It is uncommon for front-end engineers to implement some of the complex algorithms tested in interviews

At companies like Facebook and Google, the people are software engineers first, domain experts second

Unfortunately, rules are set by the companies, not the candidates. There is a high emphasis on general computer science concepts like algorithms, design patterns, data structures; core skills that a good software engineer should possess. If you want the job, you have to play by the rules set by the game masters — improve your coding interview skills

This post is structured into the following two sections. Feel free to skip ahead to the section that interests you

• The breakdown of coding interviews, and how to prepare for them
• Helpful tips and hints for each algorithm topic (arrays, trees, dynamic programming, etc. ), along with recommended LeetCode practice questions to review core concepts and to improve on those topics

The content for this post can be found here. I'll make updates there when necessary

If you are interested in Front End content, check out my front end interview handbook here

Picking a programming language

Before anything else, you need to pick a programming language for your algorithmic coding interview

Most companies will allow you to code in the language of your choice. The only exception I know is Google. They allow their candidates to pick from only Java, C++, Python, Go or JavaScript

For the most part, I recommend using a language that you are extremely familiar with, rather than one that is new to you but that the company uses widely

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ư len(), for .. in ... và ký hiệu cắt trên các chuỗi (chuỗi, danh sách và bộ dữ liệu). Lấy phần tử cuối cùng trong một chuỗi là arr[-1] và đảo ngược nó chỉ đơn giản là arr[::-1]. Bạn có thể đạt được rất nhiều với cú pháp tối thiểu trong Python

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 được 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ì chọn 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

yangshunGitHub

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 sort() của ngôn ngữ và sự phức tạp về thời gian và không gian của nó (trong Python đó là Timsort, là dạng kết hợp)

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 từng 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. Explain the time and space complexities and clarify why it is bad. 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?" . This means they are looking for a more optimal approach

This is usually the hardest part of the interview. In general, look for repeated work and try to optimize them by potentially caching the calculated result somewhere. Reference it later, rather than computing it all over again. 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

Only start coding after you and your interviewer have agreed on an approach and you have been given the green light

Starting to code

Use a good style to write your code. Đọ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 tiến bộ hơ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à thực hành đủ để thực hiện các cuộc phỏng vấn giả định, 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])]

0,______0_______1 và

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])]

2

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])]

3 và

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])]

4 trong bộ đệm LRU

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])]

5 , điều này không áp dụng cho mọi trường hợp

Sự liên 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.

  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])]

  6
• Đặt bit thứ k.

  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])]

  7
• Tắt bit thứ k.

  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])]

  8
• Chuyển đổi bit thứ k.

  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])]

  9
• Để kiểm tra xem một số có phải là lũy thừa của 2 không.

  rows, cols = len(matrix), len(matrix[0])
  copy = [[0 for _ in range(cols)] for _ in range(rows)

  0

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 có. 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 traverse(matrix):
  rows, cols = len(matrix), len(matrix[0])
  visited = set()
  directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
  def dfs(i, j):
    if (i, j) in visited:
      return
    visited.add((i, j))
    # Traverse neighbors
    for direction in directions:
      next_i, next_j = i + direction[0], j + direction[1]
      if 0 <= next_i < rows and 0 <= next_j < cols: # Check boundary
        # Add any other checking here ^
        dfs(next_i, next_j)
  for i in range(rows):
    for j in range(cols):
      dfs(i, j)

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.

rows, cols = len(matrix), len(matrix[0])
copy = [[0 for _ in range(cols)] for _ in range(rows)

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

rows, cols = len(matrix), len(matrix[0])
copy = [[0 for _ in range(cols)] for _ in range(rows)

2 và

rows, cols = len(matrix), len(matrix[0])
copy = [[0 for _ in range(cols)] for _ in range(rows)

3 có được coi là khoảng thời gian chồng chéo hay không, bởi vì nó ảnh hưởng đến cách bạn sẽ viết kiểm tra bình đẳng của mình

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 danh sách
• Sắp xếp lại danh sách

Toán học

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

rows, cols = len(matrix), len(matrix[0])
copy = [[0 for _ in range(cols)] for _ in range(rows)

• 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à

transposed_matrix = zip(*matrix)

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. 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

rows, cols = len(matrix), len(matrix[0])
copy = [[0 for _ in range(cols)] for _ in range(rows)

4 tích hợp như Python, hãy yêu cầu sử dụng lớp đó để thay thế

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

mask = 0
for c in set(word):
  mask |= (1 << (ord(c) - ord('a')))

Để xác định xem hai chuỗi có ký tự chung hay không, hãy thực hiện

rows, cols = len(matrix), len(matrix[0])
copy = [[0 for _ in range(cols)] for _ in range(rows)

5 trên hai mặt nạ bit. Nếu kết quả khác không,

rows, cols = len(matrix), len(matrix[0])
copy = [[0 for _ in range(cols)] for _ in range(rows)

6 , thì hai chuỗi có các ký tự chung

đả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ủa 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à

rows, cols = len(matrix), len(matrix[0])
copy = [[0 for _ in range(cols)] for _ in range(rows)

7

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 duy nhất một cây. Đặ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

rows, cols = len(matrix), len(matrix[0])
copy = [[0 for _ in range(cols)] for _ in range(rows)

8 và các phương thức

rows, cols = len(matrix), len(matrix[0])
copy = [[0 for _ in range(cols)] for _ in range(rows)

9,

transposed_matrix = zip(*matrix)

0 và

transposed_matrix = zip(*matrix)

1 của nó

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. Iterate through each element, pushing it into the 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
• Find Median from Data Stream

Conclusion

Coding interviews are tough. But fortunately, you can get better at them by studying and practicing for them, and doing mock interviews

To recap, to do well in coding interviews

1. Decide on a programming language
2. Study CS fundamentals
3. Practice solving algorithm questions
4. 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
5. Practice by doing mock technical interviews
6. Interview successfully to get the job

By following these steps, you will improve your coding interview skills, and be one step closer (or probably more) to landing your dream job

All the best

The content for this post can be found here. Future updates will be posted there. Pull requests for suggestions and corrections are welcome

If you enjoyed this article, share it with your friends

You can also follow me on GitHub and Twitter

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

---

Yangshun Tay

Full Front End Stack Engineer at Meta/Facebook

---

If you read this far, tweet to the author to show them you care. Tweet a thanks

Learn to code for free. 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. Get started

Is JavaScript allowed in coding interview?

What type of coding questions asked in Amazon interview?

Are Amazon coding interviews hard?

Chúng tôi có thể sử dụng JavaScript để viết mã không?