Interview Experience 107

#2018

SDE

First Round-

• Matrix 01 sorted
• Given a 2D matrix with only 0 and 1, placed such that each row is sorted. Find the row with max no of 1s.
• Snake and ladder - Given you can control the outcome of the dice roll. What is the least no of moves in which you can complete the game.

Second Round-

• Tree equal distance nodes
• Given a binary tree, a node in the tree, and an int k, find all nodes in the tree that are at a distance k.
• String matching - Given a large string and a small string, find the number of times the small string appears in the large string. (KMP discussion)

3rd round-

• Optimize calculaions - A machine has many cores and can do multiple tasks in parallel. Each core can compute the following in time K- adding any no of numbers (a+b+c..) subtracting two numbers (a-b) multiplying any no of numbers (abc..) Given any string (with +/-/*) to calculate the answer for, what algo/logic would you apply to solve it in minimal time. String eg-> a * (b + c + ((d * e) - f) + (g - h) + i + j

• Sort very large file in disk, using very little memory.

• Given a file with 10000 numbers, sort them using little memory(say 100).