Sort Features by Popularity

Sort Features by Popularity

What is this problem about?

"Sort Features by Popularity" is a string processing and ranking problem often presented in a real-world context. You are given a list of feature names and a list of user responses (sentences). A feature's popularity is defined by the number of unique responses in which it appears.

Your task is to sort the features based on their popularity in descending order. If two features have the same popularity, they should maintain their original relative order from the input feature list (a stable sort). This problem requires careful counting and efficient string searching.

Why is this asked in interviews?

Amazon frequently uses this coding problem because it mirrors actual tasks engineers face, such as analyzing customer feedback or logs. It tests your ability to use Hash Tables for frequency counting and your understanding of string matching (splitting sentences into words). It also checks if you can implement a stable sort, which is a common requirement in ranking systems where ties must be broken consistently.

Algorithmic pattern used

The pattern involves frequency counting and custom sorting:

1. Use a Hash Table (Map) to store the popularity of each feature, initialized to 0.
2. Process each response:
   • Convert the response into a set of unique words (to ensure we only count a feature once per response).
   • Check which features from the set are in our feature list and increment their count in the map.
3. Sort the feature list using a custom comparator:
   • Compare by popularity (descending).
   • If counts are equal, preserve the original order.

Example explanation

Features: ["storage", "battery", "hover"] Responses: ["Battery is good", "I want more storage", "Battery and storage"]

1. Response 1: ["battery"]. Counts: {battery: 1, storage: 0, hover: 0}
2. Response 2: ["storage"]. Counts: {battery: 1, storage: 1, hover: 0}
3. Response 3: ["battery", "storage"]. Counts: {battery: 2, storage: 2, hover: 0}
4. Sorting: battery (2), storage (2), hover (0). Since battery came before storage in the original list, the result is ["battery", "storage", "hover"].

Common mistakes candidates make

A common error is counting a feature multiple times if it appears twice in the same response (e.g., "Battery is better than the old battery"). The problem usually specifies unique responses. Another mistake is inefficient string matching—searching for each feature in every response string can be slow. Splitting responses into sets of words is much faster. Finally, using an unstable sorting algorithm can lead to incorrect results when popularity counts are tied.

Interview preparation tip

When tackling the "Sort Features by Popularity interview question," focus on preprocessing. Mention that you would convert all words to lowercase if the problem is case-insensitive. Also, discuss the time complexity: $O(R \times W + F \log F)$ where $R$ is responses, $W$ is words per response, and $F$ is features. This shows you are thinking about how the solution scales with large feedback datasets.