0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Efficient enough for what? $\endgroup$ – Juho Oct 30 '18 at 18:14
1
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.