Replysis AI
Try free

Question bank / Software Engineering, Coding, Intermediate

How to answer: Design an LRU cache with O(1) get and put operations.

Whether you can combine two structures so that two operations both stay constant time.

What the interviewer is testing.

Data structure composition and invariants. Whether you can combine two structures so that two operations both stay constant time.

An outline for this question.

  1. Say why one structure is not enough: a hash map finds fast but cannot order, a list orders but cannot find.
  2. Combine a hash map to nodes with a doubly linked list ordered by recency.
  3. On get, move the node to the front. On put, insert at the front and evict the tail when full.
  4. Name the invariant: the map and the list always hold exactly the same keys.

The mistake to avoid.

Using a singly linked list. Removing a node from the middle then needs a scan, and the O(1) promise breaks.

The general method: clarify, plan, code, test.

The same shape works for most coding questions, whatever the topic.

  • Restate the problem and ask about inputs, size limits and edge cases before you write anything.
  • Describe your approach and its complexity out loud, then check it makes sense with the interviewer.
  • Write clean code in small steps, narrating as you go.
  • Walk through a normal case and an edge case by hand, then say what you would test.

Practice it, out loud.

Reading an outline is not the same as saying it. Answer this question in a mock interview, in your own words, then compare it with the outline above.

Practice this questionSee live interview help

More to practice.

This is a Replysis practice question. It is not a leaked or official question from any company, and the outline is a guide to structure, not a script. Use your own experience and facts.