How would you sort 10 million phone numbers?

Question

dreamCoder · Accepted Answer

Radix sort would sort in linear time. Since phone numbers are of fixed length (assuming 10), the complexity would be O(10*10million)

Refer wiki for more info: http://en.wikipedia.org/wiki/Radix_sort

Sigiloso · Answer

asinine.

asksa · Answer

From Programming Pearls using bit vector, #define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F int a [1 + N/BITSPERWOD] void set(i) { a[i>>SHIFT] |= (1>SHIFT] &= ~(1>SHIFT] & (1<<(i&MASK));} int main(void) { int i; for (i = 0 ; i < N ;i++) clr(i); while(scanf("%d", &i) != EOF) set(i); for(i = 0; i < N; i++) if(test(i)) printf("%d ", i) return 0 } Time complexity = O(N) Space = 0(N/BITSPERWORD]

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas