@i_pranavmehta: My Google DSA/coding interview...

My Google DSA/coding interview experience.
Some learnings included!🧵

After basic introduction.

She shared a problem which imo was equivalent to a LC medium.

Me: This would form a tree structure, but could you tell me how's the input gonna be provided?

She: a list of pairs denoting relationship between the manager and employee.

Me: I started coding while explaining itself as the logic was already clear in my head.

**it would've taken me 3-4 minutes to code it up ig (that's generally how long I take to code up LC easy-med).

She: can you now extend this problem to calculate the average rather than just summation at all levels?

**I had intentionally utilised an additional function here as I was expecting this sorta extension.

Me: Sure!

**Had to make 3-4 lines of code changes (just the return values and a slight logical change). Took another 2 mins.

She: could you dry run this? And let's check how this is working?

Me: yeah sure! Let's take an example of ......

**basically explained the entire flow and it looked fine! It was barely 15 mins now and I had solved both the problems, so she complicated it again!

I tried thinking of this complicated problem for a couple mins and couldnt think of an optimal solution so I coded a bruteforce solution.

She: yes this would work, but let's optimise this.

I was having 0 clue for the next several minutes.

Finally a solution clicked! A modification of Euler tour of tree (ETT), which enabled me to optimise the solution by using 2 segment trees.

But there was no way I would've coded it in the remaining 10 mins.

Me: do you need to code this up?

She: No! Just logic would do!

Me: explained the entire ETT (this is at least a 2200 level CF) in the next 5 mins, and she was convinced and satisfied 🙌.

She: any questions you might have for me?

Me: asked some basic standard things and signed off!

Result: cleared! ✅

However this is the lesson I learnt (based on chats/spaces I had later): Interviews arent meant to be this hard, had I not tried taking is as a contest had explained the thought process patiently without jumping on to the code, it might have never gone to the ETT part.

Interviewer tries to understand your thought process, try explaining without any assumptions of him/her knowing stuff already, also when you make assumptions about the problem definitely try to make it explicit! So as to avoid last minute failures.

I hope this helped! Will write another thread on the interview experience of my current job, based on response this post gets!