-1

I came across this question while going through previous interview questions. Any direction to approach this ?

Find first unique number in an unsorted array of 32 bit numbers without using hash tables or array of counters.

danish sodhi
  • 1,793
  • 4
  • 21
  • 31
  • 2
    can we sort the data? – vishal-wadhwa Oct 22 '17 at 13:15
  • Possible duplicate of [Algorithm to find a number which occurs only once in an array, given all the other numbers occur twice](https://stackoverflow.com/questions/1089987/algorithm-to-find-a-number-which-occurs-only-once-in-an-array-given-all-the-oth) – Thomas Jungblut Oct 22 '17 at 13:21
  • the optimal algorithm is basically just XOR'ing all the numbers together, so the only one that is not duplicated will be the resulting integer. – Thomas Jungblut Oct 22 '17 at 13:22
  • 1
    @ThomasJungblut That doesn't work if there are three copies of a number, or if there is more than one unique number. – interjay Oct 22 '17 at 13:39
  • @interjay yes, that is the assumption. Any even number of duplication would work though. – Thomas Jungblut Oct 22 '17 at 13:48
  • 1
    @ThomasJungblut But that assumption wasn't made in the question. You can't just add assumptions. – interjay Oct 22 '17 at 13:49
  • @interjay I remember that question from previous big company interview pools, that assumption would've come if the interviewee would've asked the appropriate questions afterwards. It's one of the more famous bit twiddling questions. – Thomas Jungblut Oct 22 '17 at 13:51
  • 1
    @ThomasJungblut That's a different question, which happens to be similar but is not identical. The fact that this question asks about the "first unique number" means that there could be more than one. – interjay Oct 22 '17 at 13:56
  • @interjay I assume that if the use of hash table is not allowed, not even a support array is it, right? – Jul10 Oct 22 '17 at 15:29
  • @HJuls2 I don't know, it isn't my question. This is why I don't like questions with artificial restrictions like "do not use X", because you never know what exactly X includes. – interjay Oct 22 '17 at 15:54
  • @crystal I assume that if the use of hash table is not allowed, not even a support array is it, right? – Jul10 Oct 22 '17 at 15:58
  • @interjay Sorry, I was wrong to tag you. – Jul10 Oct 22 '17 at 15:59

2 Answers2

1

Seeing that the input array is unsorted, you can solve the problem by sorting it. This is a bit silly - why give an answer to the question in the question itself? - but the technicalities of the sorting are a little interesting, so maybe this answer isn't trivial after all.

When looking at the array after sorting, you will find several numbers that are not equal to their predecessor and successor; from these, you want to choose the first one in the original array.

To do that efficiently, in your temporary array which is being sorted, for each number, store also the index of that number in the original array. So, at the end, choose the number which is not equal to its predecessor and successor, and which has the lowest index in the original array.

anatolyg
  • 26,506
  • 9
  • 60
  • 134
0

When you have to "do X without using Y", you can sometimes use Z, which has the same effect as Y, and argue that you were not using Y. Or you can disguise Y well enough so no one would recognize using it at first sight.

With that in mind, consider storing repetition counters for all the numbers in a trie. To choose the first number from the set of all unique numbers, store also the indices together with repetition counters.

I can claim that a trie is not an array of repetition counters, because you don't have to allocate and initialize 232 memory cells for the array. This is more like a glorified hashtable, but looks different enough.

anatolyg
  • 26,506
  • 9
  • 60
  • 134