We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sort Features by Popularity

Number: 1919

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given an array of feature names and an array of user responses (each response being a string of space-separated words), calculate the popularity of each feature as the number of responses that mention it at least once. Then, return the list of features sorted in non-increasing order by popularity. If two features have the same popularity, preserve their original order from the features array.

Key Insights

  • Use a set to store words from each response to avoid counting duplicate mentions in the same response.
  • Use a dictionary (or hash map) to count how many responses mention each feature.
  • Preserve the original index to handle ties by sorting features with equal counts by their order in the input list.
  • Sorting involves first sorting by popularity (in descending order) and then by the original index (in ascending order).

Space and Time Complexity

Time Complexity: O(R * L + F log F)

  • R: number of responses.
  • L: average number of words per response.
  • F: number of features. Space Complexity: O(F + W)
  • F: space for the features count dictionary.
  • W: auxiliary space for the word sets per response (processed one at a time).

Solution

We first create a mapping from each feature name to its corresponding index and initialize a count dictionary for popularity. For each response, split the string into words and convert them into a set to remove duplicates. Then, for every feature in the set that also appears in the features list, increment its count. Finally, sort the features based on their popularity in descending order; if counts are equal, use the original index (ascending order) to decide the order.

Code Solutions

# Define a function to sort features by popularity
def sort_features_by_popularity(features, responses):
    # Create a mapping for features to their initial index for tie-breaking
    feature_to_index = {feature: i for i, feature in enumerate(features)}
    # Initialize popularity dictionary with zero counts for each feature
    popularity = {feature: 0 for feature in features}

    # Process each response
    for response in responses:
        # Convert response into a set of words to count unique occurrences
        unique_words = set(response.split())
        # Update count for features mentioned in the unique set
        for word in unique_words:
            if word in popularity:
                popularity[word] += 1

    # Sort features by:
    # 1. Popularity in descending order (reverse count), then
    # 2. By original index in ascending order if popularity is the same
    features_sorted = sorted(features, key=lambda x: (-popularity[x], feature_to_index[x]))
    return features_sorted

# Example test
features = ["cooler", "lock", "touch"]
responses = ["i like cooler cooler", "lock touch cool", "locker like touch"]
print(sort_features_by_popularity(features, responses))
← Back to All Questions