CareerCup

We need to track numbers that are distinct, so need to go with Set. We need to check if the next number already exists in the Set and if it does then we need to remove it, so need to have a quick lookup - Hash. Insertion order is important so need to be Linked. So, use LinkedHashSet - add numbers as they arrive but check if it exists already. If it exists then rather than additing to the Set, remove it from the Set. So, O(n) time and O(n) space.

There are 3 operations - check-in (could be any nth element), check-out, get least check in number. If we use BitSet (arraylist that stores everything in bits), the time complexity to set/get bit at nth location would be constant O(1), since it uses array under-neath and random-access search from array is O(1). So, check-in and check-out could be done by saying bitset.set(n) or bitset.get(n) in O(1). To get the least check-in number - we can do 2 things : sequential search O(n) (based on the application - if lets say least numbers are most likely to be checked-in first thereby hoping to achieve O(1) in most cases) - goal here is that we are mostly expecting the best case scenario. The second thing could be to do binary search O(log n) - worst case to find the least checked-in number.

In terms of space complexity, with Bitset we can store 8 bits in 1 byte. That's like achieving log n with base 8. Which is pretty good.