Katkat
Back

Implement LRU cache and copy random list

MetaMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to handle complex pointer manipulation through linked-list deep copying and your proficiency in designing a thread-safe-capable cache using hash maps and doubly-linked lists.

Part 1: Deep Copy with Random Pointers

Given a linked list of size n where each node has an additional random pointer that points to any node in the list or null, return a deep copy of the list. You cannot modify the original list structure.

Part 2: LRU Cache Design

Design and implement a Least Recently Used (LRU) cache class LRUCache that supports get(key) and put(key, value) operations in O(1) average time complexity.

Function Signatures

class Node:
    def __init__(self, val, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

class LRUCache:
    def __init__(self, capacity: int):
        pass
    def get(self, key: int) -> int:
        pass
    def put(self, key: int, value: int) -> None:
        pass

Constraints

  • For Part 1: 0 2 where 1.random points to 2 and 2.random points to 1. The copy must be a distinct set of memory nodes that maintain identical structural and random-pointer relationships.

LRU Cache: cache = LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1); The cache is now {1: 1, 2: 2}. If we call cache.put(3, 3), the key 2 is evicted, leaving {1: 1, 3: 3}.

Hints

Hint 1

For the deep copy, consider using a hash map to map original nodes to their cloned counterparts during the first pass.

Hint 2

For the LRU cache, a combination of a hash map (for O(1) lookups) and a doubly-linked list (for O(1) insertion and deletion of nodes) is essential.

Hint 3

In the deep copy, if you don't want to use extra space for a hash map, you can interleave cloned nodes directly into the original list temporarily.

Follow-up questions

  • How would you modify the LRU cache to be thread-safe in a multi-threaded environment?
  • If the deep copy list was extremely large and contained cycles, how would your cloning approach change?
  • Can you explain the trade-offs between using a doubly-linked list versus a standard Python `OrderedDict` for the LRU cache implementation?