So here’s an interesting problem: Given an NxM integer matrix in which each row is sorted, find the overall median of the matrix assuming N*M is odd. For example,
Interpolation search is an algorithm for finding a given key in a sorted array. While binary search always chooses the middle element for comparison, discarding one half of the search space or the other, interpolation search tries to predict where the key would lie in the search space via a linear interpolation, reducing the search space to the part before or after the estimated position if the key is not found there. This method will only work if calculations on difference between key values are sensible.
This problem appeared in Round 1A of Google Code Jam 2013. Here’s the problem description: