## 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)).