Were they even looking for answers?
I recently had an on-site interview at Google and some of the rounds seem to have went well, while others not so well. I think the two rounds with female interviewers didn't go well and they asked me pretty open-ended questions : 1. Give an algorithm to find the vertex cover of an undirected graph. - I gave a polynomial time solution without proof and when she highlighted an edge case, I refined it to include it too. After that, wrote some Python code for it and didn't have enough time left to prove or disprove it. She didn't say anything about the time complexity or correctness of the solution but she was a fairly new dev with one or two years of experience so the round seemed to have went well. But, later the recruiter told me otherwise and I found out that this is an NP-hard problem without any known polynomial time solution, but only heuristics or approximate solutions, like the given by me. So my approach and solution was fair enough? 2. This was the final round. The interviewer was a senior software engineer and she asked me to design Google news. She asked me to fill in as many details as possible and was probing about my approach. One thing she perhaps particularly was stuck on was - how will you scale it for almost instantaneous lookups or results, just like Google search. I think I couldn't answer it well enough but only gave reasons like hardware/software level optimizations might help. But, isn't that the magic of Google? That they are able to process and show results at such a large scale so quickly and efficiently? How can I even know the answer of this? She also asked about the ordering of news articles and how I would rank them. I told I would use something like Alexa rank or another ranking algorithm, which also happens to be a Google trade secret. Did she really expect me to know all these answers and explain them to her in 45 minutes? She didn't offer me any further insights on how these could work but maybe a minor hint on regional caching. Again, I'm not sure if this is a normal round or were they really looking for answers? Maybe they are just looking for an approach to such open-ended or unsolved problems, but then the question is, how can they even know the correct approach, without knowing the correct solution?
System design is always open ended. But still you should never say that it's all magic. Your solution might not be the most efficient but still you could have suggested something specific like caching
It's your job as the interviewer to constrain the problem into something both you and the interviewer can agree on, and then to dive deep into the problem. Read this: https://www.rooftopslushie.com/request/Google-System-design-interviews-156
Your coding round sounds poor. Attempting to solve an NP-hard problem with a polynomial time solution and not catching edge cases on your own are both bad signs.
Ok. So I should have identified it as an NP-hard problem to begin with and then gave the naive exponential solution and then the polynomial time approximate solution? How do I claim that a problem can't be solved in polynomial time when it's not known if P=NP?
What did you discuss with your interviewer at the start of the interview?
Was that your first time interviewing at Google?
First time for an engineering role.
Hope you learnt a lot from the experience. They are many YouTube videos that teach people how to do interviews.
Cache is absolutely critical for search result. That’s all I know though lol
Ha ha... Yeah. But at the scale of Google even that falls short. Don't know how they do it.
Clearly the issue is that they were female. Good thing you mentioned that detail, otherwise we would have never gotten to the bottom of this
Recruiter gave me feedback without me asking for it. She told me what she received and it seemed as if the only two rounds that didn't go well were with the ladies. I'm still guessing this but surprisingly this seems to be the case. I still can't understand how a company as irresponsible as Google in hiring candidates, be so big and well known. Forgive my bias but now I'm beginning to smell a distinct odour from everything American and that smell ain't good. The bigger fact and the perhaps the most ridiculous thing about the entire process is, that these questions have nothing to do with either the job description, the work responsibilities or my work experience/domain. US and the American tech companies are a marvel just like your comical superheroes indeed.
I'm not going to invalidate your feelings, because I understand emotions run high when it comes to things like this. It's just a shame you didn't adopt a different mindset coming into this. There's a game they want you to play, and imho I thinked you ignored it and set different expectations
Obviously you went in unprepared. Look up system design interviews for faang. Pretty standard stuff lots of YouTube tutorials
For system design I'd agree. But for NP-hard problem?