Amazon Interview Question 1

10 000 integer numbers in an array, Each number is 10 bit. Sort the array

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.

#include <cstdio>
#include <iostream>

using namespace std;

int main(){
 int cnt[1024],count = 0,tmp;

 freopen("i.txt","r",stdin);

 for(int i = 0; i < 1024; i++){
  cnt[i] = 0;
 }

 /*scan number*/
 while(scanf("%d",&tmp) == 1){
  cnt[tmp]++;
 }

 for(int i = 0; i < 1024; i++){
  while(cnt[i]){
   printf("%d\n",i);
   cnt[i]--;
  }
 }
 return 0;
}