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 Technical Screen rounds at Adyen.

What role is this question designed for?

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

Implement LRU and target-sum combinations

Quick Overview

Implement LRU and target-sum combinations evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Adyen

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Design and implement the following: 1) An in-memory cache with Least Recently Used (LRU) eviction supporting get(key) and put(key, value) in O( 1). If implementing from scratch, describe the hash map + doubly linked list approach, including how sentinel dummy head/tail nodes simplify edge cases, and why Java's LinkedList is not appropriate. Compare this to using LinkedHashMap and explain trade-offs. Analyze time and space complexity. 2) Given a list of candidate transfer amounts and a target amount, return all unique combinations of candidates that sum to the target (each candidate may be used unlimited times). Explain your backtracking approach, pruning rules to reduce the search space, how you avoid duplicate combinations, and the time/space complexity. Justify why backtracking is appropriate here and briefly compare with dynamic programming.

Quick Answer: Implement LRU and target-sum combinations evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

LRU Cache (get / put in O(1))

Design and implement an in-memory cache with Least Recently Used (LRU) eviction. The cache is constructed with a positive integer `capacity` and supports two operations in O(1) average time: - `get(key)` — return the value of `key` if present, otherwise return `-1`. Accessing a key marks it as the most recently used. - `put(key, value)` — insert or update `key`. If the cache is at capacity, evict the least recently used key before inserting. Updating an existing key also marks it as most recently used. The classic approach pairs a hash map (key → node) with a doubly linked list ordered by recency. Sentinel dummy head and tail nodes remove all null-pointer edge cases when inserting/removing at the ends. Java's `LinkedList` (singly-tracked traversal API) is inappropriate because removing an arbitrary node is O(n); `LinkedHashMap` with `accessOrder=true` and an overridden `removeEldestEntry` gives the same behavior for free but hides the mechanics. This challenge implements the map + doubly-linked-list version from scratch. You are given a list of `operations` and a parallel list of `args`. The first operation is always `"LRUCache"` with `args[0] = [capacity]`. Subsequent operations are `"get"` (`[key]`) or `"put"` (`[key, value]`). Return a list whose i-th element is the result of the i-th operation: `null` for the constructor and for `put`, the returned value for `get`.

Constraints

1 <= capacity <= 10^4
0 <= number of operations <= 2 * 10^5
The first operation is always the 'LRUCache' constructor.
Keys and values are integers; get on an absent key returns -1.

Examples

Input: (['LRUCache','put','put','get','put','get','put','get','get','get'], [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]])

Expected Output: [None, None, None, 1, None, -1, None, -1, 3, 4]

Explanation: Capacity 2. put(1,1),put(2,2); get(1)=1 (1 now MRU); put(3,3) evicts key 2; get(2)=-1; put(4,4) evicts key 1; get(1)=-1; get(3)=3; get(4)=4.

Input: (['LRUCache','put','get','get'], [[1],[2,1],[2],[3]])

Expected Output: [None, None, 1, -1]

Explanation: Capacity 1. put(2,1); get(2)=1; get(3)=-1 (absent key).

Input: (['LRUCache','get'], [[2],[1]])

Expected Output: [None, -1]

Explanation: Edge: get on an empty cache returns -1.

Input: (['LRUCache','put','put','get','get'], [[2],[1,10],[1,20],[1],[2]])

Expected Output: [None, None, None, 20, -1]

Explanation: Edge: overwriting an existing key updates the value (1->20) without evicting; get(1)=20, get(2)=-1 (never inserted).

Hints

Pair a hash map (key -> node) with a doubly linked list ordered most-recent-at-front. The map gives O(1) lookup; the list gives O(1) reordering and eviction.
Use sentinel dummy head and tail nodes so insert/remove at the ends never touch null pointers — every real node always has a prev and a next.
On both get and put-of-existing-key, splice the node out and re-insert it at the front. On a put that overflows capacity, evict tail.prev (the LRU node) and delete it from the map.

Target-Sum Combinations (unlimited reuse)

Given a list of distinct candidate transfer amounts and a target amount, return all unique combinations of candidates that sum exactly to the target. Each candidate may be used an unlimited number of times. A combination is a multiset of candidate values (order does not matter); two combinations are the same if they use each candidate the same number of times. Return each combination as a sorted (non-decreasing) list, and return the list of combinations in sorted order. Backtracking is the natural fit: the answer set can be exponential and we must enumerate every valid combination, not just count or find one — so a DFS over an implicit decision tree that emits each leaf is appropriate, whereas a DP table (great for *counting* combinations or the coin-change minimum) does not directly materialize the combinations themselves. Pruning / dedup rules: - Sort candidates and only ever recurse into indices >= the current index. Fixing a non-decreasing pick order is what prevents permutations of the same multiset (e.g. [2,3] and [3,2]) from both being emitted. - Allowing the same index again (start at `i`, not `i+1`) implements unlimited reuse. - Once a sorted candidate exceeds the remaining target, break — all later candidates are larger and cannot fit.

Constraints

1 <= candidates.length <= 30
Candidate values are positive integers; treat duplicates in the input as a single distinct value.
1 <= target <= 500 (typical OA bound)
Each candidate may be reused an unlimited number of times.

Examples

Input: ([2, 3, 6, 7], 7)

Expected Output: [[2, 2, 3], [7]]

Explanation: 2+2+3=7 and 7 itself. No other multiset of these candidates sums to 7.

Input: ([2, 3, 5], 8)

Expected Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Explanation: Three distinct combinations sum to 8 with unlimited reuse.

Input: ([2], 1)

Expected Output: []

Explanation: Edge: every candidate (2) already exceeds the target (1), so no combination exists.

Input: ([1], 0)

Expected Output: []

Explanation: Edge: target 0 yields no non-empty combination (the empty combination is not returned).

Input: ([3, 5, 8], 11)

Expected Output: [[3, 3, 5], [3, 8]]

Explanation: 3+3+5=11 and 3+8=11.

Input: ([5, 10, 25], 30)

Expected Output: [[5, 5, 5, 5, 5, 5], [5, 5, 5, 5, 10], [5, 5, 10, 10], [5, 25], [10, 10, 10]]

Explanation: Coin-style amounts: all five non-decreasing multisets of {5,10,25} that total 30.

Hints

Sort the candidates first. Recursing only into indices >= the current pick forces non-decreasing order, which is exactly what stops [2,3] and [3,2] from both appearing.
Unlimited reuse means the recursive call starts at the same index i (not i+1) — you can pick the same value again.
Prune hard: once a (sorted) candidate exceeds the remaining target, break out of the loop — every later candidate is at least as large and cannot fit. A target of 0 reached means emit a copy of the current path.

Quick Overview