Implement classes in existing abstract hierarchy
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: This question evaluates object-oriented design and implementation skills in Python within the Coding & Algorithms and software engineering domain, focusing on completing concrete subclasses in an existing abstract class hierarchy while preserving public interfaces and type compatibility.
Constraints
- 0 <= len(commands) <= 200000
- 1 <= len(key), len(prefix) <= 30
- -10^9 <= value, delta <= 10^9
- All prefix sums fit in a signed 64-bit integer
- Only successful SET, ADD, and DELETE commands are undoable; GET, SUM, invalid commands, and ROLLBACK itself are not recorded as mutations
Examples
Input: (['SET apple 3', 'SET app 2', 'SUM app', 'ADD apple 4', 'GET apple', 'SUM ap'],)
Expected Output: ['5', '7', '9']
Explanation: Both app and apple match prefix app for a sum of 5. After adding 4 to apple, apple is 7 and the sum for prefix ap is 9.
Input: (['GET missing', 'DELETE missing', 'SET x 10', 'DELETE x', 'GET x', 'ROLLBACK 1', 'GET x', 'ROLLBACK 2', 'GET x'],)
Expected Output: ['NULL', 'ERROR', 'NULL', '10', 'ERROR', '10']
Explanation: Deleting a missing key is an error. Rolling back one successful mutation restores x. Rolling back two more mutations fails because only one undoable mutation remains.
Input: (['SET a 5', 'ADD a -2', 'SUM a', 'SET bad notint', 'ADD b 1', 'ROLLBACK 0', 'GET a'],)
Expected Output: ['3', 'ERROR', 'ERROR', '3']
Explanation: Negative deltas are valid, so a becomes 3. The malformed integer and ADD on a missing key both produce errors. ROLLBACK 0 is valid and changes nothing.
Input: (['SET a 1', 'SET ab 2', 'SET abc 3', 'SUM a', 'ROLLBACK 2', 'SUM a', 'GET ab', 'GET abc', 'ROLLBACK 1', 'GET a', 'SUM a'],)
Expected Output: ['6', '1', 'NULL', 'NULL', 'NULL', '0']
Explanation: The first sum is 1 + 2 + 3. Rolling back two mutations removes ab and abc. Rolling back one more removes a, so later lookups are NULL and the prefix sum is 0.
Input: (['SET k 5', 'SET k 8', 'SUM k', 'ROLLBACK 1', 'GET k', 'DELETE k', 'SUM k', 'ROLLBACK 1', 'GET k'],)
Expected Output: ['8', '5', '0', '5']
Explanation: A SET over an existing key records the old value for rollback. DELETE is also rollbackable, restoring k to 5.
Input: ([] ,)
Expected Output: []
Explanation: With no commands, there are no outputs.
Solution
def solution(commands):
from abc import ABC, abstractmethod
ERROR = 'ERROR'
def is_name(token):
return isinstance(token, str) and len(token) > 0 and all('a' <= ch <= 'z' for ch in token)
def parse_int(token):
try:
return int(token)
except (TypeError, ValueError):
raise ValueError('invalid integer')
class Context:
def __init__(self):
self.store = {}
self.prefix_sums = {}
self.undo_stack = []
self.outputs = []
def _add_to_prefixes(self, key, delta):
if delta == 0:
return
for i in range(1, len(key) + 1):
prefix = key[:i]
new_total = self.prefix_sums.get(prefix, 0) + delta
if new_total:
self.prefix_sums[prefix] = new_total
else:
self.prefix_sums.pop(prefix, None)
def record_set(self, key, value):
existed = key in self.store
old_value = self.store.get(key, 0)
delta = value - old_value if existed else value
self.store[key] = value
self._add_to_prefixes(key, delta)
self.undo_stack.append((key, existed, old_value))
def record_delete(self, key):
old_value = self.store[key]
del self.store[key]
self._add_to_prefixes(key, -old_value)
self.undo_stack.append((key, True, old_value))
def restore(self, key, existed, old_value):
if key in self.store:
current_value = self.store.pop(key)
self._add_to_prefixes(key, -current_value)
if existed:
self.store[key] = old_value
self._add_to_prefixes(key, old_value)
class Command(ABC):
@abstractmethod
def validate(self, ctx):
pass
@abstractmethod
def execute(self, ctx):
pass
class SetCommand(Command):
def __init__(self, key, value):
self.key = key
self.value = value
def validate(self, ctx):
return True
def execute(self, ctx):
ctx.record_set(self.key, self.value)
class AddCommand(Command):
def __init__(self, key, delta):
self.key = key
self.delta = delta
def validate(self, ctx):
return self.key in ctx.store
def execute(self, ctx):
ctx.record_set(self.key, ctx.store[self.key] + self.delta)
class DeleteCommand(Command):
def __init__(self, key):
self.key = key
def validate(self, ctx):
return self.key in ctx.store
def execute(self, ctx):
ctx.record_delete(self.key)
class GetCommand(Command):
def __init__(self, key):
self.key = key
def validate(self, ctx):
return True
def execute(self, ctx):
if self.key in ctx.store:
ctx.outputs.append(str(ctx.store[self.key]))
else:
ctx.outputs.append('NULL')
class SumCommand(Command):
def __init__(self, prefix):
self.prefix = prefix
def validate(self, ctx):
return True
def execute(self, ctx):
ctx.outputs.append(str(ctx.prefix_sums.get(self.prefix, 0)))
class RollbackCommand(Command):
def __init__(self, count):
self.count = count
def validate(self, ctx):
return 0 <= self.count <= len(ctx.undo_stack)
def execute(self, ctx):
for _ in range(self.count):
key, existed, old_value = ctx.undo_stack.pop()
ctx.restore(key, existed, old_value)
class Parser(ABC):
@abstractmethod
def parse(self, line):
pass
class CommandParser(Parser):
def parse(self, line):
if not isinstance(line, str):
raise ValueError('invalid command')
parts = line.split()
if not parts:
raise ValueError('invalid command')
op = parts[0]
if op == 'SET':
if len(parts) != 3 or not is_name(parts[1]):
raise ValueError('invalid SET')
return SetCommand(parts[1], parse_int(parts[2]))
if op == 'ADD':
if len(parts) != 3 or not is_name(parts[1]):
raise ValueError('invalid ADD')
return AddCommand(parts[1], parse_int(parts[2]))
if op == 'DELETE':
if len(parts) != 2 or not is_name(parts[1]):
raise ValueError('invalid DELETE')
return DeleteCommand(parts[1])
if op == 'GET':
if len(parts) != 2 or not is_name(parts[1]):
raise ValueError('invalid GET')
return GetCommand(parts[1])
if op == 'SUM':
if len(parts) != 2 or not is_name(parts[1]):
raise ValueError('invalid SUM')
return SumCommand(parts[1])
if op == 'ROLLBACK':
if len(parts) != 2:
raise ValueError('invalid ROLLBACK')
count = parse_int(parts[1])
if count < 0:
raise ValueError('invalid ROLLBACK')
return RollbackCommand(count)
raise ValueError('unknown command')
class Processor:
def __init__(self, parser):
self.parser = parser
self.ctx = Context()
def run(self, lines):
for line in lines:
try:
command = self.parser.parse(line)
if command.validate(self.ctx):
command.execute(self.ctx)
else:
self.ctx.outputs.append(ERROR)
except ValueError:
self.ctx.outputs.append(ERROR)
return self.ctx.outputs
return Processor(CommandParser()).run(commands)Time complexity: O(T), where T is the total number of characters in all commands plus the total length of keys updated during successful SET, ADD, DELETE, and ROLLBACK operations. Each SUM query is O(1) after prefix totals are maintained.. Space complexity: O(U * L + M), where U is the number of distinct stored keys ever contributing prefixes, L is the maximum key length, and M is the number of successful undoable mutations currently on the undo stack..
Hints
- Use concrete command objects with common validate and execute methods so the processor can treat them polymorphically.
- For efficient SUM prefix queries under updates and rollback, maintain a running total for every prefix of each key whenever that key changes.