Challenge - 5 Problems
Chaining Mastery
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of inserting keys in a chained hash table
What is the printed state of the hash table after inserting keys 10, 22, 31, 4, 15, 28, 17, 88, 59 using chaining with hash function h(key) = key % 10?
DSA C
typedef struct Node {
int key;
struct Node* next;
} Node;
Node* hashTable[10] = {NULL};
void insert(int key) {
int index = key % 10;
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->next = hashTable[index];
hashTable[index] = newNode;
}
void printTable() {
for (int i = 0; i < 10; i++) {
printf("%d: ", i);
Node* temp = hashTable[i];
while (temp) {
printf("%d -> ", temp->key);
temp = temp->next;
}
printf("NULL\n");
}
}
int main() {
int keys[] = {10, 22, 31, 4, 15, 28, 17, 88, 59};
int n = sizeof(keys)/sizeof(keys[0]);
for (int i = 0; i < n; i++) {
insert(keys[i]);
}
printTable();
return 0;
}Attempts:
2 left
💡 Hint
Remember that new nodes are inserted at the head of the linked list for each bucket.
✗ Incorrect
The hash function is key % 10. Each key is inserted at the head of the linked list at the computed index. For example, 28 and 88 both hash to 8. Since 88 is inserted after 28, it becomes the new head, so the list at index 8 is 88 -> 28 -> NULL.
🧠 Conceptual
intermediate1:00remaining
Number of items in a chained hash table bucket
If a hash table uses chaining and the hash function distributes keys uniformly, what is the expected number of items in each bucket after inserting n keys into a table with m buckets?
Attempts:
2 left
💡 Hint
Think about how keys are spread evenly across buckets.
✗ Incorrect
If keys are uniformly distributed, each bucket gets about n/m keys on average.
🔧 Debug
advanced1:30remaining
Identify the bug in chaining insertion code
What error will this code cause when inserting keys into a chained hash table?
Code snippet:
void insert(int key) {
int index = key % 10;
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->next = NULL;
if (hashTable[index] == NULL) {
hashTable[index] = newNode;
} else {
Node* temp = hashTable[index];
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}
Assume hashTable is an array of Node* initialized to NULL.
Attempts:
2 left
💡 Hint
Check how the linked list is traversed and where the new node is added.
✗ Incorrect
The code correctly inserts new nodes at the end of the linked list for the bucket. The hashTable array is assumed initialized to NULL, so no segmentation fault. No infinite loop occurs because the loop stops at last node. Memory leak is unrelated to insertion logic.
❓ Predict Output
advanced2:00remaining
Output after deleting a key from chained hash table
Given the hash table with chaining below, what is the printed state after deleting key 15?
Initial state:
0: 10 -> NULL
1: 31 -> NULL
2: 22 -> NULL
3: NULL
4: 4 -> NULL
5: 15 -> 25 -> NULL
6: NULL
7: 17 -> NULL
8: 88 -> 28 -> NULL
9: 59 -> NULL
Deletion code removes the first occurrence of key 15 in the chain at index 5.
DSA C
void deleteKey(int key) { int index = key % 10; Node* temp = hashTable[index]; Node* prev = NULL; while (temp != NULL && temp->key != key) { prev = temp; temp = temp->next; } if (temp == NULL) return; // key not found if (prev == NULL) { hashTable[index] = temp->next; } else { prev->next = temp->next; } free(temp); } // After calling deleteKey(15), printTable() is called.
Attempts:
2 left
💡 Hint
Deleting key 15 removes the first node with key 15 in the chain.
✗ Incorrect
Key 15 is at the head of the chain at index 5. After deletion, the head points to the next node with key 25.
🧠 Conceptual
expert1:30remaining
Why chaining is preferred over open addressing in high load factor scenarios
Why is chaining often preferred over open addressing when the hash table load factor is high (close to or greater than 1)?
Attempts:
2 left
💡 Hint
Think about how collisions are handled and how performance changes as table fills up.
✗ Incorrect
Chaining stores collided keys in linked lists, so it can handle many keys per bucket without performance dropping drastically. Open addressing suffers from clustering and long probe sequences at high load factors.