CareerCup

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

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.

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
            h.add(val);
        }
    }