## Amazon Interview Question for Computer Scientists

• 1
of 1 vote

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

good point about considering the practical implementation issues and negative numbers.

Comment hidden because of low score. Click to expand.
0

using a radix sort for each bucket will give you O(n) performance.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a bit trie.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

1. Convert bits to decimal >> to arraylist - o(n)
2. then call sort method

Comment hidden because of low score. Click to expand.
-1
of 1 vote

1. Convert bits to decimal >> to arraylist - o(n)
2. then call sort method

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.