Pregunta de entrevista de Amazon
it is basic algorithms. The first is a sort algorithm. There is an array with a million integer. The integer's length is 10 bit. Find an algorithm with run complexity of N. The second is about detect if there is any circle in a linkelist
Respuesta de la entrevista
Anónimo
16 de dic de 2015
All integers are 10 bits in length, so there can only be values from 0 to 1023 in the million integer array. Create a hash table array of 1023 indexes, the starting value at each index is 0. For each number in the million integer array, increment the value at same index position in the hash table. You now have a compressed representation of the sorted million integer array. Simply overwrite the million integer array with the new values deduced from the compressed version.