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 Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Shopify.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Shopify during technical interviews.

Implement an LRU Cache | Shopify Interview Question

Q: Implement an LRU Cache

This question evaluates competence in designing efficient cache mechanisms and mastery of data-structure strategies to support average O(1) get and put operations.

Problem: LRU Cache (LeetCode 146)

Design and implement a Least Recently Used (LRU) Cache that supports the following operations in average O(1) time.

Requirements

Implement a class LRUCache with:

LRUCache(int capacity) : Initialize the cache with a positive capacity.
int get(int key) : Return the value of the key if it exists; otherwise return -1 .
- Accessing a key counts as using it, so it becomes most recently used .
void put(int key, int value) : Insert or update the value of the key.
- If the key exists, update its value and mark it as most recently used .
- If inserting causes the cache to exceed capacity, evict the least recently used key.

Notes / Constraints

Keys and values are integers.
Aim for O(1) average time per get and put .
You may use any language, standard library containers, and write unit tests.

Example

If capacity = 2:

put(1, 1) -> cache = {1=1}
put(2, 2) -> cache = {1=1, 2=2}
get(1) -> returns 1 , cache order becomes [2 (LRU), 1 (MRU)]
put(3, 3) -> evicts key 2 , cache = {1=1, 3=3}
get(2) -> returns -1

Problem: LRU Cache (LeetCode 146)

Design and implement a Least Recently Used (LRU) Cache that supports the following operations in average O(1) time.

Requirements

Implement a class LRUCache with:

LRUCache(int capacity) : Initialize the cache with a positive capacity.

int get(int key) : Return the value of the key if it exists; otherwise return -1 .

Accessing a key counts as using it, so it becomes most recently used .

void put(int key, int value) : Insert or update the value of the key.

If the key exists, update its value and mark it as most recently used .
If inserting causes the cache to exceed capacity, evict the least recently used key.

Notes / Constraints

Keys and values are integers.

Aim for O(1) average time per get and put .

You may use any language, standard library containers, and write unit tests.

Example

If capacity = 2:

put(1, 1) -> cache = {1=1}

put(2, 2) -> cache = {1=1, 2=2}

get(1) -> returns 1 , cache order becomes [2 (LRU), 1 (MRU)]

put(3, 3) -> evicts key 2 , cache = {1=1, 3=3}

get(2) -> returns -1

Implement an LRU Cache

Quick Overview

Problem: LRU Cache (LeetCode 146)

Requirements

Notes / Constraints

Example

Comments (0)

Implement an LRU Cache

Quick Overview

Problem: LRU Cache (LeetCode 146)

Requirements

Notes / Constraints

Example

Comments (0)