Implement an LRU cache with O(1) ops

Q: Implement an LRU cache with O(1) ops

This is a Coding & Algorithms interview question from OneMain Financial for Data Scientist 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 code an LRU cache supporting get(key) and put(key, value) in O(1) average time with capacity N. Specify your data structures, handle updates to existing keys, and define precise eviction behavior when capacity is exceeded. Discuss thread-safety concerns and how you would add an optional per-key TTL without violating big-O guarantees. Provide complexity analysis for time and space, and identify edge cases (e.g., N=1, repeated gets, large values).

Implement an LRU cache with O(1) ops

Comments (0)