Question

Google | Interview experiences | SDE | 2022 | Set-37

Answer 1

Google | SDE | Bangalore

Location: Bangalore
I got call through employee referral

 

Telephonic Round:

 

Time/Space complexity of some sort algorithms(merge sort, quick sort)
Calculate 2^24 (Asked to check how interactive you are with the interviwer)
 

Round-1(Skype):
You have N dices having K faces each numbered 1 to K. What's probability of generating sum S by rolling all N dices.

 

Solved with DP

 

Round-2

 

Given a array of pairs(start IP and end IP ) of IP address, and one more IP address as a input. Return the index of a pair in which the given IP address lie.
Solved using binary search

 

Round-3

 

Given a complete binary tree. Find the total number of nodes in tree.
Tree was structured in such a way that: If it has N nodes, it will give numbers in 1,2,3,..., N after level order traversal.

 

Solved using DFS and Binary Search

 

Round-4
It was a googliness and culture fitment round
I was asked various situation based questions. It was just to check your thought process and confidence

 


 

Round-5 (On-Site)
A question related to string was asked. Don't remeber exactly.
Gave brute-force approach.

 

Round-6

 

 

A matrix of size mxn was given which consists of 0 or 1 only. Find largest possible square having all 1's.
Solved using DP

 

 

Give array of numbers. If same element exist in a sub-array of lenght 3 or more, remove all of the element in that sub-array. Return the resultant array after performing above operations.
Solved using stack. Store element with the contiguous count of that element

Verdict: REJECTED