Qualcomm Interview Question


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

- Kumar Baibhav October 16, 2012 | Flag Reply
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?

- Learner July 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- words&lyrics July 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SANDEEP July 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- words&lyrics July 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

merge sort....
only 21 comparisons

- Arpit Gupta July 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Aashish July 29, 2012 | Flag
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.

- Anonymous July 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Number of buckets will be 10.

- words&lyrics July 29, 2012 | Flag
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

- manish.patel.mnnit July 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- words&lyrics July 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- manish.patel.mnnit July 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anonymous July 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- words&lyrics July 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

QUESTION IS CLOSED

- Shobhit July 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

plz give an explanation to this!!

- ANURAG August 03, 2012 | Flag Reply
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.

- rahul.deshmukhpatil August 04, 2012 | Flag Reply
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

- sudarsan.dabburi August 31, 2012 | Flag Reply
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?

- susan August 31, 2012 | Flag Reply
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))

- Sree September 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

the answer is 280
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)

- Anonymous October 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

nlogn where n=7.

- Manish December 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ankur Jain May 15, 2013 | Flag
Comment hidden because of low score. Click to expand.


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