Sort Features by Popularity

Medium

Asked by:

11 views

Topics:

ArraysStrings

You are given an array of strings features where each string is a single word. You are also given an array responses, where each response[i] is a string that consists of space-separated words.

You need to sort the features array in descending order based on their popularity. The popularity of a feature is the number of responses that contain the feature. If two features have the same popularity, order them in ascending lexicographical order.

Return the sorted array of features.

Example 1:

Input: features = ["cool","new","awesome"], responses = ["cool product","awesome word","new idea"]
Output: ["cool","awesome","new"]
Explanation: The feature "cool" appears once in the responses, "new" appears once, and "awesome" appears once. Since they all have the same popularity, order them in ascending lexicographical order.

Example 2:

Input: features = ["practical","solution","algorithm"], responses = ["efficient solution","solution","obvious solution"]
Output: ["solution","practical","algorithm"]
Explanation: The feature "solution" appears three times in the responses, "practical" appears once, and "algorithm" appears zero times. Sort by popularity and break ties in lexicographical order.

Constraints:

1 <= features.length <= 100
1 <= features[i].length <= 100
features[i] consists of lowercase English letters.
All the strings in features are unique.
1 <= responses.length <= 100
1 <= responses[i].length <= 100
responses[i] consists of lowercase English letters and spaces.
responses[i] does not have leading or trailing spaces.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What data types are the features and feature requests? Are they strings, and can they be null or empty?
How is 'popularity' defined? Specifically, if two features have the same number of requests, what is the expected order?
What should be returned if the list of feature requests is empty, or if none of the feature requests match any feature?
Are the feature requests case-sensitive with respect to the provided features?
What is the size limit of the features and featureRequests arrays?

Brute Force Solution

Approach

The brute force approach involves checking every single possible way to count how many times each feature is mentioned. We go through each review and look for each feature individually to see if it's there. This ensures we don't miss any mentions, but it can take a long time.

Here's how the algorithm would work step-by-step:

Take the first feature from the list of features.
Go through each review, one by one.
For the current feature, check if it's mentioned in the current review.
If the feature is mentioned, increase its count by one.
Move to the next review and repeat the checking process until all reviews are checked for that feature.
Move to the next feature in the list of features.
Repeat the process of checking all the reviews for the new feature and counting its mentions.
Keep doing this until we have counted the mentions for every single feature in the list.
Once we have the counts for all features, we can sort the features from the most frequently mentioned to the least.

Code Implementation

def sort_features_by_popularity_brute_force(features, reviews):
    feature_counts = {}

    for feature in features:
        feature_counts[feature] = 0

    # Iterate through each feature.
    for feature in features:

        # Iterate through each review to count feature mentions.
        for review in reviews:
            if feature in review:

                # Increment count when feature is found.
                feature_counts[feature] += 1

    # Sort features by counts in descending order.
    sorted_features = sorted(feature_counts.items(), key=lambda item: item[1], reverse=True)

    # Extract the feature names from the sorted list.
    sorted_feature_list = [feature for feature, count in sorted_features]

    return sorted_feature_list

Big(O) Analysis

Time Complexity

O(m*n*k) – The brute force approach iterates through each of the m features. For each feature, it iterates through each of the n reviews. Within each review, we perform a check to see if the feature exists, which takes k time, where k is the length of the review string in worst case or the length of the feature in best case. Thus, the time complexity is O(m*n*k).

Space Complexity

O(1) – The algorithm iterates through features and reviews, counting mentions, but it doesn't create any auxiliary data structures whose size depends on the number of features or reviews. It primarily uses a counter variable to keep track of mentions for each feature which takes constant space. Therefore, the space complexity is constant, independent of the input size. No additional lists, maps, or significant data structures are allocated.

Optimal Solution

Approach

To efficiently sort features based on popularity from provided customer reviews, we'll first count how many times each feature is mentioned. Then, we'll use this count to arrange the features in the order of most to least popular, while also respecting any initial ordering constraints.

Here's how the algorithm would work step-by-step:

First, create a system to track how many times each feature appears in the list of customer reviews. For each review, check if it mentions any of the features.
For each feature, record the number of reviews that mention it. This tells you how popular each feature is based on the reviews.
Now, organize the features from most popular to least popular based on their mention counts. The feature mentioned the most should be at the top.
Also, maintain any pre-existing order of features if it exists and if any features have equal popularity counts.
Finally, produce a list of the features sorted by popularity, with the most popular features appearing first.

Code Implementation

def sort_features_by_popularity(number_of_features, feature_list, number_of_reviews, reviews):
    feature_counts = {feature: 0 for feature in feature_list}

    for review in reviews:
        review_lower = review.lower()
        for feature in feature_list:
            feature_lower = feature.lower()

            # Count feature mentions. Case-insensitive search.
            if feature_lower in review_lower:
                feature_counts[feature] += 1

    # Sort features by popularity, then by original order.
    sorted_features = sorted(
        feature_list,
        key=lambda feature: (-feature_counts[feature], feature_list.index(feature))
    )

    # Return the sorted list of features.
    return sorted_features

Big(O) Analysis

Time Complexity

O(R*F*L + FlogF) – Let R be the number of reviews, F be the number of features, and L be the average length of a review. The first step iterates through each review (R) and checks if each feature (F) is present within the review (L), resulting in O(R*F*L). Sorting the features based on their counts takes O(FlogF) time, where F is the number of features. Since O(R*F*L) typically dominates O(FlogF), the overall time complexity is O(R*F*L + FlogF).

Space Complexity

O(F) – The algorithm uses a hash map (or dictionary) to store the counts of each feature's mentions. The size of this hash map is directly proportional to the number of unique features, which we denote as F. In the worst case, each feature in the provided features list is unique and stored in the hash map, contributing to the auxiliary space. Therefore, the auxiliary space complexity is O(F), where F is the number of unique features.

Edge Cases

Case	How to Handle
Empty feature list or empty feature requests list	Return an empty list or original feature list respectively, as there's nothing to sort or no requests to base the sort on.
Null feature list or null feature requests list	Throw an IllegalArgumentException (or equivalent) to indicate invalid input.
Feature requests list contains duplicates	Count the occurrences of each feature, so duplicates increment popularity accordingly.
Feature requests list contains null or empty strings	Ignore null/empty strings during processing or throw an exception depending on requirements.
featureList contains duplicate feature names	Handle the first occurrence, or aggregate popularity from requests for all duplicate feature names.
Very large featureList or featureRequestsList causing potential memory issues	Consider using more memory efficient data structures or processing the data in chunks.
Feature requests contain feature names not present in featureList	Ignore these irrelevant feature requests, or log them for analysis/reporting if required.
Tie in popularity count between multiple features, maintaining original order	Use a stable sorting algorithm to preserve the original order among features with the same popularity count.

Empty feature list or empty feature requests list

How to Handle:

Return an empty list or original feature list respectively, as there's nothing to sort or no requests to base the sort on.

Null feature list or null feature requests list

How to Handle:

Throw an IllegalArgumentException (or equivalent) to indicate invalid input.

Feature requests list contains duplicates

How to Handle:

Count the occurrences of each feature, so duplicates increment popularity accordingly.

Feature requests list contains null or empty strings

How to Handle:

Ignore null/empty strings during processing or throw an exception depending on requirements.

featureList contains duplicate feature names

How to Handle:

Handle the first occurrence, or aggregate popularity from requests for all duplicate feature names.

Very large featureList or featureRequestsList causing potential memory issues

How to Handle:

Consider using more memory efficient data structures or processing the data in chunks.

Feature requests contain feature names not present in featureList

How to Handle:

Ignore these irrelevant feature requests, or log them for analysis/reporting if required.

Tie in popularity count between multiple features, maintaining original order

How to Handle:

Use a stable sorting algorithm to preserve the original order among features with the same popularity count.