I have close to only 1.5 years experience as a Software Engineer (2 companies) and I have appeared for quite a few technical interviews! These 2 firms have been really rigorous and multiple attempts have made my question-bank grow well. Here are some of the questions I was asked -
1. You have 100 balls, out of which 1 is defective (heavier or lighter, you don't know). You have 1 scale (2 pans) and you can use it only once. So in just 1 weigh, identify a good (non-defective) ball.
2. You are given a N*M matrix. Starting from the top left cell, you have to reach the bottom-right cell, 1 cell at a time. You can only move right or bottom. In how many ways can you do this ?
3. There is a staircase with n steps. A boy can climb 1 step at a time, or 2 steps at a time, or 3 steps at a time...... or k steps at a time. In how many ways can he climb the staircase ?
Example (5 stairs, k = 3): {1,1,1,1,1}, {3,1,1}, {2,3},{1,3,1}... and so on.
4. Given an array, generate a random permutation and prove that it is random.
5. How many rectangles are there on a chess board ?
6. Given a set {1,2,3,4,....n}, write code to generate all subsets.
7. A needle (length l) drops on a page which has parallel lines drawn on that. Line spacing is s. The needle makes angle theta with the lines. What is the probability that the needle does not touch the lines ?
8. There are 2 linked lists that intersect at a point. How will you find the point of intersection ? (You can visit each node twice)
9. There is a beaker full of H2SO4 (100% conc). Now water is being poured in the beaker at the rate of r/sec. At the same time, the contents of the beaker are leaking at the rate of r/sec. In how much time, will the concentration of H2SO4 in the beaker become half ?
10. (a) Implement a queue using 2 stacks. (b) Design a data structure in which push(), pop() and max() functions are all O(1).
1. You have 100 balls, out of which 1 is defective (heavier or lighter, you don't know). You have 1 scale (2 pans) and you can use it only once. So in just 1 weigh, identify a good (non-defective) ball.
2. You are given a N*M matrix. Starting from the top left cell, you have to reach the bottom-right cell, 1 cell at a time. You can only move right or bottom. In how many ways can you do this ?
3. There is a staircase with n steps. A boy can climb 1 step at a time, or 2 steps at a time, or 3 steps at a time...... or k steps at a time. In how many ways can he climb the staircase ?
Example (5 stairs, k = 3): {1,1,1,1,1}, {3,1,1}, {2,3},{1,3,1}... and so on.
4. Given an array, generate a random permutation and prove that it is random.
5. How many rectangles are there on a chess board ?
6. Given a set {1,2,3,4,....n}, write code to generate all subsets.
7. A needle (length l) drops on a page which has parallel lines drawn on that. Line spacing is s. The needle makes angle theta with the lines. What is the probability that the needle does not touch the lines ?
8. There are 2 linked lists that intersect at a point. How will you find the point of intersection ? (You can visit each node twice)
9. There is a beaker full of H2SO4 (100% conc). Now water is being poured in the beaker at the rate of r/sec. At the same time, the contents of the beaker are leaking at the rate of r/sec. In how much time, will the concentration of H2SO4 in the beaker become half ?
10. (a) Implement a queue using 2 stacks. (b) Design a data structure in which push(), pop() and max() functions are all O(1).
