Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
@dataclass
class TrueRun:
start: int
end: int
class BoolStackSparse:
def __init__(self):
self.clear()
@property
def _top(self) -> TrueRun:
return self.true_runs[-1]
def push(self, value: bool):
""" Push a bool onto stack """
if value:
# Need to push a run or update
if self._top.end == self.head_idx:
self._top.end += 1
else:
self.true_runs.append(TrueRun(self.head_idx, self.head_idx+1))
self.head_idx += 1
def pop(self) -> bool:
""" Pop in lifo order """
if self.empty():
raise ValueError("empty")
v = False
if self._top.end == self.head_idx:
# We are in a true run
v = True
self._top.end -=1
# If the top true run has 0 len, pop it (unless it's the run at 0)
if self._top.end == self._top.start and self._top.start != 0:
self.true_runs.pop()
self.head_idx -= 1
return v
def empty(self) -> bool:
""" Whether the stack is empty """
return self.head_idx == 0
def clear(self) -> None:
""" Reset to empty state """
self.head_idx = 0
self.true_runs = [TrueRun(0, 0)] # List of TrueRun insts
- Anonymous January 31, 2022