The Tail End

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
BCG Securities

Problem

Asking for the lowest value still saved has to stay cheap however many checkpoints have piled up and however many have been rolled back. We're replaying commands against a Checkpoints class, each a list with the command name first: ['push', 5] saves a value, ['pop'] rolls back the newest save, ['peek'] reads the newest without removing it, and ['is_empty'] and ['min'] report on what is still saved, with one result back per command, in order.

Push, pop, peek. The basics that break people.

Example 1

Input:

operations = [["push",5],["push",2],["min"],["pop"],["min"],["peek"]]

Output:

[null,null,2,2,5,5]

Example 2

Input:

operations = [["is_empty"],["pop"],["push",8],["is_empty"],["min"],["pop"],["min"]]

Output:

[true,null,null,false,8,8,null]

Worked solution and explanation

What this problem is really about

Saving, rolling back and reading the newest are free here: a Python list already does it if you treat its last slot as the newest save. What actually bites is min. Call min(self.values) every time and you rescan every save per query, quietly turning a long replay into O(n^2). Index the last slot of an empty list and an IndexError kills the replay mid-sequence. The real requirement is a second list of running lows that grows and shrinks together with the values, plus an empty guard on every read. Miss the pairing and the lowest goes stale after a rollback; miss the guard and your results list never comes back.

Build it up

Step 1: Give Checkpoints a reset that sets up two lists

Checkpoints keeps two lists side by side: values for what was saved and lows for the lowest value at each depth. reset creates both empty, and the_tail_end calls it once before replaying anything, so every run starts clean.

Step 2: Record the running low on every save

In add, compare the incoming value with the last slot of lows and append whichever is smaller (or the value itself when lows is empty). Each slot of lows now answers "what was the lowest when this many values were saved", so the current answer is always the last slot.

Step 3: Trim both lists together on rollback

undo reads the last slot of values, then deletes the last slot of BOTH lists. Deleting from values alone is the bug: lows would still remember a value that was rolled back. newest reads the same slot and deletes nothing.

Step 4: Guard the empty case before indexing

undo, newest and lowest each check for an empty list first and return None. That one early return per method is what keeps a badly timed command from crashing the whole replay.

Step 5: Drive the class from the command list

the_tail_end walks operations in order, dispatches on op[0], and appends exactly one result per command: None for 'push', a boolean for 'is_empty'. One command in, one result out keeps the output aligned with the input.

The solution

`Checkpoints` with a paired list of running lows
class Checkpoints:
    def reset(self):
        self.values = []
        self.lows = []  # lows[i] is the lowest of values[0..i]

    def add(self, value):
        low = value
        if self.lows:
            last = len(self.lows) - 1
            if self.lows[last] < value:
                low = self.lows[last]
        self.values.append(value)
        self.lows.append(low)
        return None

    def undo(self):
        if not self.values:
            return None
        last = len(self.values) - 1
        newest = self.values[last]
        del self.values[last]
        del self.lows[last]
        return newest

    def newest(self):
        if not self.values:
            return None
        return self.values[len(self.values) - 1]

    def is_empty(self):
        return len(self.values) == 0

    def lowest(self):
        if not self.lows:
            return None
        return self.lows[len(self.lows) - 1]


def the_tail_end(operations):
    saved = Checkpoints()
    saved.reset()
    results = []
    for op in operations:
        name = op[0]
        if name == 'push':
            results.append(saved.add(op[1]))
        elif name == 'pop':
            results.append(saved.undo())
        elif name == 'peek':
            results.append(saved.newest())
        elif name == 'is_empty':
            results.append(saved.is_empty())
        elif name == 'min':
            results.append(saved.lowest())
    return results
Rescan on every query
min(self.values) walks every save on each call. Correct, but many queries on a deep history go O(n^2), and it still needs a guard because min([]) raises.
Running low kept alongside
Each save records the running low beside the value; each rollback discards it. The answer is always the last slot of lows, read in O(1) behind the same empty guard as undo and newest.

Common follow-up questions