HashMap Implementation from Scratch in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the array that stores the buckets in the HashMap class.

DSA C#

private LinkedList<KeyValuePair<TKey, TValue>>[] [1];

Drag options to blanks, or click blank then click option'

Aitems

Belements

Cnodes

Dbuckets

Attempts:

3 left

💡 Hint

Common Mistakes

Using a generic name like 'items' which is less descriptive.

Using singular form instead of plural.

The array that stores the buckets is commonly named 'buckets' to represent the storage slots for key-value pairs.

2fill in blank

medium

Complete the code to compute the index for a given key in the HashMap.

DSA C#

int index = Math.Abs(key.GetHashCode()) [1] buckets.Length;

Drag options to blanks, or click blank then click option'

A/

B%

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using division '/' which returns a quotient, not an index.

Using multiplication '*' which can exceed array bounds.

The modulo operator '%' is used to ensure the index fits within the array bounds.

3fill in blank

hard

Fix the error in the Add method to correctly add a new key-value pair to the bucket.

DSA C#

if (buckets[index] == null) {
    buckets[index] = new LinkedList<KeyValuePair<TKey, TValue>>();
}

buckets[index].[1](new KeyValuePair<TKey, TValue>(key, value));

Drag options to blanks, or click blank then click option'

AAddLast

BAddFirst

CAddAfter

DAddBefore

Attempts:

3 left

💡 Hint

Common Mistakes

Using AddFirst which adds at the start and may affect order.

Using AddBefore or AddAfter without a reference node.

AddLast adds the new key-value pair at the end of the linked list, which is the standard approach.

4fill in blank

hard

Fill both blanks to complete the Remove method that deletes a key-value pair by key.

DSA C#

int index = Math.Abs(key.GetHashCode()) [1] buckets.Length;

if (buckets[index] != null) {
    var current = buckets[index].First;
    while (current != null) {
        if (current.Value.Key.Equals(key)) {
            buckets[index].[2](current);
            return true;
        }
        current = current.Next;
    }
}
return false;

Drag options to blanks, or click blank then click option'

A%

B/

CRemove

DRemoveFirst

Attempts:

3 left

💡 Hint

Common Mistakes

Using division '/' instead of modulo for index calculation.

Using RemoveFirst which removes the first node regardless of key.

The modulo operator '%' calculates the index, and Remove removes the node from the linked list.

5fill in blank

hard

Fill all three blanks to complete the TryGetValue method that retrieves a value by key.

DSA C#

int index = Math.Abs(key.GetHashCode()) [1] buckets.Length;

if (buckets[index] != null) {
    foreach (var pair in buckets[index]) {
        if (pair.Key.[2](key)) {
            value = pair.[3];
            return true;
        }
    }
}
value = default;
return false;

Drag options to blanks, or click blank then click option'

A%

BEquals

CValue

DContains

Attempts:

3 left

💡 Hint

Common Mistakes

Using Contains which is not a method on keys.

Using incorrect property names for accessing value.

Modulo '%' calculates the index, Equals compares keys, and Value accesses the stored value.

Practice

1. What is the main purpose of a HashMap in data structures?

easy

A. To store data sequentially like a list

B. To store key-value pairs for fast data retrieval

C. To store data in a sorted order

D. To perform mathematical calculations

Solution

1. Step 1: Understand the role of HashMap

   A HashMap stores data as key-value pairs, allowing quick access to values using keys.

2. Step 2: Compare with other data structures

   Unlike lists or arrays, HashMaps do not store data sequentially or sorted but focus on fast lookup.

3. Final Answer:

   To store key-value pairs for fast data retrieval -> Option B

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMap = fast key to value lookup [OK]

Common Mistakes:

• Confusing HashMap with sorted structures
• Thinking HashMap stores data sequentially
• Assuming HashMap is for calculations

2. Which of the following is the correct way to declare a simple HashMap in C# using generics?

easy

A. Hashtable map = new Hashtable();

B. HashMap map = new HashMap();

C. Map map = new Map();

D. Dictionary map = new Dictionary();

Solution

1. Step 1: Recall C# standard HashMap equivalent

   In C#, Dictionary<K,V> is the built-in generic collection similar to HashMap.

2. Step 2: Check syntax correctness

   Dictionary map = new Dictionary(); correctly declares a Dictionary with int keys and string values.

3. Final Answer:

   Dictionary map = new Dictionary(); -> Option D

4. Quick Check:

   C# HashMap = Dictionary [OK]

Hint: Use Dictionary for HashMap in C# [OK]

Common Mistakes:

• Using non-existent HashMap class in C#
• Confusing Hashtable with generic Dictionary
• Wrong generic syntax

3. Consider this simple HashMap implementation snippet in C#:

class SimpleHashMap {
  private int[] keys = new int[5];
  private string[] values = new string[5];

  public void Put(int key, string value) {
    int index = key % 5;
    keys[index] = key;
    values[index] = value;
  }

  public string Get(int key) {
    int index = key % 5;
    if (keys[index] == key) return values[index];
    return null;
  }
}

SimpleHashMap map = new SimpleHashMap();
map.Put(1, "One");
map.Put(6, "Six");
string result = map.Get(1);

What is the value of result after this code runs?

medium

A. null

B. "One"

C. "Six"

D. Runtime error

Solution

1. Step 1: Calculate index for key 1

   Index = 1 % 5 = 1. So keys[1] = 1, values[1] = "One".

2. Step 2: Calculate index for key 6

   Index = 6 % 5 = 1. This overwrites keys[1] = 6, values[1] = "Six".

3. Step 3: Get value for key 1

   Index = 1 % 5 = 1. keys[1] is now 6, not 1, so Get returns null.

4. Final Answer:

   null -> Option A

5. Quick Check:

   Collision overwrites key 1, so Get(1) = null [OK]

Hint: Check key collision and overwrite in simple hash arrays [OK]

Common Mistakes:

• Ignoring key collision overwrite
• Assuming values are stored separately
• Expecting 'One' despite collision

4. Identify the bug in this simple HashMap Put method and choose the correct fix:

public void Put(int key, string value) {
  int index = key % 5;
  if (keys[index] != key) {
    keys[index] = key;
    values[index] = value;
  }
}

medium

A. Change modulus to key % 10 for bigger array

B. Remove the if check to always overwrite key and value

C. Add linear probing to handle collisions

D. Use keys[index] == key instead of != in if condition

Solution

1. Step 1: Understand current behavior

   The if (keys[index] != key) inserts only if the existing key differs: overwrites on collisions (data loss for previous keys) and skips updates for matching keys.

2. Step 2: Identify collision handling

   Without collision handling like linear probing, new keys that hash to occupied slots overwrite existing data.

3. Step 3: Fix by adding linear probing

   Linear probing searches next slots to find an empty or matching key slot, preventing overwrites.

4. Final Answer:

   Add linear probing to handle collisions -> Option C

5. Quick Check:

   Collision fix = linear probing [OK]

Hint: Handle collisions with probing, not just overwrite [OK]

Common Mistakes:

• Removing if causes overwrites
• Changing modulus without resizing array
• Wrong if condition logic

5. You want to implement a HashMap from scratch in C# that supports storing string keys and integer values. Which approach correctly handles collisions and allows retrieval of values?

class MyHashMap {
  private List>[] buckets;
  private int size = 10;

  public MyHashMap() {
    buckets = new List>[size];
    for (int i = 0; i < size; i++) buckets[i] = new List>();
  }

  private int GetBucketIndex(string key) {
    return Math.Abs(key.GetHashCode()) % size;
  }

  public void Put(string key, int value) {
    int index = GetBucketIndex(key);
    var bucket = buckets[index];
    for (int i = 0; i < bucket.Count; i++) {
      if (bucket[i].Key == key) {
        bucket[i] = new KeyValuePair(key, value);
        return;
      }
    }
    bucket.Add(new KeyValuePair(key, value));
  }

  public int? Get(string key) {
    int index = GetBucketIndex(key);
    var bucket = buckets[index];
    foreach (var kvp in bucket) {
      if (kvp.Key == key) return kvp.Value;
    }
    return null;
  }
}

MyHashMap map = new MyHashMap();
map.Put("apple", 5);
map.Put("banana", 3);
map.Put("apple", 10);
int? val = map.Get("apple");

What is the value of val after this code runs?

hard

A. 10

B. 5

C. 3

D. null

Solution

1. Step 1: Understand Put method behavior

   When inserting "apple" the second time, the code finds the existing key and updates its value to 10.

2. Step 2: Understand Get method behavior

   Get("apple") searches the bucket and returns the updated value 10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Updated value for "apple" = 10 [OK]

Hint: Update existing key value, else add new pair [OK]

Common Mistakes:

• Returning old value instead of updated
• Ignoring collision handling with buckets
• Returning null if key exists