Implement cloud storage with quotas and compression
Company: Coinbase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
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.
Input: ([['ADD_USER', 'u', '9'], ['ADD_FILE', 'u', 'x', '6'], ['COMPRESS_FILE', 'u', 'x'], ['ADD_FILE', 'u', 'y', '6'], ['DECOMPRESS_FILE', 'u', 'x.compressed'], ['COMPRESS_FILE', 'u', 'y'], ['DECOMPRESS_FILE', 'u', 'x.compressed'], ['GET_FILE_SIZE', 'u', 'x'], ['GET_FILE_SIZE', 'u', 'x.compressed'], ['GET_FILE_SIZE', 'u', 'y.compressed']],)
Expected Output: ['true', 'true', 'true', 'true', 'false', 'true', 'true', '6', '', '3']
Explanation: The first decompression fails because it would exceed capacity. After compressing y, there is enough room, so decompressing x.compressed succeeds.
Input: ([['ADD_FILE', 'ghost', 'a', '1'], ['GET_FILE_SIZE', 'ghost', 'a'], ['UPDATE_CAPACITY', 'ghost', '5'], ['ADD_USER', 'eve', '0'], ['ADD_FILE', 'eve', 'z', '1'], ['COMPRESS_FILE', 'eve', 'missing'], ['DECOMPRESS_FILE', 'eve', 'missing.compressed'], ['ADD_USER', 'eve', '3']],)
Expected Output: ['false', '', '-1', 'true', 'false', 'false', 'false', 'false']
Explanation: Covers missing users, empty-string responses, update on a missing user, zero capacity, missing files, and duplicate user creation.
Input: ([['ADD_USER', 'p', '10'], ['ADD_FILE', 'p', 'a', '6'], ['COMPRESS_FILE', 'p', 'a'], ['ADD_FILE', 'p', 'b', '7'], ['UPDATE_CAPACITY', 'p', '2'], ['GET_FILE_SIZE', 'p', 'a.compressed'], ['GET_FILE_SIZE', 'p', 'b']],)
Expected Output: ['true', 'true', 'true', 'true', '2', '', '']
Explanation: After compressing a, the heap still contains a stale entry for the old uncompressed file. UPDATE_CAPACITY must ignore stale data and delete the current largest valid files until used space is within the new limit.
Input: ([],)
Expected Output: []
Explanation: Edge case: no queries means no results.
Input: ([['ADD_USER', 'odd', '1'], ['ADD_FILE', 'odd', 'f', '1'], ['COMPRESS_FILE', 'odd', 'f'], ['GET_FILE_SIZE', 'odd', 'f.compressed'], ['DECOMPRESS_FILE', 'odd', 'f.compressed'], ['GET_FILE_SIZE', 'odd', 'f']],)
Expected Output: ['true', 'true', 'true', '0', 'true', '0']
Explanation: Compression uses integer division, so a 1-byte file becomes 0 bytes. Decompression then doubles 0 to 0, matching the rules exactly.
Solution
def solution(queries):
import heapq
class RevStr:
__slots__ = ('s',)
def __init__(self, s):
self.s = s
def __lt__(self, other):
return self.s > other.s
def __eq__(self, other):
return isinstance(other, RevStr) and self.s == other.s
users = {}
result = []
suffix = '.compressed'
def add_current_file(user, name, size):
user['files'][name] = size
user['used'] += size
heapq.heappush(user['heap'], (-size, RevStr(name), name))
def evict_largest_valid(user):
files = user['files']
heap = user['heap']
while heap:
neg_size, _rev_name, name = heapq.heappop(heap)
size = -neg_size
if files.get(name) == size:
del files[name]
user['used'] -= size
return True
return False
for query in queries:
op = query[0]
if op == 'ADD_USER':
user_id = query[1]
capacity = int(query[2])
if user_id in users:
result.append('false')
else:
users[user_id] = {
'capacity': capacity,
'used': 0,
'files': {},
'heap': []
}
result.append('true')
elif op == 'ADD_FILE':
user_id = query[1]
file_name = query[2]
size = int(query[3])
user = users.get(user_id)
if user is None or file_name in user['files'] or user['used'] + size > user['capacity']:
result.append('false')
else:
add_current_file(user, file_name, size)
result.append('true')
elif op == 'GET_FILE_SIZE':
user_id = query[1]
file_name = query[2]
user = users.get(user_id)
if user is None or file_name not in user['files']:
result.append('')
else:
result.append(str(user['files'][file_name]))
elif op == 'UPDATE_CAPACITY':
user_id = query[1]
new_capacity = int(query[2])
user = users.get(user_id)
if user is None:
result.append('-1')
else:
user['capacity'] = new_capacity
deleted = 0
while user['used'] > new_capacity:
if evict_largest_valid(user):
deleted += 1
else:
break
result.append(str(deleted))
elif op == 'COMPRESS_FILE':
user_id = query[1]
file_name = query[2]
user = users.get(user_id)
if user is None:
result.append('false')
continue
if file_name not in user['files']:
result.append('false')
continue
if file_name.endswith(suffix):
result.append('false')
continue
compressed_name = file_name + suffix
if compressed_name in user['files']:
result.append('false')
continue
old_size = user['files'].pop(file_name)
user['used'] -= old_size
add_current_file(user, compressed_name, old_size // 2)
result.append('true')
elif op == 'DECOMPRESS_FILE':
user_id = query[1]
compressed_name = query[2]
user = users.get(user_id)
if user is None:
result.append('false')
continue
if compressed_name not in user['files']:
result.append('false')
continue
if not compressed_name.endswith(suffix):
result.append('false')
continue
original_name = compressed_name[:-len(suffix)]
if original_name == '' or original_name in user['files']:
result.append('false')
continue
compressed_size = user['files'][compressed_name]
new_size = compressed_size * 2
if user['used'] - compressed_size + new_size > user['capacity']:
result.append('false')
continue
del user['files'][compressed_name]
user['used'] -= compressed_size
add_current_file(user, original_name, new_size)
result.append('true')
return resultTime complexity: O(Q log Q) total amortized in the worst case. Space complexity: O(Q).
Hints
- Use a hash map for each user's files so existence checks and size lookups are O(1) on average.
- 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.