Im thinking about this one rn: last stream we did system design of rate limiter. It would not be that hard to implement mvp next time. Our own rate limiter with black jack and whores, what do u think?? Should I prepare it for the next stream?

Good, let's do it then.

Today's backtracking problem:
https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/?envType=study-plan-v2&envId=leetcode-75

Seems like I got day off starting from now xDDD


The thing is that everything is connected to MS account, and if I cannot log in - I cannot work

So, about our backtracking. In the comments I will post different solutions. Feel free to post yours as well, and we can discuss. There will be with spoiler, so no worries.

Now, the interesting part is the complexity. Have a look into the backtracking call stack.
what is the time complexity you would think?

Consider that worst case, at each step is to 4 subnodes, as some numbers correspond to 4 characters instead of 3 as in example

The tree simplifies the idea, basically on every call, you are calling function recursively 4 times (worst case) or 3 times (best case).

For the worst case it means we will have O(4^n), where n is the length of the initial digits string.

Let's break down:

First layer: 4 calls = 4,
Second layer: 4 calls are doing 4 calls = 4 * 4 = 16
Third layer: 16 calls are doing 4 calls = 16*4 = 64
... and so on.

Formally it is simplified to this 4 * 4 * 4 * 4 ... n => 4^n

so it turned out that windows client DNS was broken. It happened to other people as well, and we ended up updating hosts file.

MS....

Let's GOOOOOO

Dynamic Programming. I think this was the hardest topic for me back then. I might post a bit more problems related to dynamic programming then.

https://leetcode.com/problems/n-th-tribonacci-number/description/?envType=study-plan-v2&envId=leetcode-75

I came to the conclusion, that the best way to solve it is to do 3 step solutions.
Usually it looks like that:

1. brute force + recursion
2. top down: recursion + memoization (save sub problems' responses to map)
3. bottom up: start with sub problems' responses array and solve base cases. Then iterate and calculate the bigger subproblems based on previous (smaller)

Today we gonna solve this Tribonacci number using 3 approaches.

If you already solved basic fibonacci number before - you would already know the naive recursive solution. This is first step to solve the Dynamic Programming problem.

If you start building the call stack tree - you will see that there are a lot of function call with the same argument.

The time is exponential: every function call we are calling recursive function 3 times. So it is 3^n time somplexity. The space complexity is the height of this tree = O(n).

I think the call stack tree should lead you to the optimization here

What you have to do is to remember the result once you calculated it. So next time, if you need to do recursive call - you would return the result from the map straight away.
For it we don't have to change the code that much, only add map there

But then, what can be done even better, since it is recursive solution, and interviewer for sure will ask you - how you will deal with stack overflow, and is there any iterative solution. In that case - you should start from the below: building the solution from the base case and move up until your N. Then just return the last element in memoization array

Having fun in office’s music room

oops...
As always, client fckd up
https://www.techzine.eu/news/collaboration/129181/the-end-is-nigh-for-skype-microsoft-to-pull-the-plug-in-may/

Once you will hear official commentary from MS, I will tell the story as well as I'm kind of part of this thing :)

People, today we are streaming 19:00 UTC (8pm Prague time).
Gonna do couple of LeetCode questions, and implement the rate limiter we have designed before

while implementing, we will talk a bit about concurrency. Think we never spoke about this topic before. And yeah, since we are talking about concurrency - we cannot talk about JS, so Rate Limiter will be implemented using my main: .NET.

Charging