Given an array of unsorted integers, determine which number appears most often.

Question

Original poster · Accepted Answer

The ideal solution, and the one I discussed with the interviewer was:

Make a hash table. Run through the array and for each number, if the location in the hash table is empty, add 1, and if the location is taken, increment the count in that bucket. Once you've run through the entire array, simply determine which bucket has the largest number, and that's your most common number (as well as how many times it appeared).

Sigiloso · Answer

@2nd poster - a collision is the heart of the solution. A collision shows the element exists and hence increments the count

Sigiloso · Answer

I think what the 2nd poster means is, you can have, say 123 and 847 hashed to the same location, then your result would be wrong.

Sigiloso · Answer

Seeing that it's a stream of integers, using a hashtable would be your best bet.
For each x in array:
  if hashtable has x: add 1 to hashtable[x]
  else: hashtable[x] = 1

Sigiloso · Answer

A hash table won't work due to the potential of collisions.

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas