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

What role is this question designed for?

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

Implement Python LRU cache with varargs

Quick Overview

This question evaluates a candidate's ability to implement an LRU caching mechanism in Python, including decorator design, argument canonicalization for positional args, *args, and **kwargs, handling unhashable inputs, eviction semantics, cache metadata operations (clear, cache_info), and JSON-based persistence and versioning.

Company: HubSpot

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Implement an LRU cache in Python as a decorator cache(maxsize) that memoizes a target function's results. Must support positional args, *args, and **kwargs so that semantically equivalent calls (e.g., f(1, b= 2) and f(1, 2)) map to the same key. Handle unhashable arguments by canonicalizing them into a deterministic, hashable representation. Provide operations: eviction by least recently used, clear(), and cache_info(). Follow-up: add persistence methods save(filepath) and load(filepath) that serialize the cache to JSON (no pickle). Define how you encode keys and values, and how you handle non-JSON-serializable return values and versioning.

Quick Answer: This question evaluates a candidate's ability to implement an LRU caching mechanism in Python, including decorator design, argument canonicalization for positional args, *args, and **kwargs, handling unhashable inputs, eviction semantics, cache metadata operations (clear, cache_info), and JSON-based persistence and versioning.

Implement the core of a Python-style `cache(maxsize)` memoization decorator as a pure simulation. You are given: - `maxsize`: the maximum number of distinct cached call-keys to retain (or `None` for unbounded). - `params`: the ordered list of the target function's positional parameter names, e.g. `['a', 'b']`. - `calls`: a list of calls, each a dict with optional `args` (a list of positional argument values) and `kwargs` (a dict of keyword argument values). For each call, build a cache key by **binding** positional `args` to `params` by position and merging in `kwargs`, so that semantically-equivalent invocations map to the same key — e.g. with `params = ['a','b']`, the calls `{'args':[1,2]}` and `{'args':[1],'kwargs':{'b':2}}` must collide. Any positional argument beyond `len(params)` goes into an order-sensitive `*args` bucket. Because argument values may be **unhashable** (lists, dicts, sets), canonicalize each value into a deterministic, hashable representation before keying. Maintain an LRU cache of at most `maxsize` keys. A call whose key is already present is a **hit** (and refreshes recency); a new key is a **miss** (inserted as most-recently-used, evicting the least-recently-used key if the cache would exceed `maxsize`). When `maxsize` is `None`, never evict. Return the list of `'hit'` / `'miss'` strings, one per call in order.

Constraints

0 <= len(calls) <= 10^4
0 <= len(params) <= 50
maxsize is a positive integer or None (unbounded)
Argument values may be ints, strings, bools, or nested lists/dicts/sets (possibly unhashable)
Binding rule: positional args fill params by index; extras form an order-sensitive *args bucket; kwargs override/add by name

Examples

Input: (2, ['a', 'b'], [{'args': [1, 2]}, {'args': [1], 'kwargs': {'b': 2}}])

Expected Output: ['miss', 'hit']

Explanation: Binding positional [1,2] to params [a,b] gives {a:1,b:2}; the second call {a:1, b:2} binds to the same mapping, so it hits.

Input: (2, ['a', 'b'], [{'kwargs': {'b': 2, 'a': 1}}, {'args': [1, 2]}])

Expected Output: ['miss', 'hit']

Explanation: Keyword order does not matter: {b:2,a:1} canonicalizes to the same sorted key as positional [1,2].

Input: (2, ['x'], [{'args': [1]}, {'args': [2]}, {'args': [3]}, {'args': [1]}])

Expected Output: ['miss', 'miss', 'miss', 'miss']

Explanation: With maxsize 2, after caching 1 and 2, inserting 3 evicts 1 (LRU); the later call 1 is therefore a miss.

Input: (2, ['x'], [{'args': [1]}, {'args': [2]}, {'args': [1]}, {'args': [3]}, {'args': [2]}])

Expected Output: ['miss', 'miss', 'hit', 'miss', 'miss']

Explanation: 1,2 cached; 1 hits and becomes MRU; 3 evicts the LRU (2); final 2 is a miss since it was evicted.

Input: (3, ['data'], [{'args': [[1, 2, 3]]}, {'args': [[1, 2, 3]]}, {'args': [{'k': 1}]}, {'args': [{'k': 1}]}])

Expected Output: ['miss', 'hit', 'miss', 'hit']

Explanation: Unhashable list and dict arguments are canonicalized deterministically, so identical structures hit on repeat.

Input: (1, ['x'], [{'args': [1]}, {'args': [2]}, {'args': [1]}])

Expected Output: ['miss', 'miss', 'miss']

Explanation: maxsize 1 holds only the most recent key; every distinct call evicts the prior one, so nothing ever hits here.

Input: (2, ['a'], [])

Expected Output: []

Explanation: No calls yields an empty result.

Input: (None, ['x'], [{'args': [1]}, {'args': [2]}, {'args': [3]}, {'args': [1]}])

Expected Output: ['miss', 'miss', 'miss', 'hit']

Explanation: Unbounded cache (maxsize None) never evicts, so the repeated call 1 hits.

Hints

Two calls are 'the same' only after you bind positional args to parameter names — normalize every call into a single name->value mapping before hashing.
Lists, dicts and sets are unhashable. Recursively convert them into nested tuples (sort dict items and set elements) so the key is deterministic regardless of insertion order.
An OrderedDict gives you O(1) LRU: move_to_end on a hit, and popitem(last=False) to drop the least-recently-used key when you exceed maxsize.
Tag primitives with their type in the key so values like 1 and True (or 1 and '1') don't accidentally collide.

Quick Overview