Qualcomm Interview Question
Country: United States
counting +radix sort
answer is 40
First MSB will be sorted using counting or bucket sort (both are stable sorts) total number of buckets will be 10 (decimal base 10) so 10 comparisons. similarly for other digit positions.
Total comparison 4*10 =40
THEY ARE ASKING ABOUT COMPARISONS AND COUNTING SORT IS NOT A COMPARISON SORT ALGORITHM.
we can also use count sort in place of bucket sort, count sort is stable and requires only 7 operations, and applying this we will get 28.
please correct me if i am wrong.
If Radix Sort is used then Maximum no of comparisons is 280. For each number of form ad ad-1 ... ak...a1,a0 we have to compare each digit ak with bucket digit(here 0 to 9) so for each numner 10*4=40 comaprisons are required. For 7 such numbers 7*40=280 comparisons are required
You don't need to compare with each bucket. 1 will go in bucket 1 , 2 will go in bucket 2 .....
Ok. Then have a look at "MCQsnin Computer Science: Fourth Edition
By Timothy J. Williams". This question is there with solution. If there is fault in my logic then please correct.
Well I don't have the book.
Think in this way
My buckets will be link lists in an array say,
buck[10]
when I need to push a digit say i, in its corresponding bucket
the bucket will be buck[i]. What comparison I did?? ith bucket is mapped to ith location.
Radix sort is not a comperasion based sort, it uses counting sort which sort numbers in O(max(n,d)) where d is difference between min and maximum number, here we sort each digit column which contain number from {0,1,2,3,4,5,6,7,8,9} only, we apply same for each column of digits msd to lsd. it will give O(max(n,d)*r), if r is length of each number , here n = 7, d will be 10, r = 4. but remember we are not doing any comparisons here, we just count number of numbers in each buckets only, it require 7 int space, but no comparison.
Ans:280 comparisons in worst case.This case will be of Radix Sort.
- Kumar Baibhav October 16, 20127*4*10=280(7=no. of numbers,4=no. of digits,10=size of decimal(0-9)).