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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Grouping Anagrams by Sorted Key

What is the output of the following C code that groups anagrams using a hash map keyed by sorted strings?

DSA C

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

// Simple hash map node for demonstration
typedef struct Node {
    char *key;
    char **words;
    int count;
    int capacity;
    struct Node *next;
} Node;

// Function to sort characters in a string
void sortString(char *str) {
    int len = strlen(str);
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if (str[i] > str[j]) {
                char temp = str[i];
                str[i] = str[j];
                str[j] = temp;
            }
        }
    }
}

// Insert word into hash map node
void insertWord(Node *node, char *word) {
    if (node->count == node->capacity) {
        node->capacity *= 2;
        node->words = realloc(node->words, node->capacity * sizeof(char*));
    }
    node->words[node->count++] = word;
}

// Simple hash function
unsigned int hash(char *str) {
    unsigned int h = 0;
    while (*str) {
        h = h * 31 + *str++;
    }
    return h % 10;
}

// Find or create node in hash map
Node* findOrCreate(Node **map, char *key) {
    unsigned int h = hash(key);
    Node *curr = map[h];
    while (curr) {
        if (strcmp(curr->key, key) == 0) return curr;
        curr = curr->next;
    }
    Node *newNode = malloc(sizeof(Node));
    newNode->key = strdup(key);
    newNode->capacity = 2;
    newNode->count = 0;
    newNode->words = malloc(newNode->capacity * sizeof(char*));
    newNode->next = map[h];
    map[h] = newNode;
    return newNode;
}

int main() {
    char *words[] = {"eat", "tea", "tan", "ate", "nat", "bat"};
    int n = 6;
    Node *map[10] = {0};

    for (int i = 0; i < n; i++) {
        char *copy = strdup(words[i]);
        sortString(copy);
        Node *node = findOrCreate(map, copy);
        insertWord(node, words[i]);
        free(copy);
    }

    // Print groups
    for (int i = 0; i < 10; i++) {
        Node *curr = map[i];
        while (curr) {
            printf("Group: ");
            for (int j = 0; j < curr->count; j++) {
                printf("%s ", curr->words[j]);
            }
            printf("\n");
            curr = curr->next;
        }
    }
    return 0;
}

A

Group: bat 
Group: tan 
Group: nat 
Group: eat 
Group: tea 
Group: ate 

B

Group: eat tea ate 
Group: bat 
Group: tan nat 

C

Group: bat 
Group: tan nat 
Group: eat tea ate 

D

Group: bat tan nat eat tea ate 

💡 Hint

Think about how sorting the characters in each word groups anagrams together.

The code sorts each word to create a key. Words with the same sorted key are grouped together. The hash map stores these groups. The output prints groups of anagrams.

🧠 Conceptual

intermediate

Why Use Sorted Strings as Keys in Grouping Anagrams?

Why do we use the sorted version of a word as the key in a hash map when grouping anagrams?

A Because sorting words makes them shorter and easier to store.

B Because sorted strings are unique identifiers for anagram groups.

C Because sorted strings are always the same length as original words.

D Because sorting words removes duplicate letters.

💡 Hint

Think about what makes anagrams similar.

Anagrams have the same letters in different orders. Sorting letters puts them in a standard order, so all anagrams share the same sorted string key.

🔧 Debug

advanced

Identify the Error in Hash Map Grouping Code

What error will this code produce when grouping anagrams using a hash map keyed by sorted strings?

DSA C

char *words[] = {"abc", "bca", "cab"};
Node *map[5] = {0};

for (int i = 0; i < 3; i++) {
    char *copy = strdup(words[i]);
    sortString(copy);
    Node *node = findOrCreate(map, copy);
    insertWord(node, copy);
    free(copy);
}

A No error; code runs correctly.

B Segmentation fault because map size is too small.

C Memory leak because 'copy' is never freed.

D Use after free error due to freeing 'copy' after inserting it.

💡 Hint

Check what happens to 'copy' after inserting it into the node.

The code inserts 'copy' pointer into the node, then frees 'copy'. Later access to that pointer causes use after free error.

❓ Predict Output

advanced

Output of Group Anagrams with Different Hash Function

What is the output of this code that groups anagrams using a hash map with a hash function returning constant 0?

DSA C

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

typedef struct Node {
    char *key;
    char **words;
    int count;
    int capacity;
    struct Node *next;
} Node;

void sortString(char *str) {
    int len = strlen(str);
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if (str[i] > str[j]) {
                char temp = str[i];
                str[i] = str[j];
                str[j] = temp;
            }
        }
    }
}

void insertWord(Node *node, char *word) {
    if (node->count == node->capacity) {
        node->capacity *= 2;
        node->words = realloc(node->words, node->capacity * sizeof(char*));
    }
    node->words[node->count++] = word;
}

unsigned int hash(char *str) {
    return 0; // constant hash to force collisions
}

Node* findOrCreate(Node **map, char *key) {
    unsigned int h = hash(key);
    Node *curr = map[h];
    while (curr) {
        if (strcmp(curr->key, key) == 0) return curr;
        curr = curr->next;
    }
    Node *newNode = malloc(sizeof(Node));
    newNode->key = strdup(key);
    newNode->capacity = 2;
    newNode->count = 0;
    newNode->words = malloc(newNode->capacity * sizeof(char*));
    newNode->next = map[h];
    map[h] = newNode;
    return newNode;
}

int main() {
    char *words[] = {"eat", "tea", "tan", "ate", "nat", "bat"};
    int n = 6;
    Node *map[1] = {0};

    for (int i = 0; i < n; i++) {
        char *copy = strdup(words[i]);
        sortString(copy);
        Node *node = findOrCreate(map, copy);
        insertWord(node, words[i]);
        free(copy);
    }

    Node *curr = map[0];
    while (curr) {
        printf("Group: ");
        for (int j = 0; j < curr->count; j++) {
            printf("%s ", curr->words[j]);
        }
        printf("\n");
        curr = curr->next;
    }
    return 0;
}

A

Group: bat 
Group: tan nat 
Group: eat tea ate 

B

Group: eat tea ate 
Group: bat 
Group: tan nat 

C

Group: bat tan nat eat tea ate 

D

Group: eat tea ate bat tan nat 

💡 Hint

All keys hash to the same bucket, so groups are stored in a linked list.

The constant hash 0 puts all nodes in bucket 0. New nodes are prepended: 'aet' first, then 'ant' -> 'aet', then 'abt' -> 'ant' -> 'aet'. Printing traverses: 'bat', 'tan nat', 'eat tea ate'.

🚀 Application

expert

Number of Unique Anagram Groups

Given the list of words {"listen", "silent", "enlist", "google", "gogole", "abc", "cab"}, how many unique anagram groups will be formed using a hash map keyed by sorted strings?

A 3

B 6

C 5

D 4

💡 Hint

Group words by their sorted letters and count distinct groups.

The groups are: {"listen", "silent", "enlist"} (sorted 'eilnst'), {"google", "gogole"} (sorted 'eggloo'), {"abc", "cab"} (sorted 'abc'). 3 unique groups.