Finding duplicates in a stream of numbers

Question

This is an interview question.
Say you have a function foo() which returns some integer.
You need to write an algorithm that does the following:

(1). Call foo() in a loop, till the returned value of foo() is -1.
(2). Returns true if during the loop there were two calls of foo() which returned the same value.

This is what I thought to do, please tell me if this is efficient enough:

(1). Initialize a hash map , which maps an integer to the number of times we got it in the loop
(2). Call foo() in a loop till the returned value of foo() is -1, while updating the hash map accordingly.
(3). Check if there is a key in the hash map which is mapped to a value greater than 1.

Answer 1

There might be other variations, but your answer should be pretty good.

There are two improvements to your algorithm, though.

• Instead of a hashmap that counts the number of times each integer appears, you can just use a hashset to record the appearance of each integer.
• While you are calling foo() in a loop, you will return immediately if you find the returned integer is in the hashset and if you are not required to finish the loop till the returned value of foo() is -1. Many built-in implementations return false when you insert an existing value into a hashset.