Round 1 (Written Test) -
There were 2 questions and total time was 1 hr.
1. A variation of this problem -Add two numbers.
- Input numbers were in their "correct order" i.e. 69 was input as 6 -> 9.
2. Given a binary tree, connect nodes at each levels such that they form a linked list (from left to right)
The written programs were supposed to handle corner cases as well.
Round 2 -
1. Given a number N, print all numbers less than N such that their adjacent digits differ by exactly 1.
Ex. - if N = 26, op = [10, 12, 21, 23] i.e. first and second digit differ by exactly 1.
2. You are given a matrix M whose row represents how many people do you know at a party.
Ex - M[4] = [ 0 1 0 1 1], then 4th person knows 2nd, himself and 5th person.
Celebrity of the party is a person who knows no one but himself and everyone knows him. Find the celebrity.
This round lasted about 1 hr. The interviewer was very helpful as well.
Round 3 -
- Given an array, find if there is a subset whose average equals given number AVG. I couldn't solve it so, then interviewer asked me to check if there is a subset whose sum is AVG. I was able to give a 2^N complexity solution.
- Given a binary tree with an infected node such that the infection spreads to connected nodes in unit time, find the time required for the entire tree to be infected. I was not able to solve this completely.