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 medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Databricks.

What role is this question designed for?

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

Implement lazy array and KV store | Databricks Coding Question

Quick Overview

This question evaluates understanding of lazy evaluation and functional transformation chaining for a LazyArray alongside in-memory data structure design and stateful API behavior for a key-value store with hit counting, within the Coding & Algorithms domain covering functional programming, data structures, and API design.

Implement lazy array and KV store

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are asked two coding problems in the same interview round: 1. **Implement a lazy array abstraction** - Create a `LazyArray<T>` that wraps an input list. - It should support chained transformations such as `map` and `filter`. - Intermediate transformations must be recorded but **not executed immediately**. - Computation should happen only when a terminal operation is called, such as `toList()`, `reduce()`, or `get(index)`. - In addition to implementation, explain how you would test that the class is truly lazy and does not accidentally evaluate work early. 2. **Implement an in-memory key-value store with hit counting** - Support `put(key, value)`, `get(key)`, `delete(key)`, and `getHitCount(key)`. - Each successful `get` on an existing key should increment that key's hit counter. - Define the expected behavior for missing keys and for overwriting existing values. - Aim for clear APIs and efficient basic operations.

Quick Answer: This question evaluates understanding of lazy evaluation and functional transformation chaining for a LazyArray alongside in-memory data structure design and stateful API behavior for a key-value store with hit counting, within the Coding & Algorithms domain covering functional programming, data structures, and API design.

Part 1: Lazy Array Query Processor

You are given an initial integer array `nums` and a list of operations that simulate a lazy array abstraction. Transformation operations are recorded but must not be executed immediately: - `('map_add', x)`: add `x` to each element - `('map_mul', x)`: multiply each element by `x` - `('filter_gt', x)`: keep elements greater than `x` - `('filter_lt', x)`: keep elements less than `x` - `('filter_even',)`: keep even elements - `('filter_odd',)`: keep odd elements Terminal operations trigger evaluation of the full current pipeline: - `('to_list',)`: materialize the current lazy array as a list - `('reduce_sum',)`: return the sum of the current lazy array - `('get', i)`: return the element at 0-based index `i` in the current lazy array, or `None` if it does not exist Process the operations in order. Transformations remain part of the pipeline after a terminal operation; they are not cleared. Return the results of all terminal operations in order. A genuinely lazy design stores pending transformations and only iterates the base array when a terminal operation is called. In a class-based version, one good way to test laziness is to use a transform with a side effect or counter and verify that the counter stays unchanged until `to_list`, `reduce_sum`, or `get` is executed.

Constraints

0 <= len(nums) <= 2000
0 <= len(operations) <= 2000
All operation names are valid and use the formats described above
Array values and operation parameters fit in 32-bit signed integers
`get` indices are integers; if the requested index is out of range, return `None`

Examples

Input: ([1, 2, 3, 4], [('map_mul', 2), ('filter_gt', 4), ('to_list',)])

Expected Output: [[6, 8]]

Explanation: The pipeline is `*2` then `>4`, so the final list is `[6, 8]`.

Input: ([1, 2, 3, 4, 5], [('filter_odd',), ('get', 1), ('map_add', 10), ('reduce_sum',), ('to_list',)])

Expected Output: [3, 39, [11, 13, 15]]

Explanation: After `filter_odd`, the lazy array is `[1, 3, 5]`, so `get(1)` is `3`. Then `map_add 10` makes it `[11, 13, 15]`, whose sum is `39`.

Input: ([], [('map_add', 5), ('to_list',), ('reduce_sum',), ('get', 0)])

Expected Output: [[], 0, None]

Explanation: Edge case: an empty input stays empty under all transformations.

Input: ([2, 4, 6], [('filter_odd',), ('get', 0), ('to_list',)])

Expected Output: [None, []]

Explanation: Filtering odd numbers removes every element, so index 0 does not exist.

Hints

Do not update the array immediately for `map` and `filter`. Store the operations in a list first.
When a terminal operation arrives, build a generator/iterator pipeline from the original array. For `get(i)`, stop as soon as you find the i-th surviving element.

Part 2: In-Memory Key-Value Store with Hit Counts

You are given a list of operations to execute on an in-memory key-value store. Supported operations: - `('put', key, value)`: insert a new key or overwrite an existing key with `value`. If the key already exists, only the value changes; its current hit count is preserved. - `('get', key)`: if the key exists, return its value and increment its hit count by 1. If it does not exist, return `None` and do not create the key. - `('delete', key)`: remove the key and its hit count. Return `True` if the key existed and was deleted, otherwise `False`. - `('getHitCount', key)`: return the current hit count for the key, or `None` if the key does not exist. Return a list of outputs for every `get`, `delete`, and `getHitCount` operation, in order. `put` does not produce output. If a key is deleted and later inserted again with `put`, it is treated as a new key and its hit count starts at 0.

Constraints

0 <= len(operations) <= 100000
Keys are strings of length 1 to 50
Values fit in 32-bit signed integers
All operations are valid and are one of `put`, `get`, `delete`, or `getHitCount`
Average-time efficiency is expected for each basic operation

Examples

Input: ([('put', 'a', 10), ('get', 'a'), ('get', 'a'), ('getHitCount', 'a')],)

Expected Output: [10, 10, 2]

Explanation: Two successful `get` operations increment the hit count from 0 to 2.

Input: ([('get', 'x'), ('delete', 'x'), ('getHitCount', 'x')],)

Expected Output: [None, False, None]

Explanation: Edge case: missing keys return `None` for `get` and `getHitCount`, and `False` for `delete`.

Input: ([('put', 'a', 1), ('get', 'a'), ('put', 'a', 99), ('getHitCount', 'a'), ('get', 'a'), ('getHitCount', 'a')],)

Expected Output: [1, 1, 99, 2]

Explanation: Overwriting changes the stored value to `99` but preserves the existing hit count.

Input: ([('put', 'k', 5), ('get', 'k'), ('delete', 'k'), ('getHitCount', 'k'), ('put', 'k', 7), ('getHitCount', 'k'), ('get', 'k'), ('getHitCount', 'k')],)

Expected Output: [5, True, None, 0, 7, 1]

Explanation: After deletion, reinserting `k` starts a new hit count at 0.

Input: ([],)

Expected Output: []

Explanation: Edge case: no operations produce no output.

Hints

A dictionary is the natural choice for the main store. You can keep another dictionary for hit counts.
Decide the overwrite behavior first. Here, overwriting updates the value but keeps the hit count for that key unchanged.

Quick Overview