Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
No , its basically you have a pool of number from 0 to long long and every time you do a checkout you get the next min number now once you are done with the number you can check it back in by checkin() function . Think of these numbers like some kind of token system
Well challenge here is numbers are from 0 to long long . What will be the size of your minheap for this ? Do you think you can hold it on ram ?
I think we can also use the concept of Sorted doubly linked list. Whenever a new number will come, we can search its location in LogN time and update the linked list and also return the next smallest number In O(1) time.
Keep a static counter which increments from 0.
However, every time someone gives back a number (i.e. Checkin ), add that number to a min heap.
Whenever someone checks out,
a ) check if the min heap has anything to pop if so, return that
b) otherwise, return +1 to the static counter
Farid, your solution is correct except that in order to avoid the heap growing forever on checkin you also want to compare the number being checked in against the counter. This way you can decrement the counter and avoid extra space on the heap. Furthermore, you can free more space by re evaluating the heap after a decrement.
Here is one possible solution.
Given:
- NumberPool has numbers from 0 to ...
- checkOut() next smallest available number
- checkIn(long number) adds the number to the pool
Brainstorm:
- Will contain a large number of elements
- data structure needs to dynamic in nature
- Min() should possibly be O(1)
- Insert() should be fast was well
- Delete-Min() should be as fast as possible
- Space O(n)
- Possible data structure is dynamically increasing min-heap():
- O(logn) extract min
- O(logn) insert
- O(1) find min
** Fibonacci heap is more complicated, but could possibly give O(1) insertion and O(logn) amortized extract min
class NumberPool {
private long [] heap;
private int size;
private int leaf;
private int root;
public NumberPool(int size) {
this.heap = new int[size];
this.size = size;
this.root = 0;
this.leaf = 0;
}
public long checkout() throws Exception {
return extractMin();
}
public void checkin(long number) {
insert(number);
}
private long extractMin() throws Exception {
long min = this.heap[root];
this.heap[root] = this.heap[leaf];
leaf--;
int i = root;
while(i > root) {
int minChild = getMin(2 * i + 1, 2 * i + 2);
if(minChild > 0) {
if(this.heap[i] > this.heap[minChild]) {
long temp = this.heap[i];
this.heap[i] = this.heap[minChild];
this.heap[minChild] = temp;
}
}
i = minChild;
}
return min;
}
int getMin(int a, int b) throws Exception {
if(a <= leaf && b <= leaf) {
if(this.heap[a] < this.heap[b])
return a;
else
return b;
}
else if(a <= leaf)
return this.heap[a];
else if(b <= leaf)
return this.heap[b];
else
return -1;
}
private void insert(long number) {
if(leaf == size - 1)
resizeHeap();
this.heap[++leaf] = number;
heapify();
}
private void heapify() {
int i = leaf;
while(i > root) {
int parent = (i - 1)/2;
if(this.heap[parent] > this.heap[i]) {
long temp = this.heap[i];
this.heap[i] = this.heap[parent];
this.heap[parent] = temp;
i = parent;
}
else
break;
}
}
private void resizeHeap() {
//Resize heap to 2 times its size
}
}
This is solvable using Min Heap but in the heap maintain only the allocated numbers only . checkout should neturn Min(Heap)-1 and insert it in the Min Heap and hence o(1) time to insert as we know we are inserting a number smaller than all. Chekin(n) should actually delete n from the Min Heap and hence takes Log(n) time to heapify back after deletion
This is solvable using Min Heap but in the heap maintain only the allocated numbers only . checkout should neturn Min(Heap)-1 and insert it in the Min Heap and hence o(1) time to insert as we know we are inserting a number smaller than all. Chekin(n) should actually delete n from the Min Heap and hence takes Log(n) time to heapify back after deletion
Actually you can use ArrayList implementation in Java to implement a minHeap, with use of arraylist you can keep part of the list in the main memory and part of it on the secondary list ,
other wise , if you like to implement the data structure by yourself (not using implemented datastructure) , you can implement an arraylist by using an array of arrays , which acts like a dynamic array
need some more clarification for void Checkin(long long number) - will it accept already existing number in the pool ??
- Vin June 03, 2013use a min heap to store the values. so CheckOut() will work in constant time and Checkin() will work in log(N) time.