Group Anagrams Using Hash Map in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Grouping Anagrams by Sorted Key

What is the output of the following Python code that groups anagrams using a hash map with sorted strings as keys?

DSA Python

from collections import defaultdict
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
groups = defaultdict(list)
for word in words:
    key = ''.join(sorted(word))
    groups[key].append(word)
result = list(groups.values())
print(result)

A [['eat', 'tea'], ['tan', 'nat'], ['bat', 'ate']]

B [['eat'], ['tea'], ['tan'], ['ate'], ['nat'], ['bat']]

C [['eat', 'ate'], ['tea', 'tan'], ['nat', 'bat']]

D [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

💡 Hint

Think about how sorting each word groups anagrams together.

The code sorts each word to create a key. Anagrams have the same sorted key, so they are grouped together in the dictionary. The final list contains groups of anagrams.

🧠 Conceptual

intermediate

Key Choice for Grouping Anagrams

Which of the following is the best key to use in a hash map to group anagrams efficiently?

A The first character of the word

B The length of the word

C The sorted string of the word

D The sum of ASCII values of characters in the word

💡 Hint

Anagrams have the same letters in different orders.

Sorting the string puts all letters in order, so anagrams become identical keys. Length or first character alone cannot uniquely identify anagrams. Sum of ASCII values can cause collisions.

🔧 Debug

advanced

Identify the Error in Anagram Grouping Code

What error does the following code produce when grouping anagrams using a hash map?

DSA Python

words = ["bat", "tab", "eat"]
groups = {}
for word in words:
    key = sorted(word)
    if key not in groups:
        groups[key] = []
    groups[key].append(word)
print(groups)

A KeyError: key not found

B TypeError: unhashable type: 'list'

C SyntaxError: invalid syntax

D No error, prints grouped anagrams

💡 Hint

Check the type of the key used in the dictionary.

The sorted(word) returns a list, which is unhashable and cannot be used as a dictionary key, causing a TypeError.

❓ Predict Output

advanced

Output of Grouping Anagrams Using Character Count as Key

What is the output of this Python code that groups anagrams using character count as the hash map key?

DSA Python

from collections import defaultdict
words = ["abc", "bca", "cab", "xyz", "zyx", "yxz"]
groups = defaultdict(list)
for word in words:
    count = [0]*26
    for ch in word:
        count[ord(ch) - ord('a')] += 1
    groups[tuple(count)].append(word)
result = list(groups.values())
print(result)

A [['abc', 'bca', 'cab'], ['xyz', 'zyx', 'yxz']]

B [['abc', 'xyz'], ['bca', 'zyx'], ['cab', 'yxz']]

C [['abc'], ['bca'], ['cab'], ['xyz'], ['zyx'], ['yxz']]

D [['abc', 'bca'], ['cab', 'xyz'], ['zyx', 'yxz']]

💡 Hint

Character count arrays uniquely identify anagrams.

The code counts characters for each word and uses the count tuple as key. Anagrams have identical counts, so they group together.

🧠 Conceptual

expert

Why Use Tuple Instead of List as Hash Map Key in Anagram Grouping?

Why is a tuple preferred over a list as a key in a hash map when grouping anagrams by character count?

A Tuples are immutable and hashable, lists are mutable and unhashable

B Tuples use less memory than lists

C Lists are faster to access than tuples

D Lists cannot store integers

💡 Hint

Dictionary keys must be hashable and immutable.

Lists can change after creation, so they cannot be used as dictionary keys. Tuples cannot change and are hashable, making them valid keys.

Practice

1. What is the main idea behind grouping anagrams using a hash map?

easy

A. Use the first character of the string as the key

B. Use the length of the string as the key

C. Use sorted strings as keys to group words with the same letters

D. Use the last character of the string as the key

Solution

1. Step 1: Understand anagrams

   Anagrams are words with the same letters in different orders.

2. Step 2: Use sorted strings as keys

   Sorting letters of each word gives a common key for all anagrams.

3. Final Answer:

   Use sorted strings as keys to group words with the same letters -> Option C

4. Quick Check:

   Sorted string key groups anagrams = C [OK]

Hint: Sort each word to find its anagram group key [OK]

Common Mistakes:

• Using string length as key groups wrong words
• Using first or last character misses many anagrams
• Not sorting letters before using as key

2. Which of the following Python code snippets correctly initializes an empty hash map (dictionary) to group anagrams?

easy

A. anagrams = {}

B. anagrams = ()

C. anagrams = set()

D. anagrams = []

Solution

1. Step 1: Identify dictionary initialization

   In Python, an empty dictionary is created with curly braces {}.

2. Step 2: Check other options

   List uses [], set uses set(), tuple uses (). Only {} is dictionary.

3. Final Answer:

   anagrams = {} -> Option A

4. Quick Check:

   Empty dictionary = {} [OK]

Hint: Use {} to create an empty dictionary in Python [OK]

Common Mistakes:

• Using [] which creates a list, not a dictionary
• Using set() which creates a set, not a dictionary
• Using () which creates a tuple, not a dictionary

3. What is the output of the following code?

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
anagrams = {}
for word in words:
    key = ''.join(sorted(word))
    if key not in anagrams:
        anagrams[key] = []
    anagrams[key].append(word)
print(list(anagrams.values()))

medium

A. [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

B. [['eat', 'tea'], ['tan', 'nat'], ['bat', 'ate']]

C. [['eat', 'ate'], ['tan', 'nat'], ['bat', 'tea']]

D. [['eat'], ['tea'], ['tan'], ['ate'], ['nat'], ['bat']]

Solution

1. Step 1: Sort each word and group

   Words "eat", "tea", "ate" sorted become "aet"; grouped together. "tan", "nat" sorted "ant"; grouped. "bat" sorted "abt"; alone.

2. Step 2: Collect groups in dictionary values

   Values are lists of grouped anagrams: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

3. Final Answer:

   [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']] -> Option A

4. Quick Check:

   Sorted keys group words correctly = A [OK]

Hint: Sort letters, use as key, group words in list [OK]

Common Mistakes:

• Appending words to wrong keys
• Not sorting words before grouping
• Mixing groups or missing words

4. Find the error in this code that tries to group anagrams:

words = ["abc", "bca", "cab"]
anagrams = {}
for word in words:
    key = sorted(word)
    if key not in anagrams:
        anagrams[key] = []
    anagrams[key].append(word)
print(anagrams)

medium

A. The dictionary is not initialized correctly

B. The print statement syntax is wrong

C. The append method is used incorrectly

D. sorted(word) returns a list, which cannot be used as a dictionary key

Solution

1. Step 1: Check key type used in dictionary

   sorted(word) returns a list, but lists are not hashable and cannot be dictionary keys.

2. Step 2: Fix by converting list to string or tuple

   Use key = ''.join(sorted(word)) or key = tuple(sorted(word)) to make hashable key.

3. Final Answer:

   sorted(word) returns a list, which cannot be used as a dictionary key -> Option D

4. Quick Check:

   Dictionary keys must be hashable, list is not [OK]

Hint: Convert sorted list to string or tuple before using as key [OK]

Common Mistakes:

• Using list as dictionary key causes TypeError
• Not converting sorted result to string or tuple
• Ignoring error messages about unhashable types

5. Given the list words = ["listen", "silent", "enlist", "google", "gogole", "abc"], which code snippet correctly groups the anagrams and returns the groups sorted alphabetically by their first word?

hard

A. anagrams = {}
for w in words:
key = w
anagrams[key] = w
print(list(anagrams.values()))

B. anagrams = {}
for w in words:
key = ''.join(sorted(w))
anagrams.setdefault(key, []).append(w)
groups = list(anagrams.values())
groups.sort(key=lambda x: x[0])
print(groups)

C. anagrams = {}
for w in words:
key = ''.join(sorted(w))
anagrams[key] = w
print(list(anagrams.keys()))

D. anagrams = []
for w in words:
anagrams.append(sorted(w))
print(anagrams)

Solution

1. Step 1: Group words by sorted key using dictionary

   anagrams = {} for w in words: key = ''.join(sorted(w)) anagrams.setdefault(key, []).append(w) groups = list(anagrams.values()) groups.sort(key=lambda x: x[0]) print(groups) uses sorted word as key and appends words to list correctly.

2. Step 2: Sort groups by first word

   anagrams = {} for w in words: key = ''.join(sorted(w)) anagrams.setdefault(key, []).append(w) groups = list(anagrams.values()) groups.sort(key=lambda x: x[0]) print(groups) sorts the list of groups by the first word in each group, meeting requirement.

3. Final Answer:

   Correctly groups anagrams using sorted keys, setdefault, append, and sorts groups by first word -> Option B

4. Quick Check:

   Group by sorted key + sort groups by first word = A [OK]

Hint: Use setdefault for grouping and sort groups by first element [OK]

Common Mistakes:

• Using word itself as key loses grouping
• Overwriting dictionary values instead of appending
• Using list instead of dictionary for grouping