Google SDE Interview Experience (On-campus)

In this post, I'll be telling you about how I landed into an interview with Team Google. I didn't get an offer but then my experience can be useful for other aspirants. Overall the interview was of intermediate level.

Online Coding test:

It all started with one of the Google Kickstart competition. Kickstart is an online coding competition from which top participants are invited for an interview at Google. It has various independent rounds all along the year.

I participated in Round F and solved 2 out of 3 problems completely. My score was 48 and rank was 124.  Google's team came to our campus after this round F for giving a pre-placement talk. They officially announced that they will consider the upcoming Round G for shortlisting for interviews.

I participated in Round G and got a rank of 496 after solving 1 out of 3 problems completely. My score was 17.

For the coding competition questions, refer to the archive of kickstart.

I got shortlisted for the interview and I guess all those who had 17 or more marks were shortlisted. Roughly 15 or 20 people were shortlisted. There was resume shortlisting too I guess since some people got shortlisted even with a score of 0.

Interview Process:

Each interview was of 45 minutes. I had 4 back to back rounds.

Round 1:

I was asked to code two questions about an almost complete binary tree.

1. Assume all the nodes in the binary tree are numbered according to level order traversal starting from 1. Given a number n, find if the nth numbered node is present in the tree. The tree is an almost complete binary tree.
2. Find the total number of nodes in the almost complete binary tree using the above routine.

Link to the possibly same question: Leetcode Post

Find time complexity for both functions.

Round 2:

This was a system design interview. There are offers for a product by multiple vendors with different prices. There are multiple products. Each product has a certain product_id. For each product id, there are multiple prices available in the market. Each offer has a certain offer_id, product_id and price attached to it.

Code up three functions:

1.  add_offer(product_id, offer_id): Given product id and offer id, add an offer for the product with the given offer id.
2.  remove_offer(product_id, offer_id): Given product id and offer id, remove an offer for the product with the given offer id.
3.  find_offer(product_id, budget_price): Given product id and budget_price, find an offer for the product with the given budget_price, if available. If not available, return an offer which has the closest price to the budget_price.

There were some other catches like two offers for the same product can have the same price.

Round 3:

This was again a coding interview Two questions were asked.

1. Given two strings s1 and s2, break both strings at a certain index 'j' such that s1.substring(0,j)(with jth character exclusive) + s2.substring(j,end) is a palindrome. 
• For eg:
• s1: abcccx
• s2: xyddba
• if we cut at index 2, then (ab + ddba) is a palindrome. Hence the answer is 2.
2. Another question was a popular one on game theory. There are 2 players. Each player can take 1/2/3 coins. Each coin can have different values from -k to +k. The player with the total maximum value, in the end, will win. Return whether player1 wins or lose and total points player1 has. Assume both players are playing optimally.
• For eg:
• Coins: 1 -1 -1 -1 100
• Answer: Player 1 wins with 99 points.

Round 4: 

This was a more maths involved interview.

1. There is an n-ary tree. There are two players. Each player can choose any one node initially. Later the player can only choose nodes in a way such that all his chosen nodes are connected. Each player is playing optimally. Both of them can choose only one node in their turn. In the end, the player with maximum nodes will win.
• What is the strategy to choose a node after player 1 has chosen some node?
• If you are player 1, then what node will you choose?
• I gave her the intuition, the interviewer seemed satisfied but in the end, she said it would have been good if I could formulate all the explanation mathematically.
2. Given n lines of a poem, return total no. of possible combinations of rhyming schemes.
• for eg:
• n=2
• AA, AB are two possibilities for the rhyming scheme. Here, in AA, lines 1 and 2 have rhyming. In AB, there is no rhyming in any lines.
• Answer: 2.
• n=3
• ABA is one possible combination where line 1 and 3 are rhyming.
• Note: ABA is similar to BAB. Only one of them will be counted in the final answer.

This was the last round. There was no HR round.

Hope this experience will help you to land a job at Google. Let me know in the comments if you have any doubts about the experience. All the Best :D.