How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Salesforce.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Salesforce during technical interviews.

Design O(nm) grouping of rearranged strings | Salesforce Coding Question

Design O(nm) grouping of rearranged strings

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an array of strings, group together words that are permutations of the same characters. Provide a baseline solution that sorts each word (O(n · m log m), where n is the number of words and m is max word length). Then, under assumptions such as inputs consist only of lowercase 'a'–'z', design an O(n · m) solution using character-frequency hashing. Specify how you construct a stable key (e.g., serialized counts), handle collisions, and analyze time and space trade-offs versus sorting.

Quick Answer: This question evaluates a candidate's understanding of string manipulation, hashing and frequency-count techniques, algorithmic optimization, and time/space complexity analysis when grouping anagrams.

Given an array of strings `words`, group together all words that are permutations (anagrams) of one another and return the list of groups. A baseline approach sorts each word to form a canonical key, costing O(n·m log m) where n is the number of words and m is the maximum word length. Under the assumption that every word consists only of lowercase letters 'a'–'z', you can do better: build a stable key from a 26-element character-frequency count instead of sorting, achieving O(n·m) time. **Key construction:** For each word, compute the count of each of the 26 letters and serialize those counts into a string key (e.g. join the counts with a separator like `'#'`). Two words are anagrams iff their count vectors are identical, so they map to the same key. Using a non-numeric separator between counts prevents collisions between counts of different magnitude (e.g. `[1,12]` vs `[11,2]`). Return the groups as a list of lists. For deterministic output: groups appear in the order their first member was encountered in the input, and the words inside each group are sorted in ascending (lexicographic) order. The original word strings are preserved (not the sorted/canonical form).

Constraints

1 <= n <= 10^4 (number of words); the array may also be empty.
0 <= len(word) <= 100
Each word consists only of lowercase English letters 'a'–'z' (the empty string is allowed).
Total characters across all words fit comfortably in memory.

Examples

Input: (["eat", "tea", "tan", "ate", "nat", "bat"],)

Expected Output: [['ate', 'eat', 'tea'], ['nat', 'tan'], ['bat']]

Explanation: eat/tea/ate share counts {a,e,t}; tan/nat share {a,n,t}; bat is alone. Groups appear in first-seen order; each group's words are sorted.

Input: ([""],)

Expected Output: [['']]

Explanation: A single empty string forms one group containing just the empty string (its count vector is all zeros).

Input: (["a"],)

Expected Output: [['a']]

Explanation: A single one-character word forms its own group.

Input: (["abc", "bca", "cab", "xyz"],)

Expected Output: [['abc', 'bca', 'cab'], ['xyz']]

Explanation: abc/bca/cab are all permutations of {a,b,c}; xyz is distinct.

Input: (["aab", "aba", "baa", "aab"],)

Expected Output: [['aab', 'aab', 'aba', 'baa']]

Explanation: All four words have counts a:2, b:1, so they collapse into one group; the duplicate 'aab' is preserved, and the group is sorted alphabetically.

Input: ([],)

Expected Output: []

Explanation: Empty input yields no groups.

Hints

Two words are anagrams iff they have the same multiset of characters. Avoid sorting each word — instead derive a key directly from character counts.
Use a fixed-size array of 26 integers (one per letter) as the count vector, then serialize it into a hashable key.
Serialize counts with a separator between numbers (e.g. join with '#') so that [1, 12] and [11, 2] don't collide into the same string.
A dictionary preserves insertion order in modern Python, giving deterministic first-seen group ordering; sort each group's words before returning for a stable result.

Quick Overview

This question evaluates a candidate's understanding of string manipulation, hashing and frequency-count techniques, algorithmic optimization, and time/space complexity analysis when grouping anagrams.