## Ebay Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

Counting sort

``````public static void countingSort(int [] m)
{
int [] counts=new int[10];
for(int i=0;i<counts.length;i++)
counts[i]=0;
for(int i=0;i<m.length;i++)
{
counts[m[i]]++;
}
int counter=0;
for(int i=0;i<counts.length;i++)
{
for(int j=0;j<counts[i];j++)
{
m[counter]=i;
counter++;
}
}
}``````

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

This is having O(n2) time complexity

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

I dont think so.counts.length is a constant- the question states that only single digit numbers are present in the list (0-9). So that keeps the complexity at O(n).

You do not have 'n' numbers with each number having 'n' as its frequency. That would be O(n^2).
Please correct me in case I have messed up.

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

Great, this is even simpler than the algorithm given in CLRS!

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

use bucket sort.

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

Create BST and then inorder traversal

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

method 1: use an array of arr[10] for ten 1digit numbers.
increment count of digit in array.
print the digit no of times specified in the array

unsorted list 6 1 4 1

arr 0 1 2 3 4 5 6 7 8 9
val 0 2 1 0 1 0 1 0 0 0

sorted list: 1 1 4 6

method 2:
use radix sort if array can fit in memory

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

Shouldn't second last for loop be -

``for(int i=0;i<10;i++)``

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.