Ask HN: How to Approach Algorithm Studying?
Generally, I can intuit the "brute force" solution, but the "right" answer with linear/constant time often requires looking at the answer.
Should I expect that with practice, I'll eventually get better at quickly finding the optimal solution? Or, is it expected that optimal solutions are "memorized" similar to how hard sciences like ME / EE / CE memorize formulas?
Take ThreeSum problem for example. I was able to write the brute force solution without any prior knowledge of the problem. In an interview with time constraints this WOULD have been my solution.
I now understand that's not the right solution. I've looked at the answer, and I have the "right" solution memorized. That kind of feels like cheating though Should I have been able to write that "right" solution straight away, with no prior exposure to the problem?
Just trying to understand what my goal is in this process, and what is considered "success" for my studies.
16 comments
[ 6.7 ms ] story [ 53.5 ms ] thread1. 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.
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?
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
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?
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.
Should you be MEMORIZING solutions, or, expecting yourself to come up with the O(N)/O(1) solutions on your own?
Trust me, I understand that in the real world that's exactly how you would approach these 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.
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.
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...?
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.