Example and Summary

Example

Let’s suppose that the interviewer asks you to give the best sorting algorithm. Some interviewees immediately answer, “Quick sort! $O(nlog(n))$". Oops, mistake! It would help if you asked many questions before beginning to solve this problem.

Let’s look at these questions one by one.

Question: What kind of data are we using? Is it an integer array?

Answer: Suppose the answer is yes.

Question: How much data are we going to sort?

Answer: There are thousands of elements in the array.

Question: What exactly is the data about?

Answer: The data holds ages of people.

Question: What kind of data structure is used to hold this data?

Answer: ​​Data is stored in a list.

Question: Can we modify the given data structure?

Answer: No, you cannot change it.

We’re all set to use the given information to create a perfect solution. From the first answer, we know the type of data we have. From the second answer, we can conclude that the data size is limited. It’s only in some thousands. From the next answer, we can conclude that it’s age-related data. So we can assume that a person’s age will be between 1 to 150. Lastly, we know that data is in the form of a list and the structure cannot be changed.

To summarize, we can use bucket sort to sort the results. Since the range is only 1-150, we only need an integer list of 150 elements. We don’t have to think about data overflow because the data is in thousands, and we get the solution in linear time.

We’ll discuss different sorting algorithms in the coming chapters.