1. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.
Would you rather go first or second? Does it matter?
Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.
2. Find an unbiased decision from a biased coin. When we have a biased coin, then the probability of a head and a tail is not the same.
3. Given a dictionary of words, find all the words that are made up of two words in the dictionary. For example, mango => man + go.
4. A parking lot is unoccupied 1/3 of the time. But, you find it empty for nine consecutive days in a row.
Find the probability that it will be empty on the tenth day.
5. Given a list of alternatively sorted numbers, e.g, 20 1 25 3 29 10 30 12., design an efficient algorithm to find a given number in the list.
6. There are M sorted lists. Each list has N numbers. Design an algorithm to find the kth smallest number.
or
There is a big file containing M*N numbers. There are M machines having just enough memory to keep N numbers. Design an algorithm to generate a sorted list of all the numbers or find the kth largest/smallest element or find the median.
Hint: Merge sort using a Binary Heap Structure. Leaf nodes retrieve a number from each of the lists. A parent node contains the max/min of the leaves.
7. Design a stack which performs push, top, pop, range, and size in a constant time or with complexity O(1). Range is defined as the difference of the maximum number in the stack to the minimum number.
Hint: Use two stacks. First for keeping the numbers and the second for keeping the range for each position in the stack.
8. There are M employees in an enterprise. Each employee has a preference for working with others. Each employee rates another employee as a like, dislike, or neutral. A manager is given the task to form minimal number of groups of the employees such that no group has a employee that dislike any other employee in the same group.
Solution: Let X be the set of employees of size M. Create a graph G with a vertex set V of size M and an edge set E.. Define a bijective mapping function between X and V, i.e., every employee is mapped to exactly one vertex v in V and vice-a-versa. Put an edge between two vertices uv if at least one of them dislikes the other, i.e., create a dislike graph. Create a complement/inverse G' of the graph G. G' is a graph defined on the same set of vertices V as G, but has an edge between any two vertices uv if and only if there is no edge between u and v in G. Now the problem is to find the minimum number of non-overlapping/disjoint cliques that covers all the vertices. We can find resemblance of the problem to the well known NP-Hard problems of set cover and cliques in a graph in computational complexity theory. We can reduce the set-cover problem to our problem, thus proving that it is NP-Hard. A naive approach would be to iterate through following steps. Find a vertex with the maximum edge degree. Remove the largest clique from the graph including the vertex. Repeat the process till all the vertices in the graph are covered.
9. Given a large list of numbers, design an efficient algorithm to find the frequency of each number.
Hint: Use a Hashmap.
10. A machine is continuously receiving a stream of numbers. Give a method to report the current average.
Hint: Remember that keeping the sum is not a viable option as the value may overflow the register.
New_Number_Count = Old_Number_Count +1
New Average = (Old Average * Old_Number_Count / New_Number_Count) + (New_Number / New_Number_Count)
For very very large stream, we may again have the problem of underflow for a small New_Number. The value of (New_Number / New_Number_Count) can be smaller than the register can support.
No comments:
Post a Comment