Interesting CS Interview Questions #2

This post is a continuation of my interesting CS interview questions series. The last two problems discussed in this post lean more towards logic and probability rather than a CS concept.

Consider the Lock and Unlock operation defined on an m-ary tree as follows:

Lock Node X => If (no node present in the subtree rooted at X (including X) is locked) AND (no direct ancestor of X is locked), then lock X

Unlock Node X => Assumes that it is called only a node that has been previously locked. Simply unlocks the node X.

Design an efficient data structure and algorithms to perform the required lock and unlock operations.

The first solutions that struck me was to simply perform a complete tree traversal and determine if the required conditions for locking are being met or not. This has complexity O(N) where N is the number of nodes. Is this the best that can be done?

On further thought, since we can decide the data structure which suits us best, we can improve the efficiency. Suppose for each node we have a pointer to the parent node. Then, determining if any direct ancestor is locked is simply a loop that climbs the tree, via the parent pointers. How to check if any of the children in the subtree is already locked? Another traversal is possible, but it would not improve our time complexity. If a node is locked, all the direct ancestors need to know that a child is locked. So, this gives the idea to use a flag for each node which is set if a child is locked. Now the lock operation can check if a child is locked in constant time. After locking successfully, it needs to traverse back up to the root via the parent pointers and mark for each node that a child is locked.

How will unlock happen then? We just unlock the node that is given, but we cannot simply unmark the child-node-locked flags in the parents. Why? Because there may be other children that are locked! This seems to complicate things. But not really. Instead of using a flag to hold the information, we use an integer. The integer simply counts the number of child nodes locked. Thus, while unlocking we simply decrement these counts.

Now, what is the time complexity? It is logarithmic because we only look at the path from the node to the root (via the parent pointers).

This one is like a puzzle. A table has 100 coins, 30 of them with Heads facing up. There is another table with no coins. With your eyes blindfolded, what will do so that the number of coins with Heads facing up is equal on each table? You cannot determine if a coin is facing Heads up or not by touching it. You are basically allowed to flip coins and move them from one table to the other.

This problem was pretty challenging for me. Initially the number of Heads in each table is 30 and 0. After experimenting various things with a smaller number of coins, one notices (or at least is supposed to notice) that moving one coin from the first table to the second and flipping it causes the difference in the number of Heads between the tables to decrease by 1. Why? Suppose the coin was a Head in the first table. On flipping and moving it to the other table, the number of Heads in the first table decreases by 1 but the number of Heads on the second table remains the same (as it is added to the Tails count). If the coin was a Tail, then it increases the Heads count in the second table without affecting that of the first table. So the solution is to repeat this process of choosing some coin and flipping it, and moving it to the other table, 30 times. Since the initial difference in the number of Heads is 30, after this process the difference becomes 0. Thus, the number of Heads is equal in each table.

Given a long stream of numbers, how will you choose a single number, such that it is uniformly random among the numbers so far seen?

Although, one can store all the numbers and then choose one at random using standard random functions (like in C), we would like a method that is space efficient. There does exist a method that requires only constant space. Any idea?

Say we have reached the N-th number in the sequence and suppose we already have the solution for the first (N-1) numbers that appeared in the sequence. Suppose this solution is X. Then X was chosen with probability 1/(N-1) from the first (N-1) numbers. Since the N-th number in the sequence should have a 1/N probability of being the random number chosen among the first N numbers in the sequence, we decide if it is indeed the chosen random number with a probability of 1/N. Suppose it were not, then the number X will be the random number chosen. We can verify its probability by noting that it is given by (1/(N-1))*((N-1)/N) = 1/N. Thus, we have the solution: for the i-th number in the sequence, choose it as the random number with probability 1/i, otherwise, do not modify the previously chosen random number.