Google likes to ask interview questions with extreme cases. For example, those problems couldn't be solved with one computer, or, the data set is so big that it runs out of hard drive, etc. Below are some interesting Google interview questions for you to chew on.
* Given an array, you are given with three sorted arrays (in ascending order), you are required to find a triplet (one element from each array) such that distance is minimum.
i) find the longest continuously increasing subsequence.
ii) find the longest increasing subsequence.
* Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
* Find missing number in 4 billinon 32 bit integers
* Suppose you have N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?
* There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.
* Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.
* Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n); bonus points for a constant time algorithm.
* You have a collection of numbers that's so big that it would not fit onto one single computer. It is therefore scattered across N number of machines, with roughly L number of numbers in each machine, how would you find the median in this entire collection?
* Write some code to find all permutations of the letters in a particular string.
* If you had a million integers how would you sort them efficiently, and how much memory would that consume? (modify a specific sorting algorithm to solve this)
* How do you find out the fifth maximum element in a Binary Search Tree in an efficient manner?
* Given a number, describe an algorithm to find the next number which is prime.