A sort algorithm question from a job interview

Table of Contents

• Question
• My Answer
• After rethinking the question

1 Question

Here we are, there is an abstract data type(ADT), which has two members - student number and student score, to represent a student, and there are a millions of the students and the score is ranged from 1 to 100 as integer, there is a container to store this ADT, maybe an array. So please tell me one student's position in this exam in the fastest way.

2 My Answer

If you wanna design an algorithm, there are only two points, which you need to focus, space efficiency and time efficiency. They are a perpetual conflict, you can never achieve both space and time efficiency at the same time.

Then after a silent break, yeah, I was thinking this question, I believe I gave the stupid answer, just iterate the whole container. Damn it.

3 After rethinking the question

The interviewer gave me a hint to finding the most time efficient way, Bucket sort. After rethinking this question, I can answer this question in anther view, take the concept of a hash table.

In this case, the ADT have two members: student number and score. then I can build a hash table, the key is student score, so the hash table's length is 101(0-100), the value is the ADT. Case closed.

If I wanna get one student's position, I just use this student's score as the index and account all the ADT before that index in the hash table. So the time efficiency is O(1) to O(n), and the space efficiency is so bad, we need anther space to store a hash table.