HashMap Implementation from Scratch in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the internal storage array for the HashMap.

DSA Typescript

private buckets: Array<Array<[string, any]>> = new Array([1]);

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

A0

B16

C[]

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using an empty array literal instead of a fixed size array.

Setting size to 0 or null which causes errors.

The internal storage is an array with a fixed size, commonly 16 buckets initially.

2fill in blank

medium

Complete the code to compute the hash index for a given key.

DSA Typescript

const index = this.hash(key) [1] this.buckets.length;

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

A+

B*

C%

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or multiplication which can exceed array length.

Using subtraction which can cause negative indices.

The modulo operator (%) is used to ensure the hash fits within the bucket array size.

3fill in blank

hard

Fix the error in the put method to correctly update an existing key's value.

DSA Typescript

for (let i = 0; i < bucket.length; i++) {
  if (bucket[i][0] === key) {
    bucket[i][[1]] = value;
    return;
  }
}

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

A1

B0

C2

Dkey

Attempts:

3 left

💡 Hint

Common Mistakes

Trying to assign value to index 0 which is the key.

Using an invalid index like 2.

The value is stored at index 1 in the key-value pair array [key, value].

4fill in blank

hard

Fill both blanks to correctly retrieve a value by key from the HashMap.

DSA Typescript

const bucket = this.buckets[[1]];
if (!bucket) return undefined;
for (const pair of bucket) {
  if (pair[0] === [2]) return pair[1];
}
return undefined;

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

Aindex

Bkey

Cvalue

Dthis.key

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'value' or 'this.key' instead of the key parameter.

Using wrong variable for bucket index.

We use the computed index to get the bucket and the key to compare with pairs.

5fill in blank

hard

Fill all three blanks to complete the hash function that sums character codes.

DSA Typescript

hash(key: string): number {
  let hash = 0;
  for (let i = 0; i < [1]; i++) {
    hash += key.charCodeAt([2]);
  }
  return hash [3] 31;
}

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

Akey.length

Bi

C%

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong loop limit or index variable.

Using multiplication instead of modulo for limiting hash.

The loop runs over the key length, uses index i for charCodeAt, and modulo 31 to limit hash size.

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