Guess The Algorithm Challenge (FAANG Interview Questions)

Can you guess the right algorithm? In this video, you'll be presented with a bunch of interview questions that have historically been asked in FAANG interviews. Your task is to figure out the right algorithm or data structure to use for each question. You'll be given 4 choices each time, but be careful - some (but not many) questions will require multiple topics at once!
This video has a lot of uses, besides just being for fun. See the "why this video is useful" timestamp.
Dictionary (definitions of each topic): docs.google.com/document/d/1c...
Questions
Q1: leetcode.com/problems/lemonad...
Q2: leetcode.com/problems/delete-...
Q3: leetcode.com/problems/maximiz...
Q4: leetcode.com/problems/number-...
Q5: leetcode.com/problems/count-s...
Q6: leetcode.com/problems/maximum...
Q7: ​​leetcode.com/problems/arrangi...
Q8: leetcode.com/problems/minimum...
Q9: leetcode.com/problems/number-...
Q10: leetcode.com/problems/sqrtx/
Q11: leetcode.com/problems/reduce-...
Q12: leetcode.com/problems/minimum...
Q13: leetcode.com/problems/triangle/
Q14: leetcode.com/problems/swim-in...
Q15: leetcode.com/problems/max-are...
Q16: leetcode.com/problems/self-di...
Q17: leetcode.com/problems/network...
Q18: leetcode.com/problems/redunda...
Q19: leetcode.com/problems/delete-...
Q20: leetcode.com/problems/jump-ga...
Q21: leetcode.com/problems/count-n...
Q22: leetcode.com/problems/map-of-...
Q23: leetcode.com/problems/avoid-f...
Q24: leetcode.com/problems/delete-...
Q25: leetcode.com/problems/pizza-w...
Music
Local Forecast - Slower by Kevin MacLeod
Link: incompetech.filmmusic.io/song...
License: [yt dislikes this link, removed]
Sunset On Terra by HYBRID V (Creative Commons License)
creativecommons.org/licenses/...
Support by RFM - NCM: bit.ly/2xGHypM
Sthlm Sunset by Ehrling
• Ehrling - Sthlm Sunset
(not exactly sure how to credit, the link is dead)
Dreams by Bensound
www.bensound.com
Support by RFM - NCM: bit.ly/2xGHypM
Paradise by Ikson ( / ikson )
Link: • Ikson - Paradise
This Is For You (Prod. by Lukrembo)
Link : • lukrembo - this is for...
Timestamps
00:00 Intro
01:40 Why this video is useful
03:21 Q1
04:28 Q2
05:13 Q3
06:02 Q4
06:48 Q5
07:31 Q6
08:12 Q7
08:59 Q8
10:00 Q9
10:59 Q10
11:31 Q11
12:11 Q12
13:03 Q13
13:48 Q14
14:38 Q15
15:12 Q16
15:59 Q17
16:40 Q18
17:20 Q19
18:06 Q20
19:08 Q21
20:16 Q22
21:12 Q23
22:23 Q24
23:13 Q25
24:12 Conclusion

[@adityagaur2223]

you forgot to write top competitive programmer vs

[@ferokuk]

in this video he is not a top competitve programmer

[@arno.claude]

What an awesome video concept! Thank you, and hopefully we'll see more in the future!

[@BillFye]

Hopefully you are enjoying growing your KZbin channel Colin. I wish you nothing but the best! You are fueling my desire to consume, and also learn! Thanks!

[@Nemoatardecer]

Really good stuff, I love the structure of the video and the interaction makes it easier to understand the topics

[@keikaku9298]

This was such an enjoyable video. It is way past midnight, and this is the last thing I would have wanted to do, but I went through all the questions. You will hit 1M in no time, exceptional quality videos. Keep it up!

[@Mrcfski]

This is an incredibly useful format for learning theoretical solving. Thanks for the great vid, hope to see more in the future!

[@Avighna]

ILYSM, this is so cool, especially the why this video is useful parts, and the abbreviated versions! Keep making videos man, huge fan!

[@joakimolovsson7310]

Nice! This could be a recurring thing every so often to check up on your learning. Thanks! :)

[@wesleyso0]

Love this video, thank you Colin!

[@pervejmia8240]

Incredible idea.. we need more videos like this.. it's really helpful to improve fast thinking knowledge.

[@mircopaul5259]

Cool format, great selection of problems!

[@yoshi58003]

this content is awesome! i want you to continue this style content

[@g3nko0]

Very useful video, I found out a lot about unknown before for me properties of the mentioned in the video algorithms just by pausing and digging/googling why it's true.

[@tobiahrex]

Super duper userful Colin. I starting doing something similar where I would take questions I've solved and create Anki flashcards, with the problem & techniques that I know about. My observation is that it's using divergent thinking to lay the tools you own onto a workbench and asking "if this is the right tool, how would i use it to solve the problem?" I think this workflow maps well to any discipline so why not CP?! Please make more. Thanks!!

[@user-jc2lz6jb2e]

Question 10: Just use Newton's method. Let y= x. Then iteratively update y as follows (y + x/y)/2. Once y stabilizes and remains between 2 integers, pick the lower one.

[@Andrew_J123]

For q5, I agree on the combinatorics intuition but can you give a quick overview as to why it's that specific function I suppose. Also for q9, there's graph coloring sections of combinatorics and I think (don't quote me on this I'm really rusty at combinatorics) a chromatic polynomial type solution might do the trick, each cell of the rectangle would a node and you would have edges between adjacent cells I believe. Also I think it was a helpful video although I'll probably have to spend time going through the leetcode questions to better understand them.

[@saigirishwarrohitgeddam8429]

This is soo cooollll!!!. I Like this! Please please make more of these videos.

[@lazyemperor5182]

More vids like this, do a sequel, really enjoyed it

[@romangirin772]

Very useful video!!! Cool example for this would be 'Maximum sum subarray' and 'Maximum product subarray'. I mean, these two seem to be almost identical problems, but one solved via greedy approach and the other via DP.

[@axe8721]

Thank you much for this, Colin. Also, part two, when? ;)

[@sunnykumarsingh7039]

This is awesome !

[@user-jc2lz6jb2e]

Question 7 can just be done with a O(1) formula: floor((sqrt(8n+1)-1)/2) Let r be the number of complete rows. The ith row has i coins (possibly excluding the last), so the complete rows have 1+2+3+...+r coins. This equals r(r+1)/2, which is at most n. r^2 + r

[@sushantrocks]

Bro, try this question. Asked in one of the Faangs Given an unordered array of ints. Find all quadruples (a[i], a[j], a[k], a[l]) such that i

[@michaelbatrakov6524]

love your vids

[@FaustZZH]

what a great video thank you

[@paso2502]

For anyone wondering about the formula at 7:18 it's just a combination with repetition formula. That is (k + n - 1) over n; where k is the set from where you can take the elements(a e i o u in this case, hence 5) and n is the number of elements you need. This formula counts the amount of unique n elements groups formed with the elements of the k size set. Since there is only one way to sort these groups it also counts all the sequences that we are looking for. PS I'm sorry for my broken english, but if you need some more explanation i'll try to answer. Otherwise you can look for "combination with repetition" on internet

[@notjin2109]

ty

[@user-jc2lz6jb2e]

Question 9 with combinatorics and linear algebra: (This can probably be done by hand, I'm figuring it out while typing this out) There are "essentially" two types of rows: all 3 different, or the two outer ones the same (6 actual of each type). You only need to figure out how many rows can be put after each. (by "essentially", I mean up to some group action of flipping or recoloring) Think of it this way: It's like you have a graph of 12 nodes, each representing a valid row coloring, and 2 nodes are connected if the rows can be put atop of each other. Then, a valid coloring of the grid is just a walk in the grid, and you want the number of walks. But to get that, you just need to raise the adjacency matrix of this graph to the power of n-1 (there are n rows, but n-1 steps). Then finally multiply the result from the right by the column vector all 1's. However, you can make this graph smaller by identifying nodes of the same type together, giving you a smaller graph with 2 nodes (and a 2x2 adjacency matrix), but multiple edges between them and some self-loops. Make the new adjacency matrix out of this, and raise it to n-1, but multiply by the column vector [6, 6]^T (6 for each type). I found the matrix by hand, and it's just [3, 2] [2, 2] We need to diagonalize this, then raise the diagonal matrix to n-1, multiply by the conjugating matrices and then the vector. The eigenvalues involve sqrt(17), so to avoid floating point errors, it's best to work with a formal variable for it, create a "multiply" function, and then use binary exponentiation for a faster process. EDIT: You know what? No need for the last part with the formal variable stuff. Just binary exponentiate the matrix to n-1, then multiply by [6,6]^T. And I forgot to add: Just add the entries of the resulting vector for the final answer. Equivalently, just add the entries of the final matrix, then multiply by 6.

[@birdbeakbeardneck3617]

10:41 i think u can use linear algebra, solution is s_n=a_n+b_n with a_n+1 = 2a_n+3b_n+1 = 2a_n+3b_n and (a_1,b_1) = (6,6), the problem then is transformed to matrix power, eigenvalues..., which will requires computation but reduces the problem from O(n) to O(1)

[@tagberli]

1:00 ngl you got me there xd

[@user-jc2lz6jb2e]

Question 18: Kruskal/Prim's MST also works. If you have the MST, then just delete the edge that wasn't included in the MST.

[@giraffe4375]

Thanks colin

[@sid9882]

God bless you

[@Abhinavneelam]

Hey, Colin. Can you solve the recent CodeChef Starter problems? Some of them are very hard and I would like a different mind to attempt it. Thanks

[@samcarter8828]

for question 7 you can use math. The fornula is floor(sqrt(n*2+0.25)-0.5)

[@user-jc2lz6jb2e]

Another way to do question 8 is to have a loop that removes leaves with no apples (and thei edges, of course). Once there are no more leaves with no apples, then the answer is just double the number of edges. Note that a node with no apple might not be leaf at the start of the loop, but after removing some others, then it may become one.

[@sober_junkie5709]

what if the solution has to be strictly below O(n) ?

[@joakimolovsson7310]

For question 7, can't you solve it directly in O(1) like this: n - k(k+1)/2 = 0 k = -1/2 + sqrt(1/4 + 2n) ans = math.floor(k) Edit: sqrt(n) is O(log(n))

[@shmeepurt]

Why did you actually pause the video in the intro😭 i thought my phone broke. i love this channel

[@RohitSharma-gk9wd]

made more such videos

[@mollabeach]

do you know of any other videos / resources like this (guess the algorithm ) out there? I find it very helpful

[@michaelkanellos5899]

Linear Programming for most optimization problems!

[@samprasdsouza6993]

we can use DSU on Q4 right ?? but I guess it will complicate the solution

[@bruteforce2434]

Hi Galen, Leetcode contest editorials when?

[@thisisakshatsri]

Score: 11/25

[@cwagnello]

Being able to decide the algorithm is important. One question I have is what do you do when you don't know the algorithm, aka how to solve the problem?

[@vishnuvs6121]

I have a doubt for Q17 16:30 , shouldn't we output the longest path to make sure that every node receives the message?

[@karolinaa9478]

We find the shortest path from start node to each of the nodes. Then, we return the longest of the shortest paths.

[@anmol389]

Can you please do beginner's tutorial for soft soft mobile....please...

[@sumantkanala]

For q3, we obviously have to sort it first right?

[@Code_Solver]

Cfbr

[@caiodavi9829]

for Q18, couldnt you just remove one of the edges of the vertex with entrance degree = 2?

[@smalltowngamers9979]

is is worth studing thies algorithm in deatil?

[@faisalshaikh9061]

do you think that I should worry about not getting the solution for most of the leetcode questions?

[@rainbowman8602]

No.

[@keerthivasan9548]

Bro kindly do leetcode 862

[@caiodavi9829]

couldnt you use dijkstras at Q14?

[@caiodavi9829]

the cost of an edge from V1 to V2 is max(0, V2 - dist[V1]). just run the normal algo using this function to calculate the cost. pretty much it

[@sadeepweerasinghe]

algorithm

[@MiketheCoder]

Brains

[@ahmadsofwan4069]

First!!!

[@jesmon7951]

Yo just hit me that hard that, please, lemme go for crying. Brb.

[@035asadali8]

i am a cheater , i solve many of these problems so i know the answer before try to think

[@alperkaya8919]

It took 3 minutes and 24 seconds to video to start...

[@yajusgakhar6969]

Answer to all questions was Brute Force. Noobs

[@ramdevbaba3615]

Hey Colin can you gift me your brain 🧠 please 🙏

[@Technology-of-You]

Are you boy or Girl?

[@rohitbaisane6712]

If you want larger audience you can start teaching ds and algo at youtube.

[@johnwest8609]

Dude cut your hair no offense did you dad never like make fun of you for it

[@codingmaster008]

rofllll..

[@stephanbranczyk8306]

I vote that he keeps his hair long.