Given an array having integers with just one integer repeated thrice, how will you find out which integer is that?

Question

Sigiloso · Accepted Answer

1) You can sort it (O(n*log(n))) and find first repeating number (O(n)). But this is too obvious of a solution.

2) You can use a hash table of size O(n) to store number of occurrences. This is O(n) solution, but requires additional O(n) memory.

3) There must be a trick here, but I can't seem to find it. XOR is useless, and everything else is slower than or equal to O(n*log(n)).

dopey · Answer

@InterviewCandidate: are you sure the other elements aren't repeated twice and only one element isn't repeated thrice? Amazon likes asking a question of this form: 

""Assume you have an array of numbers where each number is repeated an even number of times and only one is repeated an odd number of times. How would you find that number?""

This is a clear cut case of XOR and by the looks of the question, I think that's what the interviewers were going for.

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas