Implement LRU and target-sum combinations

Q: Implement LRU and target-sum combinations

This is a Coding & Algorithms interview question from Adyen for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Design and implement the following:

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

Implement LRU and target-sum combinations

Comments (0)