Advanced algorithms in google interview
What should one prep for google interview in terms of advanced algorithms and ds? Anyone can recommend a list of "should know" knowledge? Failed Google on-site recently. Got asked a question related to segment tree. Yoe 3, tc: shit
YOE?
3
Usually, on advanced algorithms, they don't ask hard questions. Most probably, plain implementation of segment tree would be sufficient. I mean lazy propagation and variations of segment tree won't be asked. It's always good to be equipped with Segment tree, Binary Index tree and Tries. To be extra cautious, suffix trees and arrays. Other than this, if asked, Good Luck! Bdw, how were your other rounds? What type of questions were asked?
Thanks. I believe other rounds are fine, not great. It starts with a medium problem, I arrive at the optimal solution then code it. No time for follow ups
Seriously doubt that using a segment tree was the easiest / intended solution. Can you elaborate on the question? Usually the hardest questions you will get from G will be Union Find, DP, or maybe some complicated bit manipulation.
Yeah that question is very plausible, I admit I was wrong.
Hmmm - do you mind sharing a brief description of the questions? (Don’t provide the exact question due to NDA) I’m asking since you might be over engineering it. Maybe it’s just a tribal trie, or other basic DS/DP problem.
Check also fenwik tree, it’s simpler
Thanks. will check it out.
Usually segment tree, trie, and udfs. And always prepare for dynamic programming for google
What’s udfs?
I guess he means UFDS which is union-find disjoint set.
Google interviews were invented by idiots. Not surprisingly, as many other idiocy ideas, it has many followers. They also are trying to follow the ideas of that old fart Robert Martin, who thinks he is Confucius.
which idea of Robert Martin is bad?
That a software engineer must work 60 hours a week and be paid only for 40? In all his ideas he takes a moral stance peppering everything with stories about himself. It's his opinion how to be *righteous* devoted developer or architect. No wonder his books became a gospel. Because it's not science, it's preaching. This is why I compare him to Confucius. It's funny, some of his ideas come from his ADD. He probably even doesn't realize that. He doesn't care about being logical or base everything on science. It's all about the right public roar of support. He is too much like Trump. Check out his "WTF is monad".
Can you iterate through an array without turning it into a complicated mess? It's what the 99% do day to day anyway, and it eliminates a surprising amount.
Focus on dp and greedy style.
Which level?
L3/l4
I don’t think they generally ask these advanced DS. I haven’t heard anyone asked a DS more advanced than a Trie! I have tons of friends who work at Google and another bunch who recently interviewed at google! Probably, you had a hard luck! P.S.- I cleared Google on-site last week! I have 3 YOE!