Amazon Interview Question for Computer Scientists


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.

- dave8128 September 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kr.neerav September 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kr.neerav September 15, 2014 | Flag
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)

- zortlord September 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a bit trie.

- sujoyg June 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Youngsam September 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Youngsam September 15, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More