# Interview Questions 16

September 20, 2010 8 Comments

1. There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.

2. A file is given with many 0s stored in continuous way , store it in another file such that when you store try saving the space by using minimum amount of space. When you want to create the original file , you should be able to do so with the new file created.

3. Propose a data structure that would store numbers, without any knowledge about them, and allow to perform the operations: insert, get median, as efficiently as possible. Modify/optimize your design, only this time the numbers are from a group V, which is |V|<<n. [Hint: O(logn), O(logn)]

4. Given N computers networked together, with each computer storing N integers, describe a procedure for finding the median of all of the numbers. Assume that a computer can only hold O(N) integers (i.e. no computer can store all N^2 integers). Also assume that there exists a computer on the network without integers, that we can use to interface with the computers storing the integers.

5. [**Interesting**] Calculate the Resistance in ohm’s that a knights move would require on an infinite plane of resistors of unit resistance.

6. Given a binary tree with the following constraints: a) A node has either both a left and right child OR no children b) The right child of a node is either a leaf or NULL write code to invert this tree.

7. Suppose you are getting an infinite binary stream of characters then after any point of time you need to print whether the no is divisible by 3 or not, how will you do that? [Hint: A nice example of finite automata based algorithm design :)]

8. An array is of size N with integers between 0 and 1024(repetitions allowed). Another array of integers is of size M with no constraints on the numbers. Find which elements of first array are present in the second array.

9. Design a datastructure to represent the movement of a knight on a chess board.

10. On a empty chessboard, a horse starts from a point( say location x,y) and it starts moving randomly, but once it moves out of board, it cant come inside. So what is the total probability that it stays within the board after N steps.

For the 1st question … take the number stored in 1st node(let it be n1) … then move to the n1 th element from the 1st element and store it as 1st random number (r1) … next move further r1 times to get the second random number (r2) .. continue it ‘k’ times to get k random numbers. Will this solution do?

This wouldn’t solve the problem. You are not getting a

randomk numbers from this. It’s like, everytime you try to generate k numbers you will always generate the same set of numbers.Hope you get my point.

By the first number I meant the seed that will be provided .. e.g. if my function name is rand(int seed) .. so for the first time I’ll take the number present on the seed th location .. and then rest of the algorithm continues as described above … if the seed will not be provided, in that case system clock can be taken as a seed which will always give a unique number.

Still the distribution is not random. Random number generators provide a random number with a particular probability. Since you do not know N, you cannot ask the random number generator to produce a number with probability 1/N. So you cannot choose your first number with equal probability for all possible numbers. Beyond that is an other issue.

Hi,

For question 2, What is the set of characters that will be in the file?

Don’t make any safe assumptions based on it. Consider them a set of all characters ASCII and extended ASCII. 🙂

6. What do you mean by inverting a tree? Is it inverting upside down?

Lets take the base case: rchildlchild

Here we have a root with two children. How do we invert it?

The 2 children pointing to their parent.