Interview Question

Financial Software Developer Interview

-London, England

Bloomberg L.P.

Design an algorithm to find the first unique element in an array.

Tags:technical, algorithm
AnswerAdd Tags

Interview Answers

8 Answers

2

dear utk O(2n) = O(n) != O(n^2)...

ZT on

1

Its a hashmap. It never guarantees you the order in which you inserted the elements...!!

Ankush on

0

@ankush: this is where LinkedHashMap comes into play.

joe on

1

One possibility that comes in mind: * Walk the array, create a hashmap (key is the value in array, value is the count of such values). * Walk the array again and check the count in the hash map, once you hit 1, you have the first unique value. This is O(n) both space and time.

Anonymous on

0

@ankush: That does not matter, you do not need to keep the order in the hash map. You go again through the original array, so you definitely find the first unique value. The hashmap is just for bookkeeping.

annonymous on

0

@kabajiegara: No, that will not work, consider array "2 1" - if you sort, you'll have "1 2" and would thus return 1, which is the wrong answer because the first unique is 2.

anonymous on

0

An easier one would be to sort the array and since they are asking for the first unique element return the first element that does not appear more than once in the newly sorted array.

kabajiegara on

0

Are you sure that this is O(n), it is definitely O(n^2), you go over all items twice.

utk on

Add Answers or Comments

To comment on this, Sign In or Sign Up.