A game of timing

Beginnings

• I had applied to Google once 3 years ago and got rejected that time in the telephonic round because I couldn't implement the 2048 game's state change algorithm.
  • At that time, did not know about leetcode, was fresh out of college and could be easily described as a dumb egotistical ignorant idiot with just a little bit of brains. Actually 4 years on, I think that description is still valid :).
• My process started in Jul-21.
• Recruiter reached out over Linkedin.
• We agreed to do the telephonic rounds in Aug-21 first week.
• Took up the leet code subscription this time as I really really lack practice :| .

Telephonic round

• Interviewer started with a question from my resume.
  • Answered that to his satisfaction in 5 mins.
• Implementation of finding connected components in a Graph.
  • Implemented in 15 mins, 5 mins spent in complexity discussion, worse case analysis (I got confused here and interviewer had to hint the worst case ).
• Then a situation based problem, which required the above implementation as a sub-routine. Had to do some preprocessing on the Graph which was O(n^2) so interviewer wanted to optimize that,
  • Couldn't fully get the answer to this one just gave the first guess that came to mind.

Result : Passed and on to Onsite rounds.

Onsites

Given my lack of practice, I asked onsites to be scheduled after 4 weeks in Aug-1st Week. Onsites happended virtually over 2 days (2 rounds of 45 mins each day).

Round 1

• Another question on Graphs. This one required BFS.
• Implemented in 25 mins, complexity discussion took another 10, again got confused with the worse case :I-really-should-practice-a-lot-more-sigh:
• Then a complication in the question, required to remove the tracking of visited vertices and cleverly handling edge cases to avoid infinite loop.
  • Modified the code but missed to handle the edge cases correctly and ran out of time (:so-much-lack-of-practice-sigh: ). But verbally explained during the dry-run that this code has this issue.

Round 2

• Yet another question on Graphs, question was similar to Most-stones-removed-with-same-row-or-column
• Had solved this during my practice, but the way the question was given took me 15 mins to figure out how to do it in O(n).
• Again worse case analysis got me confused ::I-really-need-to-practice-a-lot-sigh:. Wasted 10 mins and didn't arrive at the answer until interviewer hinted.
• Implementation took another 15 mins.
• With only 5 mins remaining interviewer asked a variation of Insert-Delete-GetRandom-O1
• Had practices the above, but the variation asked was tricky to think through (:as-you-know-by-now-I-lack-practice-sigh:), so gave the simplest solution coming to mind.
• Immediately, interviewer gave me a case which failed my solution (:man-this-guy-is-good:).
• Interviewer knew 5 mins were up so he added another 5 just to see if I could correct it, but I didn;t get much far.

Round 3

• Yet another question on Graphs
  • This one required topological sort on a DAG.
    • Interviewer did not give any starting function signature, so I assumed the data-type to be a Graph of strings and explained that it could be wrapped into a model if needed.
    • Implemented in 25 mins , dry-ran, and complexity analysis all done in another 5.
• For the follow up, interviewer asked how to detect a cycle in the Graph by modifying the implementation above.
  • Used extra memory to solve it.
• Interviewer was satisfied and we still had 2 mins so I asked him a few questions and we ended on time.

Round 4

This was Leadership and Googlyness round, a lot of situational questions / past project experiences nothing on Algo and DS. We finished on time.

The waiting game and its consequences

• I had heard Google takes a while to come back with results. In my case the Onsite results came back 4 weeks later (1 Week of Sep ).
• My packet went forward till HC but they rejected it for L4 with the explanation that I lacked quick-solutioning / coming up with the most optimal solution on my own.
• They recommended L3, with an additional round to test something else.
• But here's the catch, being the idiot that I am, I stopped practising completely after Round 3. So for a month I was just sitting around letting all my practice wash away and filling my brain with utter garbage in exchange.
  • On top of that, never even bothered to email the recruiter early on.
    • I sent the followup email in the 3rd Week of Aug and got the reply in the 4th Week.
• I was dumb enough to commit to the additional round 2 weeks later and started cramming up again.
  • This time I did not even prepare well, just kept practising medium problems with a timer about 2 hrs a day, even wasted a few days in dejection and festivals.

Round 5

• Question on Trees and Strings.
  • First interviewer asked to design the Tree Node to contain the information relevant to the problem.
    • Completed in 10mins. :I-wish-I-wasn't-so-nervous-to-go-so-slow:
  • Then the actual question to handle the deletion of data in the tree.
    • Being recursive, I thought I would straightaway dive into implementation, but interviewer suggested to try outlining the cases first.
    • As usual, lack of practice + nervousness = I took about 15 mins outlining cases.
    • Finally, started to implement, and wrote absolutely garbage recursion in 15 mins. First dry run and I knew this round was gone.
    • Tried to fix a few small things in the next 10 mins ( was again given a 5 mins grace ) but realized 15 mins after the interview was over that I was easily missing 4 cases still.

Epilouge

All's well that ends well.
As expected, in my case, it did not end well :D . Got the call from the recruiter a week later ( :today-the-day-I-am-writing-this: ) and got to know that the HC resulted in the no-hire decision.

I am not disheartened. In fact, I am surprised I made it this far. By my own judgement, I should have been rejected a long time ago. Also, I stopped preparing and hastily interviewed and practically wanted to be over with it by the end of the process, so I think I deserved to be rejected.

I will try again next year. Recruiter was kind enough to let me know to reach out when I am ready.

This time I will be ready. That's my promise to myself.