Sort Features by Popularity - Practice Coding Problems

Sort Features by Popularity - Problem

You are given a string array features where features[i] is a single word that represents the name of a feature of the latest product you are working on. You have made a survey where users have reported which features they like.

You are given a string array responses, where each responses[i] is a string containing space-separated words. The popularity of a feature is the number of responses[i] that contain the feature.

You want to sort the features in non-increasing order by their popularity. If two features have the same popularity, order them by their original index in features.

Notice that one response could contain the same feature multiple times; this feature is only counted once in its popularity.

Return the features in sorted order.

Input & Output

Example 1 — Basic Case

$ Input: features = ["cooler","lock","touch"], responses = ["i love cooler cooler","lock touch cool","cooler lock"]

› Output: ["cooler","lock","touch"]

💡 Note: cooler appears in 2 responses, lock appears in 2 responses, touch appears in 1 response. cooler and lock have same count but cooler has lower index (0 vs 1).

Example 2 — Different Popularity

$ Input: features = ["a","aa","aaa"], responses = ["a aa a","a aa","aaa","a"]

› Output: ["a","aa","aaa"]

💡 Note: a appears in 3 responses, aa appears in 2 responses, aaa appears in 1 response. Sort by popularity: a > aa > aaa.

Example 3 — Tie Breaking

$ Input: features = ["x","y","z"], responses = ["x y","y z"]

› Output: ["y","x","z"]

💡 Note: y appears in 2 responses, x and z each appear in 1 response. y comes first, then x before z due to original order.

Constraints

1 ≤ features.length ≤ 10⁴
1 ≤ features[i].length ≤ 4
features[i] consists of lowercase letters
1 ≤ responses.length ≤ 10³
1 ≤ responses[i].length ≤ 10³
responses[i] consists of lowercase letters and spaces
responses[i] contains no two consecutive spaces
There are no duplicate features

Visualization

Tap to expand

Understanding the Visualization

Input

Features array and user responses mentioning features

Count

Count unique mentions of each feature across responses

Sort

Rank features by popularity, tie-break by original index

Key Takeaway

🎯 Key Insight: Count feature mentions efficiently with a hash map, then sort by popularity with original index as tie-breaker

Asked in

a Amazon 15 G Google 12 M Microsoft 8 f Facebook 6

The key insight is to count feature popularity efficiently using a hash map, then sort by count (descending) with tie-breaking by original index. Best approach uses frequency counting with O(m×k + n log n) time and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n×m×k)	O(n)	Count popularity for each feature by scanning all responses
Frequency Count with Hash Map	O(m×k + n log n)	O(n)	Use hash map to efficiently count feature popularity across all responses

Brute Force — Algorithm Steps

For each feature, count occurrences across all responses
Create pairs of (feature, popularity)
Sort by popularity (descending) and original index (ascending)

Visualization

Tap to expand

Step-by-Step Walkthrough

For Each Feature

Iterate through each feature in the array

Count Responses

Scan all responses to count mentions of current feature

Sort Results

Sort features by popularity count, tie-break by index

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int count;
    int index;
    char name[100];
} FeatureData;

int compare(const void* a, const void* b) {
    FeatureData* fa = (FeatureData*)a;
    FeatureData* fb = (FeatureData*)b;
    
    if (fa->count != fb->count) {
        return fb->count - fa->count; // Descending by count
    }
    return fa->index - fb->index; // Ascending by index
}

char** solution(char features[][100], int featuresSize, char responses[][1000], int responsesSize, int* returnSize) {
    FeatureData popularity[featuresSize];
    
    for (int i = 0; i < featuresSize; i++) {
        int count = 0;
        
        for (int j = 0; j < responsesSize; j++) {
            char* response = strdup(responses[j]);
            char* words[1000];
            int wordCount = 0;
            
            char* token = strtok(response, " ");
            while (token != NULL) {
                int found = 0;
                for (int k = 0; k < wordCount; k++) {
                    if (strcmp(words[k], token) == 0) {
                        found = 1;
                        break;
                    }
                }
                if (!found) {
                    words[wordCount++] = strdup(token);
                }
                token = strtok(NULL, " ");
            }
            
            for (int k = 0; k < wordCount; k++) {
                if (strcmp(words[k], features[i]) == 0) {
                    count++;
                    break;
                }
            }
            
            free(response);
            for (int k = 0; k < wordCount; k++) {
                free(words[k]);
            }
        }
        
        popularity[i].count = count;
        popularity[i].index = i;
        strcpy(popularity[i].name, features[i]);
    }
    
    qsort(popularity, featuresSize, sizeof(FeatureData), compare);
    
    char** result = malloc(featuresSize * sizeof(char*));
    for (int i = 0; i < featuresSize; i++) {
        result[i] = malloc(100 * sizeof(char));
        strcpy(result[i], popularity[i].name);
    }
    
    *returnSize = featuresSize;
    return result;
}

int main() {
    char features[100][100];
    char responses[100][1000];
    int featuresSize = 0, responsesSize = 0;
    
    // Simple parsing for testing
    char line[10000];
    fgets(line, sizeof(line), stdin);
    // Parse features (simplified)
    
    fgets(line, sizeof(line), stdin);
    // Parse responses (simplified)
    
    int returnSize;
    char** result = solution(features, featuresSize, responses, responsesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
        free(result[i]);
    }
    printf("]\n");
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m×k)

For each of n features, scan m responses with average k words each

✓ Linear Growth

Space Complexity

O(n)

Array to store feature popularity pairs

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler