## Tuesday, February 4, 2014

### How to prepare for an interview - 13

Back to a new set of problems. If you didn't read previous posts start from here. Read previous post here.

Remember you should discuss these solutions with me, and refer if there are mistakes or other good solutions.

Problems

121. Divide two numbers a and b.

122. Sort a binary tree and give the complixty of that.

123. Find all sub sets of size k from given set.

124. Given a sorted array and number x, return the index of this number in the array and if not exist return the index it should be inserted in.

125. Implement a read/write lock, given a mutex that has lock() and trylock() interface.

126. Prints the best collection of N coins that minimize the average number of minimum coins needed to generate values from 1 to M. So, if M = 100, and N = 4, then if we use the set {1, 5, 10, 25} to generate each value from 1 to 100, so that for each value the number of coins are minimized, i.e. 1 = 1 (1 coin), 2 = 1 + 1 (2 coins),..., 6 = 1 + 5 (2 coins), ..., 24 = 10 + 10 + 1 + 1 + 1 + 1 (6 coins), and we take the average of these coins, we would see that the average comes out to ~4.7. But if we instead use {1, 5, 18, 25}, the average would come out to be 3.7. We are to find that set of N coins, and print them, that produce the minimum average.

127. Implement a stack using only queue(s).

128. Print a bst in a sorted order.

129. Write a function that returns the largest sum you can get by adding together numbers in non-adjacent indices from the array. I.e. you if you include the things stored in arr[i] in your sum, you can't include what is stored in arr[i-1] or arr[i+1].

130. Given a m*n grid starting from (1, 1). At any point (x, y), you have two choices for the next move:
1) move to (x+y, y);
2) move to (x, y+x);
From point (1, 1), how to move to (m, n) in least moves? (or there's no such a path).

Done.