## Sunday, February 2, 2014

### How to prepare for an interview - 12

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

111. Check if 3 points are collinear.

112. Given coins of values 1, 5, 10, 25 and Sum S, give the min number of coins that can represent S.

113. Given an array of integers, return the number of longest increasing subsequence.

114. A table composed of N x M cells, each having a certain quantity of apples, is given. You start from the upper-left corner. At each step you can go down or right one cell. Find the maximum number of apples you can collect.

115. 0-1 Knapsack problem.

116. Fractional Knapsack problem.

117. Matrix multiplication.

118. Given a sorted array with duplicates, search for the start index and end index of an element using binary search.

119. Find different combinations of all the digits of an integer number with some conditions like sum < k and they can be grouped together to form a combination.

120. Given two sorted arrays, no duplicates, could be any size, return the median number in faster than O(n) time.

Done.