## Tuesday, February 4, 2014

### How to prepare for an interview - 14

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

131. How would you store and search 1 million names?

We can use HashTable. Or use External sorting to split the names and then merge them searching for the needed word.

132. Function to compute the number of ways to climb a flight of n steps. Taking 1, 2, or 3 steps at a time. Do it in Linear time and constant space.

Example:

Input:     n = 3.
Output:
1 1 1
1 2
2 1
3
Ans = 4

133. Interweave a linked list. Do it in Linear time and constant space.

Input: A->B->C->D->E
Output: A->E->B->D->C

134. Merge 'k' sorted arrays, each array may have max 'n' elements.

135. You have 9 balls, one of which weighs less than the others, but identical in appearance. If you had one weighing scale, how would you find out which ball weighs less? What would be the time complexity.

136. Implement the "see and tell" algorithm with a given seed number x and a number of iterations y. Output the result on iteration y.

137. A period of time where users login and logout, given a sets of login and logout time pairs, write a function that can show the number of users online at any given time.

138. Given a sorted array, write a program to decide if two elements sum up to a third.

139. Determine the 10 most frequent words given a terabyte of strings.

140. Giving lots of intervals [ai, bi], find a point intersect with the most number of intervals.

Done.