The Order Enforcer

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
phData

Problem

We're validating recorded step logs, each a string of lowercase codes where the rule is that no a step may appear once a b has occurred. Return whether a given log holds to that order.

Some rules say every A must come before every B.

Example 1

Input:

s = "aaabbb"

Output:

true

Example 2

Input:

s = "aabba"

Output:

false

Worked solution and explanation

What this really is

This is a two-state machine wearing a validation costume. There is a boundary in the string: the first 'b'. Before it, life is easy; after it, a single 'a' is fatal. The skill being probed is whether you read the rule as positional and carry one bit of state through a left-to-right scan. The trap is candidates who count a's and b's or compare against the sorted string: those throw away position, so they wave 'aabba' through the same as 'aaabbb'. Miss the boundary and you accept logs that are genuinely out of order.

Break down the requirements

Step 1: Track whether a 'b' has been seen

Keep a boolean that flips to True the first time you see a 'b'. That flag is the entire state machine; you never need to look backward.

Step 2: After 'b' appears, reject any 'a'

Once the flag is True, an 'a' is a violation. Return False the instant you find one so you stop scanning the rest of the string.

Step 3: Ignore everything else, then accept

Any character that is neither 'a' nor 'b' is invisible to the rule; skip it. If the scan finishes with no violation, the log is valid, and an empty string trivially reaches that True.

The solution

State flag scan for ordering violation
def validate_ab_string(s: str) -> bool:
    seen_b = False
    for ch in s:
        if ch == 'b':
            seen_b = True
        elif ch == 'a' and seen_b:
            return False
    return True

Common follow-up questions