Quick Overview

This question evaluates a candidate's ability to design and implement complex data structures, testing algorithmic reasoning, time/space complexity analysis, state modeling, and organization of code and tests.

Approach verbose data-structure design

Company: Hudson River Trading

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

For a data-structure design problem whose behavior is easy to understand but whose implementation is lengthy, describe your step-by-step approach: clarifying operations and constraints, sketching state/transition diagrams, selecting core data structures, reasoning about per-operation time/space complexity, handling boundary cases, and organizing code and tests to minimize bugs.

Quick Answer: This question evaluates a candidate's ability to design and implement complex data structures, testing algorithmic reasoning, time/space complexity analysis, state modeling, and organization of code and tests.

Design and implement an LRU, Least Recently Used, cache. The cache has a fixed capacity and supports two operations: PUT and GET. Operations are provided as integer arrays. A PUT operation is represented as [1, key, value] and inserts or updates the key with the given value. A GET operation is represented as [2, key] and returns the value for the key if it exists, otherwise -1. Both PUT and GET mark the key as most recently used when the key exists. When a PUT causes the cache to exceed capacity, evict the least recently used key. Process all operations in order and return the results of all GET operations.

Constraints

  • 0 <= capacity <= 100000
  • 0 <= len(operations) <= 200000
  • Each operation is either [1, key, value] or [2, key]
  • -1000000000 <= key, value <= 1000000000
  • The intended solution should run each operation in O(1) average time

Examples

Input: (2, [[1, 1, 1], [1, 2, 2], [2, 1], [1, 3, 3], [2, 2], [1, 4, 4], [2, 1], [2, 3], [2, 4]])

Expected Output: [1, -1, -1, 3, 4]

Explanation: GET 1 returns 1 and makes key 1 most recent. Adding key 3 evicts key 2. Adding key 4 later evicts key 1.

Input: (2, [[1, 1, 1], [1, 2, 2], [1, 1, 10], [1, 3, 3], [2, 1], [2, 2], [2, 3]])

Expected Output: [10, -1, 3]

Explanation: Updating key 1 changes its value to 10 and makes it most recent, so key 2 is evicted when key 3 is inserted.

Hints

  1. Use a hash map to find a key's stored node in O(1) time.
  2. Use a doubly linked list to maintain least-recently-used to most-recently-used order, and move nodes to the end when they are accessed.

Loading coding console...