## Amazon Interview Question Software Engineer / Developers

• 0

How to find the median from a randomly generated 1 billion integers?
Hint: To think of using specific data structure or approach so that the entire integer need not be sorted (to identity integer such that half the integers fall to the left and other half fall to the right of it)

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

median of medians recursively?

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

smart choice

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

selection algorithm?

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

It can be done by modifying the partition algo of quicksort...

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

it should be an external sort

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

it should be an AVL tree,then root is always the median.

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

Select Algorithm...no need to sort the array..linear time

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

Modify quick sort and partition until you reach the middle:
1. int index = Partition (A[1,N], billion / 2);
2. if index < billion/2 => Partition(A[index + 1, N, billion / 2 - index);
3. if index > billion/2 => Partition(A[0, N, index - billion/2);
4. if index == billion / 2 => Find index1 in A[index+1, N] such that index1 is min
5. Return (index + index1) / 2;

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

Use two heaps. I am assuming that you have two classes available (minheap and maxheap) and they each have a size method.

``````public double findMedian(final int[] numbers) {
MinHeap min = new MinHeap(numbers.length);
MaxHeap max = new MaxHeap();
for (int i = 0; i < number.length; i++) {
min.push(numbers[i]);
}
//now even out the sizes as close as possible
if (min.size() % 2 == 0) {
while (min.size() > max.size()) {
max.push(min.pop());
}
return ((min.pop() + max.pop()) / 2);
} else {
while (min.size() > max.size()+1) {
max.push(min.pop());
}
return min.pop();
}
}``````

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

@ above,
Do you know the meaning of median? Median is not mean. What is the meaning of this statement
"return ((min.pop() + max.pop()) / 2)" ---> don't try to return the average.

Don't just copy the code from any book and paste it here..

Name:

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

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### 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.