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.

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.

Read the full Hudson River Trading Software Engineer interview experience this question came from

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...