Katkat
Back

Implement LRU and target-sum combinations

AdyenSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.