Amazon Interview Question
Computer ScientistsCountry: United States
Interview Type: Written Test
Use a modified bucket sort. Start with the least significant bit of each integer. If it's a 0, put in the 0 bucket, if it's 1, put in the 1 bucket. Then check all the integers in the 0 bucket and move all integers that have no more bits to the sorted portion of the list. Then check all the integers in the 1 bucket and move all integers that have no more bits to the sorted portion of the list. Repeat the bucketing process over all the bits in the integers until all integers have been sorted. This process will read each bit once ( O(n) complexity) and might possibly be done in place (O(1) additional memory)
I think the important obvious point here is that an integer with only 3 bits is smaller than an integer with 4 bits. The question implies that there is some kind of indicator or field for the length of each integer in bits. So if there are a maximum of k bits in an integer, you can split the data into separate arrays depending on the length of the integer, sort each array individually, and then join the arrays back together afterwards, knowing that everything in the array with numbers with x bits comes before the array with x+1 bits. Assuming an even distribution, sorting the array with k bits will take the longest, because it would have about 50% of the numbers. Having k arrays would be overkill, perhaps group the values with less than say k/2 bits together. Question does not indicate if there are negative numbers, or how negative numbers are determined; having negatives would simply imply a mirror image of this solution. This was the easy part. But getting the exact n and O(n) performance connection requires more thinking.
- dave8128 September 15, 2014