## Akamai Interview Question for Java Developers

• 1
of 1 vote

Country: United States

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

instead of sorted array, use a heap.

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

to clarify, it should be min heap of size 1000.

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

heap is the right choice.

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

why a min heap if you want max elements and why is the size 1000 if only 100 elements are needed

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

also adding a new number to heap may knock off a number which is not minimum in heap

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

You can use an array and a heap at the same time! Use the array implementation of the heap.

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

Let's say it is not 100 , it is 5 .
And my current heap is { 27,13,5,10,8}

and new number that comes is 9. How do you find , eliminate 5 and restructure the heap. ??

Won't it be good to just keep circular list/queue, so that i know the range [ min, max] of my current top 100 elements. if number scanned is out of that range, we ignore and if number is in that range we insert it in it's correct place.

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

actually you should use a min heap of 100, if the next number is more that root of heap swap it with root and heapify.

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

simply store initial 100 elements in sorted order then if next number is greater then 100th number then simply delete 100 th number and add tht element(at appropriate position) .. keep doing till last .. :)

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

yeah but in implementing the same we can maintain a heap to know the largest value in the current list of 100 numbers.

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

Wait, you will have to sort the incoming stream until you get the first 100 numbers. Then if the next number is greater than any of the prev, you have to push down the set by 1, so in this worst case, you will have to do this about 100 times N. Wouldn't a binary heap will allow the insert option in big-O log base 2 of 100 times N? So be faster.

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

randomly select k elements as an observe sample set. K should be neither too large nor too small.

observe k. Since the element is integer. select a digit number as threshold to reduce the list size. let's say, after observing, we pick 5 as digit number. then we scan the whole list, and just load the element which is equal or larger than 10000 in to memory.

redix sort picked elements in memory.

average complexity should be n. It does not work in some special cases.

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

Use PriorityQueues:MinPQ
1. Insert Item
2. If size of PQueue is > 100, remove minimum.
Complexity (O(NlgN))

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.