## Microsoft Interview Question

Country: India
Interview Type: Phone Interview

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

Counting Sort would fit perfectly here.

Steps:
1) Create an array 'result[]' of size 10. So now, our index will range from 0-9.
2) Simply iterate over the given array of 10000 elements and maintain a count in the result[] array for each element.
3) Once step 2 is complete, iterate over the result[] array and enter the encountered values in the given array.
ex- If res[0] = 78 then enter 78 1s in the given array.
If res[9] = 345 then enter 345 10s into the given array
4) After step 3 we have our sorted array.

The time complexity here would O(n) and space complexity is O(1) as an extra array of 10 elements is used.

Code would be as follows:

``````public int[] sortGivenArrayOf1To10Range(int[] givenArray)
{
if(givenArray==null || givenArray.length==0)
return null;

int[] res = new int[10];

for(int individualElement:givenArray)
{
res[individualElement-1]+=1;
}

int count=0;
int j=0;

for(int i=0;i<res.length;i++)
{
count=res[i];

while(count>0)
{
givenArray[j++]=i+1;
count--;
}

}

return givenArray;
}``````

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

If res[9] = 345 then enter 345 10s into the given array

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

@dhakkad13 absolutely! Thanks for pointing that out! :-)

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

Bucket sort. Set a hashtable of length 10.

Scan the array and increment the numbers in the array when that number is found in the array.Finally, overwrite the array with the information from the hashtable.

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

Count sort!!!

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

Total iterations around the loop twice.
First just get the count of how many times each number is repeated. Save it in array of size ten where the index represents the number(0-10) and the value stores the count. Then refill the array with the corresponding count.
Hope this helps. Done with O(N) Complexity

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

counting sort

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

What if I want to find a program (FAP) first?

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

``````public class CountingSort {
public static void main(String[] args){
int[] arr = {1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,5,1,1,1,1,1,1,2,2,2,3,3,3,9,9,9,9,9,9,9,9,6,7,8,9,0,4,4,4,4,4,4,4,4,4,4,4,4};
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
for(int i=0;i<arr.length;i++) {
if(hm.containsKey(arr[i])) {
hm.put(arr[i], (hm.get(arr[i]))+1);
}else{
hm.put(arr[i], 1);
}
}
for(Map.Entry<Integer, Integer> entry : hm.entrySet()) {
//    System.out.println(entry.getKey() +" - "+ entry.getValue());
int key = entry.getKey();
int value = entry.getValue();
while(value!=0) {
System.out.print(key);
value--;
}
}
}``````

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.