Quick Overview

This question evaluates understanding of in-memory resource management, capacity accounting, eviction policies, and data-structure design for efficient dataset lookup and size tracking in the Coding & Algorithms domain.

Implement a disk space manager with eviction

Company: NVIDIA

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement an in-memory **disk space manager** that stores datasets by `datasetId` with a given `size` (e.g., in MB). The manager has a fixed **total capacity** (total space), not a limit on the number of datasets. You must support: 1) `put(datasetId, size)` - If `size > totalCapacity`, return an error (the dataset can never fit). - If there is enough free space, store/update this dataset. - If there is not enough free space, you may **evict other datasets** to free space (eviction policy is up to you, e.g., LRU). - If after evicting everything possible the dataset still cannot fit, return an error. 2) `get(datasetId)` - Return the stored `size` for that dataset if present; otherwise indicate “not found”. Clarify/handle updates: if `put` is called for an existing `datasetId`, treat it as replacing the old size (adjust used space accordingly). Implement the class/API in the language of your choice (e.g., Java).

Quick Answer: This question evaluates understanding of in-memory resource management, capacity accounting, eviction policies, and data-structure design for efficient dataset lookup and size tracking in the Coding & Algorithms domain.

Design an in-memory disk space manager with a fixed total capacity. To make the problem deterministic, use the LRU (Least Recently Used) eviction policy. Each dataset is identified by datasetId and stores an integer size. Every successful get or successful put/update makes that dataset the most recently used. When a put needs more space, evict least recently used datasets until the new dataset fits. If size is greater than total capacity, the put must fail immediately and the manager state must remain unchanged. If put is called for an existing datasetId, replace its old size with the new size and adjust used space accordingly. Because the judge expects a single function, you must process a batch of operations and return the result of each operation in order.

Constraints

  • 0 <= total_capacity <= 10^9
  • 0 <= len(operations) <= 2 * 10^5
  • For each put operation, 1 <= size <= 10^9
  • datasetId is a non-empty string
  • Use LRU eviction: successful get and successful put/update make the dataset most recently used

Examples

Input: (5, [])

Expected Output: []

Explanation: No operations means no output.

Input: (10, [('put', 'A', 4), ('put', 'B', 3), ('get', 'A'), ('put', 'C', 5), ('get', 'B'), ('get', 'A'), ('get', 'C')])

Expected Output: ['ok', 'ok', 4, 'ok', -1, 4, 5]

Explanation: After get('A'), A becomes most recent. Putting C needs 5 units, so B is evicted first as the least recently used dataset.

Hints

  1. You need two things at once: fast lookup by datasetId and fast access to the least recently used dataset.
  2. When updating an existing dataset, free its old size before deciding whether you still need to evict other datasets.

Loading coding console...