Reminding you guys, tomorrow 8pm Prague time we are streaming:
Agenda:
- LeetCode 75
- 1 question that was asked during previous stream
- System Design: Rate Limiter
- Talking about FAANG, Microsoft, and other big corpo stuff

If you want to discuss something specific - leave the comment - we gonna review every single comment

prepare yourself tea or coffee, we are starting soon

Let's go:

https://www.youtube.com/watch?v=BnM14XIRbFM&ab_channel=andreyka26_se

https://www.twitch.tv/andreyka26_

Welcome everyone who is new. Thanks for following. I would appreciate any feedback, and suggestion for the next stream and videos/articles.

For those who are new and came from Vlad or Ihor (thank you both guys ❤️):

Vlad is my friend, ex-Microsoft Engineer, doing Youtube as well, very skilled guy, he really teaches leetcode(not like me), so you could sign up for his courses and he will teach you how to pass algo interview:
https://www.youtube.com/@vladtenten
https://t.me/tenfoundation

Ihor is my friend, and he is ex-Microsoft Engineer as well. He is owning his own company at the moment related to AI. If you are business or need AI solution - reach out to him: @ihorcodes

I am Andrii, Software Engineer at Microsoft (for 3 years already almost), part of the team, that is doing backend for presence (online/away/inacall bubble in teams/outlook). Here we are doing different stuff related to software engineering, but lately I started recovering my knowledge in LeetCode (that I'm very bad at) and System Design (that I'm a bit better, but still bad), since it is time to have some interviews to keep my form.

Since I'm solving the leetcode on daily basis rn, I would be pasting here some problems, and we can share the answers, thoughts, etc. RN I'm doing LeetCode 75 list.

So today is Binary Search. So let's recall how to do it:
https://leetcode.com/problems/guess-number-higher-or-lower/description/?envType=study-plan-v2&envId=leetcode-75

The solution:
```

var guessNumber = function(n) {
let left = 1
let right = n

while (left <= right) {
let mid = left + Math.floor((right - left) / 2)
let guessed = guess(mid)

if (guessed === 0) {
return mid
}

if (guessed === 1) {
left = mid + 1
} else if (guessed === -1) {
right = mid - 1
}
}
return -1
};

```
Basically - it is simple binary search algorithm, but instead of checking sorted array, we are checking single number everytime.

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