Interview Question for Software Engineer at Google:

>>You have a data structure of integers, which can be negative, zero, or positive, and you need to support an API with two public methods, insert(int) and getmedian(). Describe a data structure you would use to support this API and describe the running time of the two methods.
-----------------------------

You have several choice here, with differing running times for insert and getmedian. You could use an unsorted list, implemented as an array. With an unsorted list, insert would run in constant time and getmedian would run in O(n). You could use a sorted list, implemented as an array. Finding the location to insert would run in O(log n), actual insertion is O(n) in the worst case since all elements might need to be shifted over, and getmedian could run in constant time since you could keep a sentinel variable to track the center. Lastly, you could use a self-balancing binary search tree, such as a red-black tree. With self-balancing binary search trees, insertion would run in O(log n) time and getmedian would run in constant time since the root is always the median.

-------

(Is that correct? Did I leave out any major structures?)

>>Imagine you're writing a function that takes an array of integers and an integer and it needs to return true if any pair in the array sum to the 2nd argument. The array can have negative numbers, zero, or positive numbers. Describe how you would design this function and what its running time would be

---------------------------------
For O(n^2), I'd use a nested for loop that summed a[i] with a[j] whenever i != j.

For O(n log n), I would first sort the list with mergesort (O(n log n)), then compare the sum of a[0] with a[n-1]. If it is less than the target, compare a[0] plus a[n-2]. If it is greater than the target, compare a[1] plus a[n-1]. In the worst case, you'd perform n/2 comparisons.

For O(n), create an empty bit array of size abs(2*target)+1. Walk through the list. Check bit[(target - a[i])]. If set, return. If not set, set bit[a(i)]. The idea is that as you walk through the list, you check if the required "partner" of each element is set, where a[i] + partner of a[i] = target. If the partner's bit is set, we know that there is a pair that sums to the target.

The answer to the median question is to actually use two heaps, a min heap and a max heap. Google for "median heap"

Nice solutions. I now remember there was a follow-up to the median question:

* Suppose you know the numbers will all be between 0 and 200, though there can still be duplicates. Can you change your solution using this information?

@ellemeno

your O(n) solution for the second question won't work if there is a hung negative num say -100*target and a huge positive num 101*target, they sum to target, but your bitmap won't able to hold them.

For O(n), create an empty bit array of size abs(2*target)+1. Walk through the list. Check bit[(target - a[i])]. If set, return. If not set, set bit[a(i)]. The idea is that as you walk through the list, you check if the required "partner" of each element is set, where a[i] + partner of a[i] = target. If the partner's bit is set, we know that there is a pair that sums to the target.

@ellemeno

For the first question, you can't simply pick off the root of a balanced tree. (I'll let you figure why.)

For the second question, a simple O(n) solution would be to utilize hashmap from the value to # of occurrences. Then go through the list again, for each number k, check whether sum - k is in hashtable. This is just a rough framework, you need to be careful of duplicate answers and things like sum/2 + sum/2 = sum (does sum/2 occurs once or twice).