How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Goldman Sachs during technical interviews.

Implement an Integer Hash Map | Goldman Sachs Coding Question

Implement an Integer Hash Map

Company: Goldman Sachs

Role: Software Engineer

Category: Coding & Algorithms

Interview Round: Take-home Project

Design a data structure `MyHashMap` that stores integer keys and integer values without using any built-in hash table library. Implement the following operations: - `put(key, value)`: Insert the key-value pair into the map. If the key already exists, update its value. - `get(key)`: Return the value associated with the key. If the key does not exist, return `-1`. - `remove(key)`: Remove the key and its value if the key exists. Requirements: - Keys and values are non-negative integers. - The implementation should support repeated updates to the same key. - Each operation should be efficient on average. - Do not use built-in map, dictionary, or hash table implementations. Example: - `put(1, 10)` - `put(2, 20)` - `get(1)` returns `10` - `get(3)` returns `-1` - `put(2, 30)` - `get(2)` returns `30` - `remove(2)` - `get(2)` returns `-1`

Quick Answer: This question evaluates understanding of hashing principles, collision handling, and data structure design for integer key-value storage, testing algorithmic complexity and API correctness within the Coding & Algorithms domain.

Design a data structure `MyHashMap` that stores non-negative integer keys and non-negative integer values without using any built-in map, dictionary, or hash table library. Implement these operations: - `put(key, value)`: Insert the key-value pair into the map. If the key already exists, update its value. - `get(key)`: Return the value associated with the key. If the key does not exist, return `-1`. - `remove(key)`: Remove the key and its value if the key exists. Because this platform evaluates a single function, implement `solution(operations, arguments)` that simulates one `MyHashMap` instance. - `operations[i]` is one of: `'MyHashMap'`, `'put'`, `'get'`, `'remove'` - `arguments[i]` contains the arguments for that operation - The first operation is always `'MyHashMap'` with an empty argument list Return a list of results aligned with the operations: - Return `None` for `'MyHashMap'`, `'put'`, and `'remove'` - Return the integer result for each `'get'` operation

Constraints

1 <= len(operations) <= 100000
operations[0] == 'MyHashMap'
0 <= key, value <= 10^9
Do not use built-in map, dictionary, or hash table implementations
Aim for average O(1) time per operation

Examples

Input: (['MyHashMap', 'put', 'put', 'get', 'get', 'put', 'get', 'remove', 'get'], [[], [1, 10], [2, 20], [1], [3], [2, 30], [2], [2], [2]])

Expected Output: [None, None, None, 10, -1, None, 30, None, -1]

Explanation: Insert two keys, read an existing key and a missing key, update key 2, then remove it.

Input: (['MyHashMap', 'get', 'remove', 'put', 'get'], [[], [42], [42], [42, 0], [42]])

Expected Output: [None, -1, None, None, 0]

Explanation: Getting or removing a missing key should not fail. After inserting key 42 with value 0, `get(42)` returns 0.

Input: (['MyHashMap', 'put', 'put', 'put', 'get', 'remove', 'get'], [[], [0, 0], [0, 5], [0, 7], [0], [0], [0]])

Expected Output: [None, None, None, None, 7, None, -1]

Explanation: The same key is updated multiple times. The latest value is returned, and after removal the key is missing.

Input: (['MyHashMap', 'put', 'put', 'get', 'get', 'remove', 'get', 'get'], [[], [1, 100], [2070, 200], [1], [2070], [1], [1], [2070]])

Expected Output: [None, None, None, 100, 200, None, -1, 200]

Explanation: These keys collide under a common modulo-based hash setup, so this checks collision handling with separate chaining.

Hints

Map each key to a bucket index using a hash function such as `key % bucket_count`.
If multiple keys land in the same bucket, store all pairs in that bucket and scan only that small bucket to find or update a key.

Quick Overview

This question evaluates understanding of hashing principles, collision handling, and data structure design for integer key-value storage, testing algorithmic complexity and API correctness within the Coding & Algorithms domain.