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 difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at OpenAI during technical interviews.

Implement in-memory database insert and delete operations

Quick Overview

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.

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.

Input: []

Expected Output: []

Explanation: No operations means no output. This checks the empty-input edge case.

Input: [('get', 'missing')]

Expected Output: [None]

Explanation: The key does not exist, so get returns None.

Input: [('insert', 'n', -7), ('insert', 'm', 2), ('delete', 'n'), ('get', 'n'), ('get', 'm'), ('delete', 'n')]

Expected Output: [True, None, 2, False]

Explanation: Deleting 'n' the first time succeeds. After that, get('n') returns None, get('m') returns 2, and deleting 'n' again fails.

Solution

def solution(operations):
    db = {}
    result = []

    for op in operations:
        action = op[0]

        if action == 'insert':
            _, key, value = op
            db[key] = value
        elif action == 'get':
            _, key = op
            result.append(db.get(key))
        elif action == 'delete':
            _, key = op
            if key in db:
                del db[key]
                result.append(True)
            else:
                result.append(False)
        else:
            raise ValueError('Unknown operation')

    return result

Time complexity: O(q) average, where q is the number of operations. Space complexity: O(k + r), where k is the number of keys stored and r is the number of returned results.

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'.

Quick Overview