As part of the Codecademy Computer Science career path, I have decided to re-create the example program shown in the Recommendation Software portfolio project, with a few refinements.
To find the types, a Binary Search algorithm is used, achieving a Θ(log n) runtime on average. To make this possible, however, the list is quick-sorted at the start of the program, and quicksort has a Θ(n log n) time complexity. The program relies on checking whether a type begins with a certain character sequence so when the list is sorted in alphabetical order, checking for all types that do start with that sequence is as simple as iterating through the list until a type that doesn't fit the condition is met. In the worst case scenario, the overall algorithm has an O(n log n) complexity.
This algorithm is also modified to return the index where the subset of valid types is found alongside the list of valid types itself. The reason why is explained below.
I used a HashMap implementation to store and access the restaurants for each type. Normally, linked lists would be used to avoid collisions, but it proved necessary to return a linked list itself, since there could be multiple restaurants of the same type. As a result, traditional hashing and collision avoidance methods could not be used. At the start of the program immediately after sorting the type list, the list of restaurants is placed in a utility class and added to the list using the Binary Search algorithm's index return value as an array index. This increases the complexity of initially assigning the values, but since the Binary Search method is already invoked when the user searches a prefix, and the array index is already stored, the program can retrieve the restaurants for a type by simply passing in the type's index in the sorted list to the HashMap.
The Linked List implementation is also modified from Codecademy's example: it ensures that each restaurant list is ordered by the sum of the price rating and overall rating. This is so it is more useful as a recommendation system.
The code is linked here.
Top comments (0)