Implement LRU and target-sum combinations
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: This question evaluates implementation and algorithmic skills by combining a practical data-structure design task (implementing an in-memory LRU cache) with a combinatorial algorithms problem (finding target-sum combinations), measuring understanding of correctness, complexity analysis, and trade-off reasoning.