## Amazon Interview Question for SDE1s

Country: United States

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

We can use a maxheap. The root of the maxheap is the minimum number. When checkout, we get the root. When checkin, we insert the number. GetRoot and Insert both take O(logn).

``````MaxHeap heap( LONG_MAX );
long CheckOut( MaxHeap heap )  return heap.GetRoot();
void CheckIn( MaxHeap heap, long input )  heap.Insert( intput );``````

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

one point on your implementation, the question says "checkout should return the minimum available LONG number" and in your implementation you are returning MAX number...

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

Thanks, I thought it requires to return maximum. Use a max heap instead could return minimum.

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

Simple solution, use 2 TreeSets (sorted sets) one for the "checked out" elements and one for "checked back in" elements. Then:

- To insert: Check the max in "checked out" set and see if there if the min number in "checked back in set" < max , if yes return that. If not, just check in max+1.
This will be O(log(n)) in the worst case

- To checkin - Just insert the element in "checked back in" set.
This will also be O(log(n)) in the worst case.

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

We could use heap for this, though I am concerned about the maximum size of heap in worst case. Here is some code (which assume a heap data structure exists). You can use priority queue in Java to implement this.

If we use checkin and checkout operations alternatively, then heap size will be zero. In worst case when we check out 1..N and then start checking in numbers < N then heap size can reach upto N-1

``````private long value = 1;
private Heap h = new Heap();

public long checkout() {
// We want the next number in the sequence
if(h.size() == 0) {
this.value++;
return value - 1;
} else {
// return the minimum value from heap
return h.removeRoot();
}
}

public void checkin(long val) {
// Checkin the previous number that was checkedout
if(val == this.value - 1) {
this.value--;
} else {
// insert into heap as its not in the sequence
}
}``````

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.