AQR Capital Management Interview Question
You are given an integer array n. Complete the function sortIntegers which takes as argument, an integer array n of up to 1 million integers such that 1 <= n_i <= 10 for every element n_i in the array, and returns the sorted array. The sort does not need to occur in-place. Please do not call a standard sorting function like quicksort, you can do better. A sample input is {3, 1, 4, 1, 5, 9, 2, 6, 5} and the corresponding output is {1, 1, 2, 3, 4, 5, 5, 6, 9}. Constraints: i <= 10^9; 1 <= n_i <= 10
Interview Answer
Anonymous
Jul 26, 2017
As we already know the sorting order of the numbers from 1-9. Parse through the array once and keep count of each integer.you will pass through array once.With the counts, you have generate the array. This will take O(n) and 2n space.