Ask HN: How to Approach Algorithm Studying?

I'm also trying to figure this out, here's my approach so far.

1. Categorize - Can I identify what type of problem this is? (ie Graph problem, bit problem, sliding window, etc.)?

2. Plan a solution - Can I come up with a strategy to solve it?

3. Based on how I felt about 1 and 2, am I confident enough to dive in and solve it?

3A. If yes, as a final check, go to the discussions and see if you can get some confirmation that you had the right approach just by reading the titles. For example, if you were thinking that this was a backtracking problem because that was the only way you thought it could be solved and you see that the most upvoted posts are talking about priority queus, you probably had the wrong approach. Otherwise if it looks like you were on the right track, only then should you go ahead and start coding it.

3B. If you had the wrong approach or if you weren't confident that you could solve it, then go ahead and learn from the solution.

You will learn a lot from the solutions that others posts but you will hardly learn anything by wasting hours on a flawed solution.

To be clear, to get good requires going well beyond the fundamentals, you need to learn from the best of the best in order to stand a chance.

great advice. id say limit yourself to 10 mins to come up with a solution, and focus on getting a solid intuition consistently

Let's take ThreeSum as an example.

Imagine you're encountering ThreeSum for the FIRST TIME as I did a few days ago. I'd never before seen this problem.

What should my EXPECTATION OF SELF be for this? What is reasonable for someone STUDYING to improve at algorithms. What would be considered SUCCESS?

Should I .... be able to intuit the O(N + NlogN) solution?

Ok maybe you would agree that's unreasonable to be able to just come up with naturally having never seen the problem before.

Should I ... be able to intuit the O(n^2 * logn) solution?

Even that solution might reasonably evade someone? Or not?

Should I .... be able to intuit the brute force solution O(N^3) but have the O(N + NlogN) solution memorized?

From wiki https://en.wikipedia.org/wiki/3SUM ... it appears that the O(N + NlogN) took formal algorithm research and study. Perhaps it's unreasonable to expect myself to on-the-fly solve some of these algorithms with sub-cubic time?

For a new problem, success is any solution that passes all test cases and implemented within an acceptable time frame.

I personally think leetcode focuses a bit too much on runtime. In a real interview, the clock is ticking down and the stakes are high. Most people won't pass all test cases. Sometimes it's not even necessary to pass them all to make it to the next round.

It's much easier to rank candidates by how many test cases they passed than by their algorithm's efficiency.

So in a real interview:

#passedTCs > algorithm efficiency

I would count the stages of success like this:

1. Brute force it. -> That is actually the most important step. In regards to this one specifically, I would be surprised if interviewers expect more than O(n^2).

2. Guess what the best runtime would be. -> If you can reason why you expect what to be the best runtime, it should bring you through all interviews.

3. Get good solutions, but memorizing won't help you in the real world (though it might in some interviews). Interview situation is pretty unique. In a normal work environment, you can search the internet, argue with collegues, sleep over it. If runtime is essential for the program you are writing, it cannot be expected of anyone to come up with best solutions on the fly.

Regarding brute force solutions, they can still vary in quality. Is it correct, easily understandable, without side-effects?

Let's take Euclid's algorithm which gets the greatest common denominator between two given numbers. Euclid was a mathematician and "father of geometry". According to Wikipedia, the algorithm was improved a long time after he first described it. That means his one wasn't even the best!

Now we have programmers being tested in hour long interviews... how could they come up with this stuff on the spot?

There is a reason why people have to study for tech company interviews. Knowing the solution to a problem that is similar to the one that is being asked will go a long way in the interview.

That's exactly what I'm trying to get at with this post.

I initially started my study of algorithms about a week ago, with nearly a decade of professional programming experience under my belt.

I quickly realized that expecting myself to find the optimal, or even near-optimal solution, was setting myself up for failure. Yet (hence this post) I wasn't sure if that was the case for other people.

I continue to wonder what other people's experiences have been like in the pursuit of algorithm study. Do you find that the intuitive, brute force solution is readily available in your mind, but that you have to "peak" aka "cheat" to find the elegant / right solution? Or are most people finding themselves able to just tackle the problems outright, getting (or nearly getting) the optimal (or nearly optimal) solution on first pass...?

Personally I am the same as you. My first attempt is never the optimal solution.

agree w/ another comment that suggested going through an algorithms textbook first. (MIT 6.006 online is also good.) i speak from experience: in some cases there might be tools missing from your algo toolbox and it could be worth more studying to fill in gaps.

for example, consider the maximum subarray problem (LC 53). this is a dynamic programming problem. but if you don't know DP, you could spend a long time staring at this problem without progress. even looking at the solutions won't be that informative if the concepts of DP are not familiar. MIT's 6.006 course takes four lectures to cover DP (not including the recitations!), which should tell you something.

In your place, I'd work through a basic algorithms + data structures book first, doing the exercises etc before attempting leetcode.

Learning via attempting leetcode problems directly seems suboptimal, like trying to learn calculus by taking timed exams vs working through a basic text first.

my 2 cents. fwiw.

And what will your goto algorithms and data structures book be?

I would suggest "The Algorithm Design Manual" by Skiena. It helped me a lot.

Again what I'm basically asking is -

Should you be MEMORIZING solutions, or, expecting yourself to come up with the O(N)/O(1) solutions on your own?

Why are these the only options? Why can't you just know there is a solution, and know where you can look details up? Expecting to find ideal solutions on your own every time is tedious and taking time away from solving the actual problem you are working on.

Because that's not how interviews work, basically.

Trust me, I understand that in the real world that's exactly how you would approach these problems.

It's about solving new problems using what you learned from previous problems.

You don't need to memorize since 1.) you don't know what parts of the problem will generalize to other problems until you've seen a lot of problems, 2.) by the time you're able to recognize the same pattern repeated in other problems, you've mostly memorized it anyway.

What I've found to be the most helpful is taking down notes of new concepts that I've learned. For example, a quick summary of how dijkstra's algorithm works so if I need to use it, I can read my own summary and quickly get up to speed on it.