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.

- Anonymous February 13, 2014 | Flag Reply
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).

- zahidbuet106 June 02, 2014 | Flag
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?

- Anonymous February 13, 2014 | Flag Reply
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

- blackfever February 13, 2014 | Flag Reply
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.

- Killedsteel February 13, 2014 | Flag Reply
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[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;
    }
}

- Westlake February 13, 2014 | Flag Reply
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.

- Dave February 14, 2014 | Flag Reply
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.

- Florian February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

    }
}

- RG April 08, 2014 | Flag Reply
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);

- outbacker August 28, 2014 | Flag Reply
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))

- simone.mapelli August 21, 2015 | Flag Reply
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.

- Saravana coumar June 22, 2016 | Flag Reply
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.

- dhruven91 November 14, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More