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.

Implement an Integer Hash Map

Company: Goldman Sachs

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

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.

Hints

  1. Map each key to a bucket index using a hash function such as `key % bucket_count`.
  2. 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.

Loading coding console...