HashMap Implementation from Scratch in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this HashMap put and get operations?

Consider a simple HashMap implementation with separate chaining. What will be printed after these operations?

DSA Typescript

class HashMap {
  private buckets: Array<Array<[string, number]>>;
  private size: number;

  constructor(size: number = 5) {
    this.size = size;
    this.buckets = Array.from({ length: size }, () => []);
  }

  private hash(key: string): number {
    let hash = 0;
    for (let char of key) {
      hash += char.charCodeAt(0);
    }
    return hash % this.size;
  }

  put(key: string, value: number): void {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value;
        return;
      }
    }
    bucket.push([key, value]);
  }

  get(key: string): number | undefined {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    for (let [k, v] of bucket) {
      if (k === key) return v;
    }
    return undefined;
  }
}

const map = new HashMap();
map.put("apple", 10);
map.put("banana", 20);
map.put("grape", 30);
console.log(map.get("banana"));
console.log(map.get("apple"));
console.log(map.get("orange"));

A 20\nundefined\n10

B undefined\n10\n20

C 10\n20\nundefined

D 20\n10\nundefined

💡 Hint

Check how the hash function distributes keys and how get returns values.

The keys "banana" and "apple" are stored with values 20 and 10 respectively. The get method returns the value for the key if found, otherwise undefined. "orange" was never added, so it returns undefined.

🧠 Conceptual

intermediate

How does separate chaining handle collisions in a HashMap?

In a HashMap using separate chaining, what happens when two keys hash to the same bucket?

A Both key-value pairs are stored in a list at that bucket.

B The second key-value pair replaces the first one in the bucket.

C The HashMap throws an error and stops execution.

D The HashMap resizes immediately to avoid collision.

💡 Hint

Think about how multiple items can be stored in one place.

Separate chaining stores all key-value pairs that hash to the same bucket in a list (or chain) at that bucket. This allows multiple entries to coexist without overwriting.

🔧 Debug

advanced

Why does this HashMap implementation fail to update existing keys?

Look at this put method. Why does it fail to update the value if the key already exists?

DSA Typescript

put(key: string, value: number): void {
  const index = this.hash(key);
  const bucket = this.buckets[index];
  for (let pair of bucket) {
    if (pair[0] === key) {
      pair[1] = value;
      return;
    }
  }
  bucket.push([key, value]);
}

A It throws a runtime error because pair is undefined.

B It never adds new pairs to the bucket.

C It always adds a new pair even if the key exists, causing duplicates.

D It clears the bucket before adding new pairs.

💡 Hint

Check if the function stops after updating an existing key.

The method updates the value if the key exists but does not stop the loop or return, so it still adds a new pair at the end, causing duplicates.

📝 Syntax

advanced

Which option fixes the syntax error in this HashMap get method?

This get method has a syntax error. Which option fixes it correctly?

DSA Typescript

get(key: string): number | undefined {
  const index = this.hash(key);
  const bucket = this.buckets[index];
  for (let [k, v] of bucket) {
    if (k === key) return v;
  }
  return undefined;
}

A Add colon after method name: get(key: string): number | undefined:

B Add missing semicolons after statements.

C Change for loop to for (let k, v of bucket) without brackets.

D Replace return undefined with return null.

💡 Hint

TypeScript allows optional semicolons but missing them can cause issues in some cases.

Adding semicolons after statements fixes the syntax error. The other options either introduce errors or change behavior.

🚀 Application

expert

What is the final state of buckets after these put operations?

Given a HashMap with size 3 and this hash function, what is the state of buckets after inserting keys "cat", "dog", "bird", "cow" with values 1, 2, 3, 4?

DSA Typescript

class HashMap {
  buckets: Array<Array<[string, number]>>;
  size: number;

  constructor(size: number = 3) {
    this.size = size;
    this.buckets = Array.from({ length: size }, () => []);
  }

  hash(key: string): number {
    let sum = 0;
    for (let c of key) {
      sum += c.charCodeAt(0);
    }
    return sum % this.size;
  }

  put(key: string, value: number): void {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value;
        return;
      }
    }
    bucket.push([key, value]);
  }
}

const map = new HashMap(3);
map.put("cat", 1);
map.put("dog", 2);
map.put("bird", 3);
map.put("cow", 4);
// What is map.buckets now?

A [[['cat', 1], ['bird', 3]], [], [['dog', 2], ['cow', 4]]]

B [[['cat', 1], ['cow', 4]], [['dog', 2]], [['bird', 3]]]

C [[['bird', 3]], [['dog', 2]], [['cat', 1], ['cow', 4]]]

D [[['cat', 1]], [['dog', 2], ['cow', 4]], [['bird', 3]]]

💡 Hint

Calculate the hash index for each key and group them accordingly.

Calculate sum of char codes mod 3 for each key:
"cat": 99+97+116=312 %3=0
"dog": 100+111+103=314 %3=2
"bird": 98+105+114+100=417 %3=0
"cow": 99+111+119=329 %3=2
Then group keys by bucket index.

Practice

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

easy

A. To store data in a sorted order

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

C. To perform mathematical calculations

D. To store data sequentially like an array

Solution

1. Step 1: Understand HashMap functionality

   A HashMap stores data as key-value pairs, allowing quick access by key.

2. Step 2: Compare with other data structures

   Unlike arrays or lists, 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 = key-value pairs for quick lookup [OK]

Common Mistakes:

• Thinking HashMap stores data in order
• Confusing HashMap with arrays
• Assuming HashMap is for calculations

2. Which of the following is the correct way to declare a simple HashMap class property in TypeScript?

easy

A. private map: {[key: string]: any} = {};

B. map = new Map();

C. let map = [];

D. const map: Map = {};

Solution

1. Step 1: Identify TypeScript syntax for object property

   Declaring a private property with type {[key: string]: any} initializes an object for key-value storage.

2. Step 2: Check other options for correctness

   map = new Map(); uses built-in Map, not a plain object; C is an array; D has wrong Map type usage.

3. Final Answer:

   private map: {[key: string]: any} = {}; -> Option A

4. Quick Check:

   TypeScript object property syntax = private map: {[key: string]: any} = {}; [OK]

Hint: Use object type {[key: string]: any} for HashMap storage [OK]

Common Mistakes:

• Using array instead of object for map
• Incorrect Map type declaration
• Confusing built-in Map with plain object

3. What will be the output of this TypeScript code snippet implementing a simple HashMap?

class SimpleHashMap {
  private map: {[key: string]: string} = {};
  set(key: string, value: string) {
    this.map[key] = value;
  }
  get(key: string) {
    return this.map[key] || null;
  }
}
const h = new SimpleHashMap();
h.set('a', 'apple');
h.set('b', 'banana');
console.log(h.get('a'));
console.log(h.get('c'));

medium

A. "apple" followed by null

B. "apple" followed by undefined

C. undefined followed by null

D. Error at runtime

Solution

1. Step 1: Trace set method calls

   Keys 'a' and 'b' are set with values 'apple' and 'banana' respectively in the map object.

2. Step 2: Trace get method calls

   Getting 'a' returns 'apple'; getting 'c' returns undefined, so || null returns null.

3. Final Answer:

   "apple" followed by null -> Option A

4. Quick Check:

   Existing key returns value, missing key returns null [OK]

Hint: Missing keys return null due to || null fallback [OK]

Common Mistakes:

• Expecting undefined instead of null for missing keys
• Confusing set and get method effects
• Assuming runtime error on missing key

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

class BuggyHashMap {
  private map: {[key: string]: number} = {};
  set(key: string, value: number) {
    this.map[key] = value;
  }
  get(key: string): number {
    return this.map[key];
  }
}
const h = new BuggyHashMap();
h.set('x', 10);
console.log(h.get('y'));

medium

A. map should be an array instead of object

B. set method should check if key exists before setting

C. get should return number | null and handle missing keys

D. No bug, code works fine

Solution

1. Step 1: Analyze get method return type

   get returns number but missing keys return undefined, causing type mismatch.

2. Step 2: Fix get method to handle missing keys

   Change return type to number | null and return null if key missing to avoid undefined.

3. Final Answer:

   get should return number | null and handle missing keys -> Option C

4. Quick Check:

   Handle missing keys in get method [OK]

Hint: Always handle missing keys in get method return type [OK]

Common Mistakes:

• Ignoring undefined return for missing keys
• Changing map to array incorrectly
• Thinking set method needs key existence check

5. You want to implement a HashMap from scratch in TypeScript that handles collisions using chaining (array of entries). Which approach correctly adds a new key-value pair to the map?

hard

A. Store keys in an array and values in a separate array without hashing

B. Compute hash, overwrite bucket with new entry ignoring existing keys

C. Use a single array for all entries without hashing

D. Compute hash, check bucket array; if key exists update value, else push new entry

Solution

1. Step 1: Understand collision handling by chaining

   Chaining stores multiple entries in a bucket array; new entries are added or updated if key exists.

2. Step 2: Analyze options for correct collision handling

   Compute hash, check bucket array; if key exists update value, else push new entry correctly checks bucket, updates existing key or adds new entry; others ignore collisions or do not hash.

3. Final Answer:

   Compute hash, check bucket array; if key exists update value, else push new entry -> Option D

4. Quick Check:

   Chaining = bucket array with update or add [OK]

Hint: Check bucket for key, update or add entry to handle collisions [OK]

Common Mistakes:

• Overwriting bucket ignoring existing keys
• Not using hashing for bucket selection
• Storing keys and values separately without hashing