Background
LC：850+
YOE：4+
Education：MTech（IIT）
General Introduction
I completed all three rounds of DSA interviews, but the Google cultural fit test (Googliness round) was postponed multiple times (specifically the fourth time). Is this related to the feedback from the previous programming round (none of the rounds met the >= hiring standard)? Since this is a cumulative feedback system, the recruiters did not update the feedback after each round. I resolved all issues and follow-up questions, except for the first round where I was unable to complete the code for the follow-up questions, but I explained the approach clearly.
The Interview Process
Round 1: DSA
Q:Given a piano where you can only use one hand to play. You will place your hand on the piano and can play the five keys. In order to play a key which is not in range you will have to raise your hand. Find the minimum number of hand raises to play all the keys in given order.
Follow up: return the list of thumb positions you actually use—so you can see exactly where your thumb goes for each segment
Solved the initial problem with (2 approaches) optimal time & space complexity but could complete the follow-up coding. Although was in the right direction.
Interviewer was satisfied but told he wanted to get more out of me. Did communicated well with dry runs but unfortunately couldn't complete coding.
Round 2: DSA
Q: On my disk, I have a file system. The file system contains files which have a known size and directories that either contain files or directories. And I want to know, given any point in this file system, what's the total space it's consuming as I got a bit confused due to time running out.
Follow-up 1 : what happens when we need to add files?
Follow-up 2 : service is timing out on boot.
Was able to code optimally for the initial question and the first follow-up 1. There was no time left for Follow-up 2 but explained the approach verbally. Interviewer seem satisfied. Followed OOD for coding. Communicated well with dry runs.
Round 3: DSA
Q1:write an algorithm to find the top K most frequent words in a document. And I have to assume that the document is already parsed. So, I can read the document as an array of strings. For example, there is a set of words in the document array. So, Google, Bike, Pencil, Google, Bike, Google. So, the top two frequent words are Google and Bike.
Follow-up 1: What would you do if your document, not the words document, was not an array of strings, but it was actually a stream?
Follow-up 2: what happens now if your integer k is 0?
Q2: write an algorithm to perform a prefix search. For example, given that we have the words Google, Good, Grape in our dictionary, and a search for Goo, it should return Google and Good, but not Grape.
Follow-up 1: what happens when your prefix is an empty string?
Solved both coding with optimal approach and answered all follow-ups via code / verbally as directed by the interviewer. Interviewer seemed satisfied as I was able to complete everything before time. He asked or pointed about few special and edge case scenarios which I answered or modified in my code as per discussion.
## Interview Summary & Suggestions
During these three rounds of interviews, I demonstrated a certain level of algorithm design ability and unique problem-solving skills, but some follow-up questions were not fully addressed. I recommend that everyone prepare for interviews by ensuring coding completeness and time management, as well as focusing on resolving follow-up questions. It is also important to reinforce your algorithm fundamentals. If you encounter any difficulties or have any questions during the interview, feel free to come here to find solutions!
Top comments (0)