Apple Interview Question
Software Engineer / DevelopersTeam: Sales
Country: United States
Interview Type: Phone Interview
Not very optimized, but it worked:
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
const int N = 10;
int A[N];
vector<int> smaller, bigger;
for (int i = 0; i < N; i++)
A[i] = rand() % 20;
int median = A[0];
for (int i = 1; i < N; i++) {
if(median < A[i]) {
bigger.push_back(A[i]);
push_heap(bigger.begin(), bigger.end(), greater<int>());
}
else {
smaller.push_back(A[i]);
push_heap(smaller.begin(), smaller.end(), less<int>());
}
int d = smaller.size() - bigger.size();
if (d > 0) {
bigger.push_back(median);
push_heap(bigger.begin(), bigger.end(), greater<int>());
median = smaller[0];
pop_heap(smaller.begin(), smaller.end(), less<int>());
smaller.pop_back();
}
else if (d < -1) {
smaller.push_back(median);
push_heap(smaller.begin(), smaller.end(), less<int>());
median = bigger[0];
pop_heap(bigger.begin(), bigger.end(), greater<int>());
bigger.pop_back();
}
cout << "median = " << median << " in ";
vector<int> t(A, A + i + 1);
sort(t.begin(), t.end());
for (int x : t) cout << x << " "; cout << endl;
}
}
In mathematical term, this is an induction. Let Mn be the median computed until now, and a the next number in line. Then it can be demonstrated that Mn+1 = Mn + 1/(n + 1) * (a - Mn). In computer terms, this has the disadvantage that due to the limited precision the result skews away rather quickly. To counteract this effect, we can break n in chunks of a convenient size k, as in n=mk+r. Then the induction's general term becomes Mmk+r=mMk + r/(mk + r) * (M'r + Mmk), where M'r is the median of the last r numbers.
Java Code. Comments are welcome.
import java.util.Random;
import java.util.PriorityQueue;
import java.util.Collections;
import java.util.Arrays;
public class findMedian {
private int[] arr;
private final int SEED = 100;
findMedian(int n) {
arr = new int[3];
}
public void createRandomNumber(int num) {
Random gen = new Random();
for( int i =0; i < num; i++) {
//arr[i] = gen.nextInt(SEED);
}
arr[0] = 1;
arr[1] =1;
arr[1] = 1;
}
public Integer findMedian() {
//Create two heaps
int len = arr.length;
if(arr == null) {
return null;
}
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>((len/2)+1); //Natural Order of Priority Group is Min Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((len/2)+1, Collections.reverseOrder()); //Reverse the order to Change it to Max Heap
maxHeap.offer(arr[0]);
//Starting from 1st index as first element is already inserted into maxHeap
//I did that so that we don't have to check NULL condition in every iteration
for(int i=1; i< arr.length; i++) {
//First Check the size of of each Heap
if(maxHeap.size() == minHeap.size()) {
//Compare the element with the root of the Max Heap
if(maxHeap.peek() > arr[i] || (maxHeap.peek() < arr[i] && minHeap.peek() > arr[i])) {
//Pop the Root element of the Max Heap and Insert it into Min Heap
//minHeap.offer(maxHeap.poll());
maxHeap.offer(arr[i]);
}
else {
maxHeap.offer(minHeap.poll());
minHeap.offer(arr[i]);
}
}
else { //If the size of the two heaps are not equal
//Here we are maintaining the structure where maxHeap size is always greater
if(maxHeap.peek() < arr[i]) {
minHeap.offer(arr[i]);
}
else {
minHeap.offer(maxHeap.poll());
maxHeap.offer(arr[i]);
}
}
}
//if the number of points is even then we are returning the ((n/2)-1)th element
return maxHeap.poll();
}
public void print(){
Arrays.sort(arr);
for(int i=0; i < arr.length; i++) {
System.out.print(i + " " + arr[i] + ",");
}
}
public static void main(String[] args) {
findMedian FM = new findMedian(40);
FM.createRandomNumber(40);
int median = FM.findMedian();
FM.print();
System.out.println();
System.out.println(median);
}
}
def median(lst):
lst.sort()
print(lst)
half = int((len(lst)-1)/2)
print(half)
print(lst[half])
if len(lst)%2==0:
m=(lst[half]+lst[half+1])/2
return m
else:
m=lst[half]
return m
print("median : ")
stream=[9,3,4,2,-1,-7,5,-3]
print(median(stream))
stream=[9,3,4,2,-1,5,-7,5,-3]
print(median(stream))
Maintain two heaps. 1 min heap and other max heap. Add numbers from the stream to these heaps alternatively. The numbers at the root of the heap will be the median.
- Anonymous February 13, 2014