Amazon Interview Question: it is basic algorithms. The f... | Glassdoor

Interview Question

Software Engineer Intern Interview

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

Interview Answer

1 Answer


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.

Anonymous on Dec 16, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.