Amazon Interview Question

1

Design an API such that it can give unique Integers on every call. These itegers must be the smallest one possible. Users can also submit these integers back to the api such that these can now be allocated to other users.
Ex:
Input:
Request
Request
Request
Request
Delete 3
Delete 4
Request
Request
Request

Output:
1
2
3
4
Delete Successful
Delete Successful
3
4
5

Requests and deletes can be in billion , suggest most optimal approach.

Follow up:
What if the deletes are in some hundreds only?

1 Like
2

We can maintain a set of elements (initially containing only 1) and then if a request comes we simply remove the element from the front of the set and return it. If the size of set was one we will insert a new element 1 greater then the element returned.
If a delete request come we will simply insert that element in the set.

3

Use priority queue or minHeap