Google | L4 Bangalore | Reject

Recruiter reached out on LinkedIn. This was my first crack at Google. So after the initial call with the recruiter and applying on the portal, they arranged for a mock interview since this was my first time interviewing with Google.

Screening round
Interviewer was from Munich. Very nice and personable.

In a matrix that contains zeros, there might exist a square matrix of ones. If it does then that is the only square matrix of ones, there are not others. Find the size of the square matrix and the position of the top left corner.

It was different type of question compared to the standard DSA questions. We discussed the approach , time complexity , ways to improve it and choice of output data structures.

Verdict: Pass

Round 1
It was with an Indian interviewer who seemed least interested in the interview.

The question was given 3 numbers and a target , find the expression string that evaluates to the target using only +, * and () .

(2 + 3) * 4 = 20

The numbers had to be in order and order can't be changed.

First he asked how many different combination are possible , then I provided a backtracking approach. He seemed fine.
While implementing it , it seemed a little too tricky to implement it.
Since he mentioned there are only 3 numbers, I suggested a brute force approach with with all the six combinations.

He seemed fine with it and I implemented it

I was not satisfied with this round , the question seemed odd.


Round 2
Given a fence with different heights and width of 1 meter. Also given a brush with width 1 meter. I can colour the fence either horizontally and vertically with the brush in one stroke. Return the minimum amount of strokes needed to paint the fence

input = 1 2 2 1 2
minimum strokes = 3

I implemented an Optimal solution using a divide and conquer algorithm
This round went well without any hiccups

Round 3
Given a stream of inputs in a messaging system like

{"A", "C", "Message 1"}
{"A", "B", "Message 1"}
{"C", "A", "Message 1"}

Implement the following methods,

registerEvent(user1, user2, content)
getFrequent() -> returns any user who has been mentioned maximum number of times across all threads. Multiple communication with the same individual are counted as one

Follow up
Find the top k user
I mentioned both heap based approach and quickselect
Told me to implement the heap based approach. The interviewer was satisfied

Round 4
Standard behavioural rounds. This round was easy


Final Outcome
The recruiter called after a few days and said it was a great attempt but not moving forward with my application at this point. Did not provide round specific feedback. Just said I need to improve coding speed and edge case handling.