Pergunta de entrevista da empresa Amazon
You have an integer array of length N, containing values in the range 1,2,3…N^2. Sort the array in O(N) time
Respostas da entrevista
Sigiloso
27 de nov. de 2010
We are given N value. So that we can find N^2 value. We can count number of digits in this value.. lets say number of digits is k. Then apply Radix sort for k times. Order of complexity is O(kN) can be written as O(N). search for Radix sort if you dont know.. (ofcourse u do this.)
1