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.

What difficulty level is this interview question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at TikTok during technical interviews.

Implement an LRU cache | TikTok Interview Question

Q: Implement an LRU cache

This question evaluates understanding of cache design and eviction policies (LRU), along with competency in selecting and reasoning about data structures and complexity to support efficient get and put operations under capacity constraints.

Problem: LRU Cache

Design and implement a data structure that supports an LRU (Least Recently Used) cache with a fixed capacity.

Requirements

Implement a cache with the following operations:

get(key) -> value
- If key exists in the cache, return its value and mark the entry as most recently used .
- If key does not exist, return -1 .
put(key, value) -> void
- Insert or update the (key, value) pair.
- If inserting causes the number of keys to exceed capacity , evict the least recently used entry.
- Updating an existing key should also mark it as most recently used .

Performance Constraints

Target time complexity: O(1) average for both get and put .
Space complexity: O(capacity) .

Example

Assume capacity = 2:

put(1, 10)
put(2, 20)
get(1) -> 10 (now key 1 is most recently used)
put(3, 30) (evicts key 2 as least recently used)
get(2) -> -1

Notes

You may choose any programming language, but clearly describe the data structures you use and how you ensure O(1) operations.

Problem: LRU Cache

Design and implement a data structure that supports an LRU (Least Recently Used) cache with a fixed capacity.

Requirements

Implement a cache with the following operations:

get(key) -> value

If key exists in the cache, return its value and mark the entry as most recently used .
If key does not exist, return -1 .

put(key, value) -> void

Insert or update the (key, value) pair.
If inserting causes the number of keys to exceed capacity , evict the least recently used entry.
Updating an existing key should also mark it as most recently used .

Performance Constraints

Target time complexity: O(1) average for both get and put .

Space complexity: O(capacity) .

Example

Assume capacity = 2:

put(1, 10)

put(2, 20)

get(1) -> 10 (now key 1 is most recently used)

put(3, 30) (evicts key 2 as least recently used)

get(2) -> -1

Notes

You may choose any programming language, but clearly describe the data structures you use and how you ensure O(1) operations.

Implement an LRU cache

Quick Overview

Problem: LRU Cache

Requirements

Performance Constraints

Example

Notes

Submit Your Answer

Implement an LRU cache

Quick Overview

Problem: LRU Cache

Requirements

Performance Constraints

Example

Notes

Submit Your Answer