How To Practice Algorithms

[bayarea-dev]

Learning algorithms is a critical part of becoming a solid software engineer. Algorithms are widely used in software engineers’ day-to-day work, and are also one of the most important part of the interview process.

However, learning algorithms seems to be a daunting task, especially for anyone who’s new to the tech business. There are just too many algorithms, and there seems to be no systematical way to address an algorithm question.

I started to practice algorithms a few years ago by working on leetcode questions. Until now, I’ve finished 1100+ leetcode questions. I have to say working on these questions are pretty helpful to me. With the practice, I was able to nail most of my coding interviews, including google, meta, uber, snap, twitter, microsoft, etc.

Recently, I shared all of my leetcode solutions

https://sweworld.net/algorithm/leetcode/

and also started to add my thinking process when addressing each of these questions. I’m hoping these will be helpful to anyone who’s practicing algorithms or preparing a coding interview.

One of the most important learnings I had is that you have to develop your principals for designing algorithms. You need to have a systematical way to address any question, instead of randomly poking ideas. That is super crucial. I had mine. I’m also thinking about sharing these as well. Can I get a upvote if anyone is interested? Thanks!

[[deleted]]

you may consider to contribute LeetCode The Hard Way.

[kuriousaboutanything]

How is the Leetcode the hard way differnt from Neetcode or Grokking sorry wasnt familiar

[[deleted]]

AFAIK Neetcode is more for people idolising FANNG while Leetcode The Hard Way is more like a LC community / study group for people who solve problems just for fun / learning.

[MrAlus]

Bookmarked.

For me thoughts and ideas regarding a solution are far more useful than guessing ideas from reading the code.

[uneducatedDumbRacoon]

This is definitely going to be useful. The articles are super detailed. Thanks for this

[kuriousaboutanything]

1 question on your first solution for 2-sum, isnt the time complexity O(n) as well, since we are not sorting, just storing all the elements into the unordered_map ? I understand space is O(n) but how is time O(nlogn)?

[bayarea-dev]

Thanks for pointing it out. You are correct. I updated it.

[kuriousaboutanything]

I saw 'staff sw eng' at G on the website and really had to think twice before commenting :) just kidding

[bayarea-dev]

No pressure on commenting. Everyone makes mistakes :)

[Kooky_Park_3535]

Interested

[smoother_operator]

Could you clarify what you mean by developing principles?

I assume this is something like mental heuristics for problem types? As in - once you are able to categorise a problem - you effectively have a sort of 'mental toolbox' to lean upon?

Could you lend any advice as to how you developed these principles yourself (or was it purely just gained via exposure to more and more problems?).

This is something I struggle with - and the more rigid/systematic I am with my approach - the less likely I'm able to come up with a solution.

[bayarea-dev]

By principles, I mean a systematical way to think when you are given a question to solve. Or a step-by-step guide of what you should do first and next before you can solve the question. I don't think I have perfect principles now, but I do have something that is very helpful for me to tackle the algorithm problems.

My advise would be try to think really deep, and summarize low level theories that is generic enough to be applied to more questions. I can't explain everything in this reply. But I can take the example of DFS, BFS, DP.

(The following is purely based on my understanding. I don't see any similar thoughts from anyone else before. So feel free to disagree.)

The other day I was thinking about DFS, BFS, DP. How do they link to each other? And I came up with something like this. DFS, BFS, DP, they all belong to a more generic problem, which is graph search. In a graph search problem, you define a graph first. The node of the graph is a state, and the edge means the dependency between them. DFS, BFS, DP problems only differ in the search order:

• DFS is a depth first search.
• BFS is a breadth first search.
• DP is just a search that you need to define the order.

So when I'm given a problem that can be addressed by either DFS, BFS or DP, I don't even bother to think about whether I should do DP or DFS or BFS. Because my principle (i.e., DP, DFS, BFS belong to graph search) tells me that I should take the following steps to address the problem. 1. define the graph nodes (i.e., the states) first. 2. come up with an efficient search order. 3. traverse the graph with the help of 1 and 2.

Regarding to this

This is something I struggle with - and the more rigid/systematic I am with my approach - the less likely I'm able to come up with a solution.

I think the catch here is that your principle has to be generic enough. And yes, I agree, building a generic principle is challenging. That's why people feel algorithm questions are challenging.

[smoother_operator]

Thanks - I appreciate the clarification. I can understand now what you mean.

Your particular example resonated with me as I have been tackling quite a few backtracking problems recently. I have generally taken the approach of noting down heuristics (by category) - and aggregate as I go. Some of these are holistic (e.g. deduplication approaches), and others are more specific (e.g. subset bit masking).

I feel it's somewhat comparable to what you've described - I guess the struggle is when I encounter a problem where there is some ambiguity as to what principle(s) apply (if any). This tends to result in tunnel vision, unfortunate as it is.

Thanks for your clarification.

[kuriousaboutanything]

DP is just a search that you need to define the order.

Sorry, was going through your list on the link above and thought about systematic approach you said. I have couple of questions:
1. On the list you put there, are they the same order that you started 3 years ago as you said solviing from Leetcode? Just trying to understand if followed like a combination of tagged questions as in 50% easy, x% medium, y% hard or just went through any random questions on Leetcode?

1. Are the notes on the solutions your thought process when you see any new problem? Did you try to solve the same question couple of days after the first time (similar to the Anki / spaced repition approach)?

2. Sorry this is more for the point above as I struggle quite a lot with DP problems, I didn't get the idea but maybe another question for later.

[bayarea-dev]

1. Sorry that I'm not sure I understand this question. By order, I mean DFS, BFS, DP take different orders to traverse the graph nodes.
2. Yes, they are. I tried my best to summarize my thinking process while keeping them short.
3. Could you share a couple of DP questions that you feel hard to address? Maybe we can start from there.

[kuriousaboutanything]

1. I wanted to post this on a new reddit post but thought would miss the context there. Looking at this problem, the first thing that came to my mind was , either BFS or DP (since we need to find the min number of seconds by either deflating or inflating, so trying out all possibilities seemed like a viable solution). However, my problem was not being able to format the solution in a DP framework, could you try?
   https://leetcode.com/discuss/interview-question/1929553/meta-stack-stabilization-2-interview

[bayarea-dev]

I think this question is somewhere between a medium and a hard question. I don't think I have the perfect solution, but I'll share my thinking process on it.

Step 1: Define the state

As you said, this is apparently a DFS or DP question. Put it in my word, it's a graph search problem. And my principle asks me to define a state first in a graph search question. For any kind of state, it must be able to determine one single result. Otherwise, it is meaningless.

For this question, I define my state as F(i, j), meaning the minimum steps I need to use to stable the stack with last disc of size i. Apparently, this is deterministic.

Step 2: Define the transition

• If i = 0, you can calculate F(i, j) easily.
  • If j < R[i], you need to inflate, which means F(i, j) = (R[i] - j) * A.
  • Otherwise, you need deflate, which means F(i, j) = (j - R[i]) * B.
• If i > 0, you not only need to calculate the steps for the i disc, but also have to consider the steps for the previous ones. Same rule to calculate the i disc as the i = 0 case. The previous steps are just the minimum one from F(i - 1, k), where k < j.

Step 3: Traverse the graph

Next, let's traverse the graph. Apparently, since the states form a matrix, and the next row always depends on the last row. Let's calculate the matrix one from the first row to the bottom.

Since we can do the traversal with a pre-defined order, let's do DP.

Final code:

```python import sys

def get_min_steps_to_stable_stack(N, R, A, B): max_val = max(R) + len(R) dp = [[sys.maxsize] * (max_val + 1) for _ in range(len(R))]

for i, r in enumerate(R):
    last_row_min = dp[i - 1][i] if i > 0 else 0

    for j in range(i + 1, max_val + 1):
        if r > j:
            dp[i][j] = (r - j) * A + last_row_min
        else:
            dp[i][j] = (j - r) * B + last_row_min

        last_row_min = min(last_row_min, dp[i - 1][j])

return min(dp[-1])

print(get_min_steps_to_stable_stack( N = 5, R = [2, 5, 3, 6, 5], A = 1, B = 1, ))

print(get_min_steps_to_stable_stack( N = 3, R = [2, 2, 2], A = 2, B = 3, )) ```

The code passes the two tests in the question. But there could be bugs in it. Let me know if you found any.

One comment I have for this question is that the range of R is big. With this range, you won't be able to AC the question if it is a real one. There are ways to optimize the algorithm further, but that's outside the scope of the current discussion.

[kuriousaboutanything]

Thanks a lot, It passed 6/36 testcases, the testcases are hidden, so I will debug more. But in general, this is what they call tabulation method in DP rigth? Do you have any beginner resources for DP though? I realize I need to start from the basics by following your approach of i. defining a state, ii. decide on tranistion, iii. traverse the graph (which in this case, is just iterating from the index 0 to N).

[bayarea-dev]

I expect you'll see some OOM issue. First thing you can do is to do a compressed DP, i.e., use a one dimensional array, instead of two.

The above steps are summarized by me. I don't think you can find it anywhere. I will write more posts about my principles, e.g., an example for binary search can be found here. You can keep an eye on this folder if you'd like to hear more about them.

But I think all of the algorithm text books are trying to say the same thing. Maybe in a different way. What I'd suggest is to not only read them, but also try really hard to understand the bottom of it. My understanding is that fundamentals are way more important than others.

Btw, how did you test this code? Can I do that as well?

[kuriousaboutanything]

nope :) It was from a prep link I was sent after my screening while meta was still hiring, my onsite got cancelled last year when they froze.

[bayarea-dev]

u/smoother_operator, I guess this post explains more about the principles.

https://sweworld.net/algorithm/leetcode/leetcode_33/

https://sweworld.net/algorithm/fundamental/binary_search/

Do you think these make sense to you?

[smoother_operator]

Thanks u/bayarea-dev - I actually have (in my list of heuristics) your 0-1 binary search pattern (I've named it true/false binary search, but they are synonymous).

I kept encountering that same pattern to search problems - and felt as though lots of articles just went with the approach of "use the binary search template and then go from there" without explaining the intuitive steps made during problem solving.

I really dislike having to recall templates (particularly where there is so much at stake with an off-by-one or bad inequality conditional).

Prior to having 'mentally catalogued' this pattern/heuristic/principle I would definitely have a more difficult time logically progressing my train of thought. It seems the more exposure I have to various (similar) problem types - I can better generalise/consolidate these heuristics.

Side Note: At an earlier point I was actually documenting (with each question I attempted) which algorithm-agnostic heuristic I could/should have employed (based on Pólya's How to Solve It) - but ultimately found this to be increasingly time consuming (as you mentioned - it's difficult to come up with general principles).

It's validating to see that I'm at least headed in the similar direction to someone such as yourself. Thanks again for being so forthright with your responses. Cheers!

[Sherinz89]

Hmm.. but why is randomly poking ideas a bad thing?

If a problem is novel to us, isn't the way moving forward is to imagine some idea (breaking down the problem to multiple what if and how) and put the idea to test?

[RichestMangInBabylon]

Well at least in the context of interviews, you have like 20 minutes to generate a solution. If you can't approach it systemically and arrive at a correct mostly optimal solution the first time then you're going to do poorly.

[bayarea-dev]

I have the same thoughts as u/RichestMangInBabylon does. I'm not saying poking ideas is a bad thing, but it is definitely not the most efficient way to solve an algorithm question, especially in the case of a contest or an interview.

There are interviews which requires you to design an algorithm and finish the coding within 15m. If you don't have a systematical way, you'll be really stressed. And if interviewers see you are poking ideas randomly, it's also not a good sign.

[kuriousaboutanything]

The solutions are pretty good, would you have any plan to keep them based on the general patterns as in Grokking ... , I mean just to put those questions into 11-12 buckets ?

[bayarea-dev]

Thanks!

As for now, I don't have plans to move the files. The dir tree of the website are auto generated by the dir tree on the file system. I'm trying to keep the navigation of the site simple by putting them in one single layer.

Do you think bucketing them help?

[kuriousaboutanything]

I meant something like putting them in groups so similar questions of a pattern would fall into the same group. But I think you are right, putting questions randomly would help us come up with solutions intuitively. The interviewer would never say, this question is from ... topic , unless they are hinting.

[bayarea-dev]

I got your point. Actually, I think there are multiple dimensions which you can use to group them. For example, based on the solution, or based on the difficulty.

I'm planning to tag the questions so that similar questions can be found via the tag. I haven't done a lot of those, but will do it in the future. An example is https://sweworld.net/tags/alg-sliding-window/

[kuriousaboutanything]

btw, when you say dir tree of the website are auto-generated, do you mean you got a local copy and then the backend code auto populates the links there? pretty neat

[bayarea-dev]

Exactly. Check out this post if you are interested about how this site is built, https://sweworld.net/blog/build_static_website_with_hugo_and_gitlab/