CareerCup

need some more clarification for void Checkin(long long number) - will it accept already existing number in the pool ??

use a min heap to store the values. so CheckOut() will work in constant time and Checkin() will work in log(N) time.

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

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