When it comes to technical interviews, the concept of counting sort is usually presented in one form or another. What makes the question interesting is that a correct answer requires an understanding of dynamic programming. Let's proceed to walk through the logic needed to solve the problem successfully.

Given the following array, produce a list that provides the number of times each selected values has occurred in the series.

let sequence = [0, 1, 3, 1, 2, 4, 3, 2] 

/*
Results: 
0 seen 1 time
1 seen 2 times
3 seen 2 times
4 seen 1 times
2 seen 2 times
*/

What will be your input and output parameters (e.g. function signature) as part of your solution? Will a recursive solution provide increased benefits relative to space or time? Can the question be solved using an in-place design? Why or why not?

Storing Previously Seen Values

When solving questions, optimization comes from how one frames the question. In many cases, the best solutions assume the data is scanned once before concluding. This approach impacts our code implementation as it eliminates the need for recursion or other techniques that require a time complexity of O(n ^ 2) or greater:

 
 

The Dynamic Approach

An optimized approach would be to store (and analyze) previously seen values as we iterate through our sequence list. To do this, we'll use a secondary, empty array. The array's length will equal the topmost value from our sequence list (e.g 4).

 
 

With our structure in place, the next step involves counting the value occurrence as seen from our sequence list. To do this, we'll use the array value index to represent the values seen and the array's value to store the count of each occurrence:

 
 

Although the algorithm is technically known as counting sort, most classic sorting algorithms take a series of unsorted values and apply the type of algorithm to create a sorted result. Many times, these solutions require nested comparisons that result in an O(n ^ 2) time complexity. Using a dynamic approach, we've modeled our solution to apply a hash table-like structure that improves the speed at which data is stored and analyzed.

Other Study Lists

Thanks for reading! If you haven’t already, be sure to also review my other lists and resources as they relate to computer science and Swift / iOS development.