Implement in-memory database insert and delete operations
Company: OpenAI
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Design and implement a simple **in-memory database** (key-value store) that supports the following operations:
- `insert(key, value)`: Insert a key-value pair into the database. If the key already exists, update its value.
- `get(key)`: Return the value associated with the key, or indicate that the key does not exist.
- `delete(key)`: Remove the key and its associated value from the database if it exists.
Assume:
- Keys are strings.
- Values are arbitrary strings (or integers; choose one and be consistent).
- The database is entirely in memory; you do not need to persist data to disk.
- You do not need to handle concurrency/multi-threading.
Requirements:
- Design the **data structures** used to support these operations.
- Aim for **average O(1) time** for `insert`, `get`, and `delete`.
- Explain the time and space complexity of your approach.
Then, write code to implement these operations in the programming language of your choice.
Quick Answer: This question evaluates understanding of data structures and algorithmic complexity in the context of designing a key-value in-memory database, and it falls under the Coding & Algorithms domain for a Machine Learning Engineer role while focusing on practical implementation skills.
You are given a sequence of operations to perform on a simple in-memory key-value database. Keys are strings and values are integers.
Support these operations:
- ('insert', key, value): Insert the key-value pair into the database. If the key already exists, update its value.
- ('get', key): Return the value associated with the key, or None if the key does not exist.
- ('delete', key): Remove the key from the database if it exists.
Write a function solution(operations) that processes the operations in order and returns a list containing the result of every 'get' and 'delete' operation, in the same order they appear.
Rules for the returned list:
- For 'get', append the stored value, or None if the key is missing.
- For 'delete', append True if a key was removed, otherwise False.
- 'insert' does not append anything to the output.
Your implementation should aim for average O(1) time per insert, get, and delete operation.
Constraints
- 0 <= len(operations) <= 100000
- Each operation is one of ('insert', key, value), ('get', key), or ('delete', key)
- Each key is a non-empty string with length at most 50
- Each value is an integer in the range [-10^9, 10^9]
- Use a data structure with average O(1) insert, get, and delete
Examples
Input: [('insert', 'apple', 3), ('get', 'apple'), ('delete', 'apple'), ('get', 'apple')]
Expected Output: [3, True, None]
Explanation: After inserting 'apple' with value 3, get returns 3. Deleting 'apple' succeeds, so append True. A later get finds no such key, so append None.
Input: [('insert', 'x', 1), ('insert', 'x', 5), ('get', 'x'), ('delete', 'y'), ('get', 'y')]
Expected Output: [5, False, None]
Explanation: The second insert updates 'x' from 1 to 5. Getting 'x' returns 5. Deleting missing key 'y' returns False, and getting 'y' returns None.
Hints
- A hash map (Python dictionary) supports average O(1) insert, lookup, and deletion by key.
- Process the operations from left to right and only append results for 'get' and 'delete'.