## Apple Interview Question for Software Engineer / Developers

Team: Sales
Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Need a little but important information: you got to make two heaps balanced (i.e. differ by at most 1 element).

Comment hidden because of low score. Click to expand.
0
of 0 vote

Linear space is trivial.

Sub-linear is topic of research questions. What was the interviewer guiding you towards?

Comment hidden because of low score. Click to expand.
0
of 0 vote

geeksforgeeksdotorg slash median-of-stream-of-integers-running-integers

a good explanation

Comment hidden because of low score. Click to expand.
0
of 0 vote

Check out Wikipedia for the median-of-medians algorithm. It provides an answer to your question in O(n) time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

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;
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;
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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorted binary tree stored as array, median item will be array[fill-size/2] for odd number of items, (array[fill-size/2] + array[fill-size/2 - 1])/2

But space can become an issue.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;

}

public void createRandomNumber(int num) {
Random gen = new Random();
for( int i =0; i < num; i++) {
//arr[i] = gen.nextInt(SEED);
}
arr = 1;
arr =1;
arr = 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);

//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);

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

why not use std::list?
list.push_back();
list.sort(),
and then use iterator to pick the medium -> advance(iterator, list.size()/2-1);

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a balances BST, just return the root, which is the median at any moment.

Comment hidden because of low score. Click to expand.
0
of 0 vote

If unique numbers are limited, we can use a map of numbers and count the occurence of each number in the stream. Based on even or odd numbers received so far, we can liniarly calculate median.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.