Getting good at Leetcode

作者: geekzl管理员 发布时间: 2021-10-11 22:10:15 27.82K 人阅读   百度未收录


Getting good at Leetcode

by Heidi Newton


Disclaimer: This post is in no way affiliated with Leetcode, or endorsed by Leetcode. I am just a user/ fan of Leetcode.

Lately, I've had a number of people asking me for advice on how to improve at answering the style of questions found on Leetcode. I'm not an expert in job interviewing—in fact, my experience in it is quite limited. But I think my experiences and improvement with solving Leetcode questions means I can give some useful advice to others. So, for what it's worth, I'm going to share some tips on how I think I've gotten where I have with it.

I started doing Leetcode questions when I wanted to get better at competitive programming, after really enjoying the Google Code Jam (Now called Kick Start) but never doing well beyond the 1st round. Fast forward to a few months later, and I've now solved almost 600 Leetcode questions, with the ultimate goal of solving them all. I take part in the Leetcode weekly competitions, where I have seen my weekly ranks slowly but surely go up. I went from only solving 1 - 3 questions per week, up to more-often-than-not, solving all 4. I went from getting only 5 participation coins per week, to getting 50 most weeks for being in the top 200. Hopefully soon I'll be in the top 100.

So with that, here we go. My 20 best tips that I hope will help you achieve the same!

1. Know your motivations

Why do you want to "get good at Leetcode"? Do you want to get your dream job? Win programming contests? Learn more about algorithms? Without a good motivation, you may struggle. If your only motivation is to get your dream job, then you might also struggle to stay motivated, especially with the "risk" of not getting the job. If you don't enjoy solving the questions, it might not be worth doing the advanced ones. There are plenty of good companies out there where you won't need to be able to solve medium-level and hard-level Leetcode questions to get into them.

So, think about what motivates you, and keep that motivation in mind!

2. Set realistic goals for yourself

Multiple times, I've seen people ask how many questions they should solve in a day. This is the wrong question to ask though. You shouldn't have a number-of-questions-per-day target. Instead, you should decide how much time you are willing and able to put towards your learning, and then make it your goal to use that time as productively as you can, aiming to improve. You can only do your best, and you should be aiming to do your best, so comparing to other people won't be helpful here.

Aim to divide your time between learning new skills, mastering old skills and general problem solving (tackling questions without initially knowing what skills you'll be applying).

3. If you don't have a CS degree, do an online data structures and algorithms course

If it wasn't for the first year data structures and algorithms course I did back when I was in university, I don't think I would have known where to start. Getting started can be daunting, and knowing what exactly to focus on can be even more so. As a rough guide, you'll need a course that takes you over key ideas such as Arrays, Sorting, Searching, Linked Lists, Trees, Graphs, Stacks, Heaps, Queues, Hashing (maps, sets, and dictionaries), Big-O notation, and complexity analysis (cost). By the end of it, you should know the use cases for each data structure, and be able to justify the reasons in terms of cost.

A good online course will have assignments and quizzes that'll help you know whether or not you're on track and picking up the most important ideas. This will then help you as you move towards self-directed learning on more advanced concepts.

There are also many good resources on the more basic programming skills. Find one that suits your style and language of choice. Make sure you can design programs with loops and conditionals (if statements) with ease, as this is central to algorithm design.

4. Find some good resources for learning more advanced algorithms

It really does help to have a good resource to look at when needed. I use the CLRS algorithms book. I'd highly recommend it, either go for the e-book version on Amazon or look for it in the library (if you're a university student with access to a library) if the cost is a concern. The Leetcode Explore modules are fantastic too. Geeks For Geeks also has some useful content, although the writing quality varies a lot and the lack of proofreading on some of the articles can make it painful to read. If you can ignore that, great, if not, then you might need to find another resource. Wikipedia also has some good articles, although quality and clarity varies a lot.

5. Learn techniques, not solutions

I've seen a few people on the Leetcode forums and beyond asking how many Leetcode questions they'd need to have done to have a good chance of seeing all the questions they'll get in their interview, and it amazes me that anybody thinks this is a good idea. Leetcode itself doesn't help the cause by providing lists of questions sorted by company (for subscribers).

If in an interview you've already seen the question, it'd be dishonest to pretend you hadn't. You'd also have to be pretty good at faking the “solving a novel problem” thought process your interviewer is looking for.

Instead, you should be aiming to do enough questions to learn about the common data structures, algorithms, and techniques that you're likely to need to use. Your goal is to get yourself to a point where if you're given a problem you've never seen before, you can work through it and decide which data structures, algorithms, and techniques you could apply to solve it. It will take a lot of practice to get to this point, and sometimes there'll be a question where it takes you a few minutes to even know where to start. But the more you learn and practice, the better you will become.

6. Learn the fundamental data structures (Basic)

These next 3 points are concerned with specific concepts you'll need to learn. I've split them into 3 general categories, based on difficulty and how often they tend to come up. I'd recommend mastering all in one category before moving up to the next. The lists aren't exhaustive, and the order isn't absolute, but this is roughly the order I worked on learning and mastering concepts.

If you have a lot of trouble with even the simplest questions in the fundamental data structures section (some are hard, I'm not saying you have to find them all easy!), then you might need to find an introduction to data structures and algorithms course to work through. Most of these topics have a Leetcode Explore module, I highly recommend using them. After that, find more problems by searching the problem list by the relevant tag. Focus mostly on easy-level questions for now.

  • Arrays and Strings: Leetcode's module for Arrays and Strings is where you should start. This is a fundamental topic, so practice lots until you're really confident.
  • Linked Lists: Again, check out the module for Linked Lists. Don't worry about the solution guides that are subscribers only—you don't need them. Check out the discuss forum instead, click on posts until you find a good one. Linked lists can be confusing at first, but they're easy as once you get your head around the idea of the next pointers.
  • Trees: Focus on the N-ary trees module and then the Binary Trees module. Don't worry about Binary Search Trees yet, you can look at those a bit later. For some reason, the information documents about traversals are subscribers only. Don't worry about this though, there are plenty of great free resources around, such as this overview and these widgets that get you to click on nodes in the correct order. You'll find lots more by googling.
  • Hashing: This is dictionaries/maps, and sets, and is covered under the Hash Tables module. This is one of the most useful topics you'll learn, so be sure to get lots of practice in, as most challenging questions use these data structures as part of the solution. Don't worry about the few bits that are subscribers only.
  • Stacks, queues, and heaps (priority queues): These are also fairly versatile, coming up in a lot of problems. Stacks and Queues have a module, although heaps/ priority queues don't yet. Have a look on Geeks For Geeks for some good articles on heaps, and then find some questions on Leetcode that are solved with a heap. Check if your programming language of choice has a built-in heap type, it will be called either a heap or a priority queue.
  • Two pointer technique: If you didn't do this with arrays, you should do it now. It comes up a lot.

Make sure you know complexity costs of these basic data structures, for example, that finding whether or not something is in a linked list is O(n), but finding whether or not its in a dictionary is O(1). You should understand the costs inside and out, knowing exactly why they are what they are. Simply memorizing the costs won't help you much.

7. Learn the more advanced data structures and some famous algorithms (Intermediate)

There are some algorithms and a few more data structures that will come up over and over again. It is well worth putting time into studying each of these, much like with the fundamental data structures. Some of them will be in the easy category and some in medium. The hard ones tend to combine multiple concepts.

  • Recursion: This alternative to iteration is helpful for solving some problems, and once you're used to it, is often quicker to write than iteration. Leetcode has a module for recursion. Just do this module, don't worry too much about recursion 2 yet, there are more important concepts for you to learn first.
  • Graphs and graph algorithms: Graph algorithms come up everywhere. I've heard that in the interview processes of top companies, getting at least one graph question is inevitable. The main things they are looking for is that you know the 3 main ways of representing a graph: linked, adjacency list, and adjacency matrix, choosing the best one for a given situation, and then running algorithms over it such as breadth-first search, depth-first search, and topological sort. Often graph questions aren't explicitly listed as such—you'll be given some data as an input that you need to convert into a valid graph format, and then run the appropriate algorithm over it. You must get really good at recognizing graph questions instantly. Be aware too that a 2D array can represent a special kind of graph where each cell represents a node linked to its neighboring cells. Often these are breadth-first search questions. You should have already seen some of this in stacks and queues, and trees. But be sure you're super confident with graphs. You should be able to BFS and DFS both iteratively and recursively, and with your eyes closed (okay, maybe not that extreme, but you should be really confident with them!).
  • Union find: This algorithm can initially seem scary, but it's not. It's useful for finding the connected components of graphs and solving a number of other problems. Have a look on Geeks for Geeks to get started or the CLRS textbook if you own a copy. There is no Leetcode module on it yet, but there are lots of relevant questions. Learn the simple optimizations, in particular path compression, as while they sound advanced, they're actually really simple and lead to huge efficiency gains.
  • Binary search: People tend to get quite bothered by this algorithm and its edge cases and resort to guessing and checking loop and conditional conditions. I'd recommend doing the binary search module, but also trying to build intuition around the algorithm. Be cautious on relying too heavily on the templates given in the module, they are good to get started, but trying to memorize the templates will only lead to edge-case bugs that you will struggle to debug. It helps to know whether your “middle index” formula is getting the lower-middle or upper-middle (when there's an even sized list) and then whether or not your low and high moving will definitely converge instead of infinite looping. Sometimes making it converge is as simple as using the upper-middle instead of lower-middle, but it depends on how you're changing low and high. Overall, you must build an intuition rather than trying to memorize the algorithm. I might write a blog on this at some point.
  • Binary search trees: These, along with generic binary trees (i.e. not sorted tree), seem to come up almost every week in the weekly competition. Being able to quickly write a recursive function to traverse the tree and get the information you need is possibly the single biggest thing you can do to improve your competition performance. They tend to be medium-level questions, but if you know what you're doing, they are easy to do in under 5 minutes! Start with the Binary Search Tree module, and then look for more questions on trees. Make sure to do lots of medium-level questions.
  • Tries and advanced string algorithms: Leetcode has a module on Tries for you to work through. As for other string algorithms, Google them or look in the CLRS algorithms book.
  • Interval trees: These are probably the most advanced data structure you'll see on a semi-regular basis. I'd recommend trying to code one. Unfortunately, Leetcode doesn't have an Explore module on them.

8. Learn the versatile algorithmic design techniques (Advanced)

This is the stage I'm currently at. It was working on these techniques that has really driven my improved performance in the competitions. They are not easy, and you'll need to work and work and work at them. You'll need to start by practicing questions where you already know which technique you'll be using, and then on ones where you don't. The competitions are useful for that, as you don't get to see the tags until the end.

  • Bit manipulation: This isn't that difficult once you get your head around it, and it's also pretty fun. Leetcode has many questions on bit manipulation, although no module for it at the time of writing. To get started, Google a guide for your programming language of choice, then have a go at some of the questions. Note that while it can be used standalone for most of the easy and medium level questions, it tends to be an optimization technique combined with other concepts in hard-level questions.
  • Backtracking: This is a strategy that many advanced recursive algorithms use, especially when coming up with solutions for NP-Complete problems. Before I learned how to do backtracking correctly, my exponential time algorithms would also use exponential space, with lists and sets getting copied everywhere. I see many hard-level questions that are straightforward with backtracking. Leetcode has a section on it, tucked inside the Recursion 2 module.
  • Divide and conquer: This is another strategy that many advanced recursive algorithms use, in particular, those that run in O(n log(n)) time (quasilinear). Mergesort and Quicksort are the most well-known examples of divide and conquer algorithms. Leetcode has a section on them, also tucked inside the Recursion 2 module.
  • Parsing: Parsing questions are very difficult if you don't know how to approach them, but very fun if you do. One technique is recursive descent, but there are also others such as using an explicit stack. Some good questions are Number of Atoms, Parse Lisp Expression, Parsing a Boolean Expression, and Evaluate Reverse Polish Notation.
  • Dynamic programming: This may be the hardest technique, and unfortunately I'm still looking for a good resource on it. The CLRS algorithms book has some good content on it though, and Leetcode has many awesome dynamic programming questions. Come on Leetcode, add an Explore module for this topic!
  • Memoization: This is an alternative to dynamic programming that instead uses recursion. It tends to be easier to reason about (for most people), so it might save you for the more challenging dynamic programming problems. In saying that, your goal should ultimately be to do as many questions as possible using dynamic programming instead of memoization. Leetcode has on it, tucked inside the Recusion 1 module.

Keep in mind too that there's often more than one approach for a question, and the tags aren't always exhaustive. For example, the Smallest Sufficient Team problem is tagged as two of these techniques, but also has really nice solutions with one of the others. I'm being intentionally vague as I don't want to give spoilers.

9. Be aware of the intractable problems, particularly the NP-Complete ones.

A computer scientist's idea of a practical joke is to give the unsuspecting victim an NP-Complete problem to solve and watch them go around in circles, possibly discovering what they think is a solution and then discovering that it fails in some cases. Okay, maybe we're not that mean. But I have definitely heard of people in interviews trying to come up with an efficient solution for a problem which is NP-Complete, and if they DID find a good solution, they wouldn't be needing the job they're interviewing for (as they'd be rich for it!). I have even heard of companies trying to solve them, not realizing. Or apps that promise to give you the shortest path between multiple stops.

So, know what they are. Wikipedia has some good lists of them. Know what the best way to solve them is⁠—sometimes it's a brute force, but with clever optimizations. Other problems have dynamic programming solutions which are what we call pseudo-polynomial. The knapsack problem is a good example of this. Sometimes an assumption you're allowed to make (specified in the problem limits) will mean there's a polynomial-time solution (or pseudo-polynomial).

10. Brush up on those math skills

If you feel a bit rusty in math, or you didn't enjoy it in school, it might be time to get out the grid paper and pencil. I did this last year, and wrote a blog post on it. Overall, it was a lot of fun, and it helped to improve my programming and algorithm skills too. I could ramble about this topic for hours, but we don't have time for that, so here are some free resources I used and recommend:

  • Khan Academy: I can't recommend this strongly enough. It covers all of primary (elementary) and high school math in great depth, and it's actually really fun. It's not just for school students, it's equally awesome for adults. Sal has a talent for explaining things and the quizzes and content are broken up into manageable chunks. If you aren't sure where your weaknesses are, have a go at the initial quizzes. They'll tell you where you have work to do. Don't be ashamed if you find there are a few primary school-level concepts that you need to work on. It happened to me, and I was amazed at how much addressing those weaknesses helped me with the more advanced stuff. If you aren't already confident with it, I especially recommend the geometry stuff. The proofs and problem-solving there is a similar kind of thinking to the thinking you're trying to develop on Leetcode.
  • Introduction to Mathematical Thinking: If you feel you possibly have some amount of math-PTSD from school, Keith Devlin is the doctor for you. Keith's mission is to enlighten the general public on what it actually is mathematicians do (i.e. not arithmetic and solving pages and pages of equations for y's x). Aside from that, the course goes over logic and proofs and aims to get you to see the difference between school math and being a mathematician. It's helpful, especially if you aren't keen on tackling the MIT OCW stuff yet.
  • MIT OCW Mathematics for Computer science: This is more advanced, but well worth tackling if it aligns with your goals, i.e. being a top competitive programmer or getting into a top tier tech company. If you did a degree in computer science, you probably already did some discrete math. Unless you did discrete math beyond an introduction at a top school though, then this course will be helpful as there'll almost certainly be stuff you didn't know. At the very least, it's great revision. Note that you'll need to put hours into doing ALL of the “in class” questions to get the maximum benefit. We all learn best from doing, and the questions are of high quality.

11. Be confident knowing the asymptotic complexity of an algorithm, and don't write code until you know your algorithm will be good enough.

When given a question in an interview or a contest, don't dive into writing code. The first thing you'll need to do is think and brainstorm possible ways of solving it. For each one, you need to know how to determine the asymptotic complexity, paying particular attention to the worst cases. You'll then need to look at the problem limits and make a judgement call as to whether or not your algorithm is likely to be fast enough. Over time, you'll build a sense for how long things take. For me, I start to worry when plugging the maximum value into the big-O formula evaluates to over a million or so. It's a very crude measurement, but it seems to serve me well.

Sometimes you'll need to come up with a better algorithm from scratch. Sometimes, you can optimize a bad algorithm so that it's a lot better. But you'll need to be fairly confident before you start coding, otherwise you'll risk wasting time writing and debugging code, only to get the dreaded Time Limit Exceeded error that can only be fixed with a full re-design and re-write.

12. Read the problem limits well.

Often, you'll be told what the maximum input sizes to expect are. These will give you a lot of clues about the kind of algorithm you might be writing. As a very rough rule of thumb:

  • If the limits are tiny, i.e. all under 50 or so, then your algorithm will probably be non-polynomial (and this is a “smell” for intractable problems).
  • If it's under about 1000, then you might be looking at quadratic or around that.
  • If it's over that, but under 1,000,000, then it's probably linear or quasilinear.
  • Over that, and it's quite possibly logarithmic. If it's ridiculously high (e.g. billions or trillions) like sometimes seen in the Google Code Jam, that can be a sign of being able to shrink it with modular arithmetic or even a constant time algorithm.

These aren't certain rules, but they definitely give a good indication. On the other hand, if your quadratic algorithm needs to run on sizes of 2000 or more, it's probably not going to pass. Usually, but not always, quadratic algorithms can be replaced with quasilinear ones taking a divide and conquer approach, or using binary search somehow.

13. Choose the best variable to scale up on.

Sometimes, what seems to be the main variable (e.g. number of items) is quite high, but another variable is surprisingly lower. Going back to one of my favourite questions -- Smallest Sufficient Team -- we are told this:

1 <= req_skills.length <= 16
1 <= people.length <= 60
1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
Elements of req_skills and people[i] are (respectively) distinct.
req_skills[i][j], people[i][j][k] are lowercase English letters.
It is guaranteed a sufficient team exists.

The interesting detail here is that the maximum number of required skills is a lot lower than the maximum number of people. This is a big clue. It suggests that the cost will primarily scale with the number of skills required, not with the number of people. Instead of an approach that considers including or not including each person, we should instead be looking at a solution where the main looping is over the skill list.

This is common in Google Code Jam questions. It's worth having a really good look and think about the limits, especially if one seems unusually low/ is a surprising constraint. It can often mean there's a good solution that wouldn't have worked as well if it was bigger.

14. Share your solutions and teach others

It's widely known that to master something, you have to teach it. Writing up high-quality solutions and explanations on the discussion forums is a great way of doing this. It will also help you develop other software engineering skills, such as writing and explaining. Make sure you post with the goal of helping others, and not showing off. Nobody likes a code dump with no comments or explanations.

Take pride in the code you share. Very few people like reading code where all the variable names appear to have been taken from the lyrics of the famous alphabet song. When writing your post and the code to put in it, pretend potential employers might be reading it. If you're wanting to get into a top tech company, then write the kind of code you'd be expected to write there. For example, use descriptive variable names. During my Google internship, I noticed this in the Google codebase and my partner James also tells me that Canva's codebase is the same.

ABOVE ALL OTHER ADVICE, put 3 backticks before and 3 backticks after your code. This will make it format nicely. It amazes me how many people don't know to do this/ don't bother to find out how when their code looks hideous and unreadable from the lack of it.

15. Practice general problem solving

When learning algorithms, data structures, and techniques, I recommend you use the tags to find relevant problems. After all, your goal is to master a specific skill.

But after that, you need to practice “problem solving”. This is where you have a problem to solve, and you do not know which of your skills you'll be applying to it. To do this, the weekly contests and mock interview feature are amazing.

Remember that sometimes a question will require a technique you've never seen before, or will require a major adaptation to one. You'll need to learn to be creative and think outside the box if this doesn't come naturally to you, memorizing solutions will not help you. A great example of this is questions such as Minimize Max Distance to Gas Station. There is a quasilinear solution using binary search. It's not at all what you might initially think.

16. Do the weekly contests

These are great fun, and a great chance to practice your general problem solving, although they can be buggy as the questions are new to the site. Cheating is also an issue, particularly in the form of people hardcoding the answers to the largest test cases. This has reduced a lot though since Leetcode stopped displaying the answer to test cases where the result was Time Limit Exceeded. There are also issues with some programming languages being faster than others. Sometimes, a poor solution will slip through with C++ and Java, but not Python, for example.

There is no rule against using previous code, although at the end of the day, one needs to decide what their goal is. Using previous code is not helping you learn. Most of the winners seem to be using previous code, their goal is generally to accumulate Leetcoins so that they can get their yearly subscription and a T-shirt (or so it seems)

It also takes a lot of practice. Over time, you'll get better at it. I wasn't getting in the top 200 at first, it took practice.

17. Use the mock interview feature

I have a Leetcode subscription, so in theory, I could do the company-specific interviews. I actually never do though, I much prefer the random sets. They seem to be taken from the company-specific ones, with the difference being you don't know which company it's from. So don't worry about not having a subscription, you'll still find this feature useful.

As a general rule, the 3 levels (screening, phone interview, and onsite) are more difficult than the last. So, start with the screening ones and then move up from there. Unfortunately, Leetcode will sometimes give you a mock interview you've seen previously, there's not much you can do about this. Once it seems to be happening a lot though, that probably means you've done most of their mock interviews of that type. Because there is a finite number of them, it's also best to not use them until you've done some practice (i.e. mastered at least the basic and intermediate skills I've listed above).

Fun question: If there are 25 mock interview problem sets, and each has the same probability of appearing, around how many mock interviews will you need to do to see them all? How many repetitions can you expect to see?

In all seriousness, the mock interview feature is great for keeping you focused (it's timed!) and for forcing you to solve some problems without seeing their tags. Remember what I said about practicing your general problem solving?

18. Don't spend all your time doing easy-level questions

I used to fall into this trap, I would do easy level questions, trying to do them as fast as I could. Then I realized that was a big waste of time, as it was the medium and hard level questions that I was struggling on in the weekly competitions, not the easy ones. Getting the easy ones solved quickly doesn't mean much compared to getting the points of the hard ones.

You need to do questions that are challenging, even if they take you over an hour. This is how you'll learn and improve. As you get better at them, your speed will go up. Focus first on accuracy and skill, and then secondly on speed. Remember that if you can at least get to the point of answering all 4 competition questions in the 90 minutes available, you're already doing better than most people.

19. Try to avoid writing bugs in the first place

We all know debugging sucks when you're timed and seeing those precious minutes tick by. The best solution is to not write bugs in the first place. By programming mindfully, with your full attention, you'll be able to consciously ensure each line is doing what you want it to.

For particularly tricky lines of code, such as binary search boundaries, make a quick example if you have to, and make sure your code does what it's supposed to on it. Do this as you're writing the algorithm, not at the end. If you don't remember the details of a particular library function perfectly, quickly look it up, don't guess. In an interview, tell your interviewer you can't remember. Most people forget these things, and there's a chance they won't remember either. They can tell you what assumption to make. Also, in competitions, it can help to have a shell up with your chosen language if it's interpreted. Sometimes I forget how particular things in Python work (especially when it involves complex splicing) so being able to quickly type in an example really helps!

Something else that helps me is writing code on paper first. I find there are less bugs, as I can't handwrite as fast as I can type.

20. You must have fun!

You'll burn out in no time if you don't enjoy it. Don't go about your studying in a way that makes it feel like a torturous chore. Do what you need to enjoy it.

And if you still just can't enjoy it, then perhaps it isn't for you, which is fine. We all have things we do and don't enjoy.

Feel free to leave any questions or further tips you might have in the comments!



当前位置:极客学长 | 极客中心 » Getting good at Leetcode


Captcha Code