## Qualcomm Interview Question

• 0

Country: United States

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

Ans:280 comparisons in worst case.This case will be of Radix Sort.
7*4*10=280(7=no. of numbers,4=no. of digits,10=size of decimal(0-9)).

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

Didn't get the exact question here.
Are the 4 digits of each number not taken as number on a whole?
Is digit by digit comparison required?

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

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

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

THEY ARE ASKING ABOUT COMPARISONS AND COUNTING SORT IS NOT A COMPARISON SORT ALGORITHM.

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

I don't think they are asking answer for comparison sort. Option doesn't make sense in that case. Even worst of comparison sorts in worst of cases will give less number of comparison than the given option

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

merge sort....
only 21 comparisons

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

Wrong! Merge sort needs even less number of comparisons.
It needs n ⌈lg n⌉ - 2^⌈lg n⌉ + 1 in worst case.
Which is 14 here.

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

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.

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

Number of buckets will be 10.

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

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

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

You don't need to compare with each bucket. 1 will go in bucket 1 , 2 will go in bucket 2 .....

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

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.

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

radix sort is not a comparison sort mind you!!!!

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

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.

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

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.

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

QUESTION IS CLOSED

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

plz give an explanation to this!!

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

I think, comparisions will depend upon sorting method, and also if you are comparising each digit or whole number.

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

If the focus is only on comparisons then we can also prefer Radix sort in which comparisons are close to zero but the number of copies needed for seven 4 digit numbers would actually be 2*N*K (K being the number of digits) so here copies would be 56

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

I don't understand this question. Can anyone please elaborate this question?

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

I guess for Radix sort complexity:
O(#digits*(#elements+base of each digit)) = O(d(n+b))

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

We need to sort the numbers into the buckets based on every digit from LSB to MSB. So, we get (7*10*4=280) -> 7 numbers, 4 digits/no, 10 buckets (0-9)

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

nlogn where n=7.

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

for quick sort it will take 20 comaprisons(6*5*4*3*2) and for each comparison -> as there is 4 digit number 14 bits is required to compare so for each number comparison 14 bit comparison and hence 20*14=280

Comment hidden because of low score. Click to expand.

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.