Interview Questions 16

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.


About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

8 Responses to Interview Questions 16

  1. cobra says:

    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?

    • Avi Dullu says:

      This wouldn’t solve the problem. You are not getting a random k 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.

      • cobra says:

        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.

  2. Avi Dullu says:

    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.

  3. Amar says:

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

  4. Amar says:

    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?

  5. Avi Dullu says:

    The 2 children pointing to their parent.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: