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 and table size 10?
DSA C++
class HashTable { public: static const int TABLE_SIZE = 10; std::list<int> table[TABLE_SIZE]; int hashFunction(int key) { return key % TABLE_SIZE; } void insert(int key) { int index = hashFunction(key); table[index].push_back(key); } void printTable() { for (int i = 0; i < TABLE_SIZE; i++) { std::cout << i << " -> "; for (int key : table[i]) { std::cout << key << " -> "; } std::cout << "null" << std::endl; } } }; int main() { HashTable ht; int keys[] = {10, 22, 31, 4, 15, 28, 17, 88, 59}; for (int key : keys) { ht.insert(key); } ht.printTable(); return 0; }
Attempts:
2 left
💡 Hint
Calculate key % 10 for each key and add it to the linked list at that index.
✗ Incorrect
The hash function is key % 10. Keys are inserted in the list at the index equal to their hash. For example, 10 % 10 = 0, so 10 goes to index 0. 22 % 10 = 2, so 22 goes to index 2. 28 % 10 = 8, so 28 goes to index 8. 88 % 10 = 8, so 88 is chained after 28 at index 8. The final table shows these chains.
🧠 Conceptual
intermediate1:30remaining
Understanding collision handling with chaining
Why is chaining a good method to handle collisions in a hash table?
Attempts:
2 left
💡 Hint
Think about how multiple keys can be stored at the same index.
✗ Incorrect
Chaining stores collided keys in a linked list at the same index. This way, multiple keys can be stored without overwriting each other. Open addressing and resizing are different collision handling methods.
🔧 Debug
advanced1:30remaining
Identify the error in chaining insertion code
What error will occur when running this code snippet for inserting a key into a chained hash table?
std::list table[10];
int hashFunction(int key) { return key % 10; }
void insert(int key) {
int index = hashFunction(key);
table[index].push_back(key);
}
Assuming this is part of a class and called correctly.
Attempts:
2 left
💡 Hint
Check if the list array is properly declared and used.
✗ Incorrect
The code declares an array of lists and uses push_back to insert keys at the correct index. There is no syntax or runtime error here.
❓ Predict Output
advanced2:00remaining
Output after deleting a key from chained hash table
Given a chained hash table with keys 10, 20, 30 inserted using h(key) = key % 10, what is the printed table after deleting key 20?
DSA C++
class HashTable { public: static const int TABLE_SIZE = 10; std::list<int> table[TABLE_SIZE]; int hashFunction(int key) { return key % TABLE_SIZE; } void insert(int key) { int index = hashFunction(key); table[index].push_back(key); } void remove(int key) { int index = hashFunction(key); table[index].remove(key); } void printTable() { for (int i = 0; i < TABLE_SIZE; i++) { std::cout << i << " -> "; for (int key : table[i]) { std::cout << key << " -> "; } std::cout << "null" << std::endl; } } }; int main() { HashTable ht; ht.insert(10); ht.insert(20); ht.insert(30); ht.remove(20); ht.printTable(); return 0; }
Attempts:
2 left
💡 Hint
20 % 10 = 0, so 20 is in the list at index 0 and should be removed.
✗ Incorrect
Keys 10, 20, 30 all hash to index 0. After removing 20, only 10 and 30 remain chained at index 0.
🚀 Application
expert1:30remaining
Analyzing average search time in chaining hash table
If a hash table uses chaining and has 1000 keys stored in 100 buckets, what is the average number of keys checked during a successful search assuming uniform distribution?
Attempts:
2 left
💡 Hint
Average chain length = total keys / number of buckets.
✗ Incorrect
With 1000 keys and 100 buckets, average chain length is 1000/100 = 10. On average, 10 keys are checked during a successful search.