Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
Amazing answer, just amazing. I could not come up with that, I lost my job probably on it.
This is a classic and very well-known approach. This is an important sorting algorithm to know. Still, I wouldn't count you out just because you didn't know this one thing with this one interviewer. Were you able to solve the problem using a different technique?
Just a small correction - we will need 1023 elements in the array instead of 1024. So, given that and the counting sort algo, you can easily solve it in O(N) time.
I knew the sorting algorithm u mentioned, I did not focus on 10 bit, and went to wrong direction.
Small optimization on counting sort: Use array of bits (e.g. bitset<> in C++). When parsing through the list, just set the corresponding bits. This will save the memory too.
Yes, counting sort is powerful if the range is known. In just one parse, you get the result.
@Victor: bitset won't work. You actually need the count of each element.
@ashot madatyan: why 1023? You want to have a special case for the 1024th one where we don't count it and fill up any space left at the end with it? It would use less than 0.1% less space but add implementation complexity.
I agree, in this particular case, count is needed and hence small optimization in the space should be that each array element for counting sort is max 2 bytes to accommodate max count of 10000.
There is a problem if repetitions are allowed. In that case, array of linkedlist needs to be created...
Complexity of Radix sort is higher than Counting sort. If you are aware of any optimization to make Radix sort faster, please share.
int[] input = new int[10000];
Random random = new Random();
for (int i=0;i<1000;i++){
input[i]=random.Next(0, 1024);
}
Sorting.CountingSort(input);
public static void CountingSort(int[] arrayA)
{
Console.WriteLine("Original Array");
for (int i = 0; i < arrayA.Length; i++)
{
Console.Write(arrayA[i] + " , ");
}
Console.WriteLine("");
int k = 1024;
int[] arrayB = new int[arrayA.Length];
int[] arrayC = new int[k];
for (int i = 0; i < arrayC.Length; i++)
{
arrayC[i] = 0;
}
for (int j = 0; j < arrayA.Length; j++)
{
arrayC[arrayA[j]] = arrayC[arrayA[j]] + 1;
}
//Place the number of elements less than each value at i into array C.
for (int i = 1; i < k; i++)
arrayC[i] = arrayC[i] + arrayC[i - 1];
//Place each element of arrayA into its correct sorted position in the
//output array B.
for (int j = arrayA.Length - 1; j >= 0; j--)
{
arrayB[arrayC[arrayA[j]] - 1] = arrayA[j];
arrayC[arrayA[j]] = arrayC[arrayA[j]] - 1;
}
//Overwrite the original arrayA with the output arrayB.
Console.WriteLine("Sorted Array");
for (int i = 0; i < arrayA.Length; i++)
{
arrayA[i] = arrayB[i];
Console.Write(arrayA[i] + " , ");
}
Console.WriteLine("");
}
10 bit means there's only 2^10 = 1024 possible values. Use counting sort. Create an array of 1024 integers and in the i-th index keep the number of occurrences of the i-th possibility. IN the end, just traverse your occurrence count array printing each element the number of times that it occurs.
- eugene.yarovoi June 21, 2012