Implement LRU cache and copy random list

Q: Implement LRU cache and copy random list

This is a Coding & Algorithms interview question from Meta for Machine Learning 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

Loading...

Coding questions (two parts)

Part A — Deep copy a linked list with random pointers

You are given the head of a singly linked list where each node has:

next : pointer to the next node
random : pointer to any node in the list or null

Return a deep copy of the list (all new nodes), preserving both next and random relationships.

Goal: The copied list must not share any nodes with the original.

Part B — Design an LRU cache

Design a data structure LRUCache that supports:

get(key) : return the value for key if present, else -1
put(key, value) : insert or update the value

The cache has a fixed capacity C. When inserting causes the cache to exceed C, it must evict the least recently used item.

Requirements

Average time complexity: O(1) for both get and put
Keys are hashable (e.g., integers/strings)

Implement LRU cache and copy random list

Coding questions (two parts)

Part A — Deep copy a linked list with random pointers

Part B — Design an LRU cache

Requirements

Comments (0)