Quick Overview

This question evaluates the ability to design and implement in-memory state management and algorithmic logic for user-scoped storage, including capacity tracking, deterministic eviction policies, file metadata manipulation, and integer/string operations.

Implement cloud storage with quotas and compression

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem Implement an **in-memory cloud storage** service that supports multiple users, per-user storage quotas, changing quotas with eviction, and file compression/decompression. You are given a list of queries. Each query is an array of strings where the first element is the operation name. Return an array of strings—one result per query. ### Data model - Each **user** has: - a unique `userId` - an integer `capacity` (maximum total size of that user’s files) - zero or more **files** - Each **file** belongs to exactly one user and has: - `fileName` (string) - `size` (positive integer) - File names are unique **per user**. ### Operations All operations are scoped to a user unless stated otherwise. #### 1) `ADD_USER userId capacity` Create a new user. - If `userId` already exists: return `"false"`. - Otherwise: create the user with the given capacity and return `"true"`. #### 2) `ADD_FILE userId fileName size` Add a new file for a user. - If the user does not exist: return `"false"`. - If a file with that name already exists for the user: return `"false"`. - If adding the file would make the user’s total used size exceed the user’s capacity: return `"false"`. - Otherwise add the file and return `"true"`. #### 3) `GET_FILE_SIZE userId fileName` Return the size of a file. - If the user or file does not exist: return `""` (empty string). - Otherwise return the file size as a string. #### 4) `UPDATE_CAPACITY userId newCapacity` Update a user’s capacity. If after the update the user is over capacity, you must **delete existing files** until the total used size is within capacity. Eviction rule: - Repeatedly delete the user’s **largest** file. - If multiple files tie for largest size, delete the one with the **lexicographically largest** `fileName` to make the behavior deterministic. - Stop once total used size \(\le\) `newCapacity`. Return: - If the user does not exist: return `"-1"`. - Otherwise return the **number of files deleted** (as a string). (If no deletion needed, return `"0"`.) #### 5) `COMPRESS_FILE userId fileName` Compress an existing file. - Compression renames the file from `fileName` to `fileName + ".compressed"`. - The compressed file size becomes `size / 2` using **integer division**. Rules: - If user does not exist: return `"false"`. - If `fileName` does not exist: return `"false"`. - If `fileName` already ends with `.compressed`: return `"false"`. - If the target name `fileName + ".compressed"` already exists for that user: return `"false"`. - Otherwise perform the rename and size change and return `"true"`. > Note: Compression reduces used space, so it will never violate capacity. #### 6) `DECOMPRESS_FILE userId compressedName` Decompress an existing compressed file. - Decompression renames `compressedName` to the original name by removing the `.compressed` suffix. - The decompressed file size becomes `size * 2`. Rules: - If user does not exist: return `"false"`. - If `compressedName` does not exist: return `"false"`. - If `compressedName` does **not** end with `.compressed`: return `"false"`. - Let `originalName` be `compressedName` with the final `.compressed` removed. If a file named `originalName` already exists: return `"false"`. - If decompressing would make the user exceed capacity: return `"false"` (and do not change anything). - Otherwise perform the rename and size change and return `"true"`. ### Input/Output format - Input: `queries`, a list of string arrays. - Output: list of strings, one per query. ### Constraints (you may assume) - Number of queries up to ~10^5. - File sizes and capacities fit in 32-bit signed integers. - `userId` and `fileName` are non-empty strings. ### Example (illustrative) Queries: - `["ADD_USER","alice","10"]` → `"true"` - `["ADD_FILE","alice","a.txt","6"]` → `"true"` - `["COMPRESS_FILE","alice","a.txt"]` → `"true"` (now `a.txt.compressed` size 3) - `["DECOMPRESS_FILE","alice","a.txt.compressed"]` → `"true"` (back to size 6) - `["UPDATE_CAPACITY","alice","4"]` → must delete largest files until used \(\le 4\); return number deleted.

Quick Answer: This question evaluates the ability to design and implement in-memory state management and algorithmic logic for user-scoped storage, including capacity tracking, deterministic eviction policies, file metadata manipulation, and integer/string operations.

Process a list of queries for an in-memory cloud storage service. Each user has a storage capacity and a collection of uniquely named files. Support creating users, adding files, reading file sizes, updating capacity with deterministic eviction, and compressing/decompressing files. For UPDATE_CAPACITY, repeatedly delete the user's largest file; if multiple files have the same size, delete the lexicographically largest fileName. Compression renames fileName to fileName + '.compressed' and changes its size to size // 2. Decompression removes the final '.compressed' suffix and changes the size to size * 2. Return one string result for every query in order.

Constraints

  • 0 <= len(queries) <= 10^5
  • 0 <= capacity, newCapacity <= 2^31 - 1
  • 1 <= size <= 2^31 - 1 for ADD_FILE operations
  • userId and fileName are non-empty strings
  • File names are unique per user
  • Compressed sizes use integer division, so a compressed file may become size 0

Examples

Input: ([['ADD_USER', 'alice', '10'], ['ADD_FILE', 'alice', 'a.txt', '6'], ['GET_FILE_SIZE', 'alice', 'a.txt'], ['COMPRESS_FILE', 'alice', 'a.txt'], ['GET_FILE_SIZE', 'alice', 'a.txt'], ['GET_FILE_SIZE', 'alice', 'a.txt.compressed'], ['DECOMPRESS_FILE', 'alice', 'a.txt.compressed'], ['GET_FILE_SIZE', 'alice', 'a.txt'], ['UPDATE_CAPACITY', 'alice', '6']],)

Expected Output: ['true', 'true', '6', 'true', '', '3', 'true', '6', '0']

Explanation: Basic flow: add a user, add a file, compress it, verify the old name disappears and the new name exists with half size, then decompress it back and update capacity without needing deletion.

Input: ([['ADD_USER', 'bob', '20'], ['ADD_FILE', 'bob', 'alpha', '5'], ['ADD_FILE', 'bob', 'beta', '7'], ['ADD_FILE', 'bob', 'gamma', '7'], ['UPDATE_CAPACITY', 'bob', '10'], ['ADD_FILE', 'bob', 'delta', '5'], ['UPDATE_CAPACITY', 'bob', '5'], ['GET_FILE_SIZE', 'bob', 'alpha'], ['GET_FILE_SIZE', 'bob', 'delta']],)

Expected Output: ['true', 'true', 'true', 'true', '2', 'true', '1', '5', '']

Explanation: When capacity drops to 10, the two 7-byte files must be removed; between beta and gamma, gamma is deleted first because it is lexicographically larger. Later alpha and delta tie at size 5, so delta is deleted.

Hints

  1. Use a hash map for each user's files so existence checks and size lookups are O(1) on average.
  2. For UPDATE_CAPACITY, a priority queue can give the largest file quickly. Since files may be renamed or deleted, think about lazy deletion of outdated heap entries.

Loading coding console...