CareerCup

You shouldn't use recursion otherwise the required space won't be O(1). If you implement the same method iteratively it would be O(1) space though.

The question is probably intentionally vague. Here we don't have access to the interviewer here to ask questions so we should make our own assumptions. If the range of the incoming data is small then we can fit all the hash table in memory and the solution is pretty trivial. But if the range is very big (like finding duplicate incoming images in imgur), we need a huge hash table to minimize collisions and we need to also think about how to map the data to a hash key. In this case the hash table might no longer fit in the memory or even in the same machine. Another important question to ask if duplicates happen often or rarely. If the answer is rarely then we can use bloom filters to check very quickly whether the incoming data is not present in our database (bloom filters are 100% accurate when they determine a data is not present in the set, otherwise we have to go to database to check for the answer).

This results in undefined behavior in c++ if v is not an atomic variable (I am assuming that we have two threads here one calling inc and another calling disp). Thread 1 will set v to 1 and then signal s. Thread 2 then can get to line D to print v, but at the same time Thread 1 goes back to line A and tries to increment v. Since we are reading and writing v at the same time, the printed value can be any number (since the read might happen before, after or in the middle of writing).
If v is an atomic variable, then the read and write can happen in any order. So the first printed value can be either 1 or 2, the next will be 2 or 3 and so on.