Q3 - The Log Extractor (Glob Matching with Captures)

Scenario: You are building a tiny log tool. A pattern is literal text with * wildcards, where * matches any run of characters (including none). A line matches when the whole line fits the pattern, and for each * you want to know exactly what it matched. This is the idea behind grep and shell globs, plus capture.

Part 1. Implement extract(pattern, line). If the line matches, return the list of substrings the *s captured, left to right; otherwise return no match. The pattern uses only literal characters and *.

extract(pattern, line):

  extract("ERROR: *", "ERROR: disk full")     ->  ["disk full"]
  extract("GET /*/watch", "GET /movie/watch")  ->  ["movie"]
  extract("a*b", "axyb")                       ->  ["xy"]
  extract("a*b", "axy")                        ->  no match   (the line does not end in "b")
  extract("*.log", "app.log")                  ->  ["app"]    a leading * captures the front
  extract("a*a", "aa")                         ->  [""]       the * matched nothing: an empty capture

  extract("[*] user=* did *", "[2024-01-01] user=amy did login")
      ->  ["2024-01-01", "amy", "login"]

Part 1: Split, Anchor, Scan

Three moves turn the pattern into captures: split it on the stars, pin the two ends, then walk the middle.

Step 1: Split the pattern on *

Splitting the pattern on * gives its literal segments. n stars produce n + 1 segments, and there is exactly one capture per star. The only subtlety is the ends: a * at the very start or end leaves an empty segment, and since the empty string is a prefix and a suffix of everything, those cases fall out for free once you split, with no special casing.

"[*] user=* did *"  ->  ["[", "] user=", " did ", ""]     3 stars -> 4 segments, 3 captures
"*.log"             ->  ["", ".log"]                       leading *  -> empty first segment
"GET *"             ->  ["GET ", ""]                       trailing * -> empty last segment
"*"                 ->  ["", ""]                           just a star -> two empty segments
"hello"             ->  ["hello"]                          no star -> the line must equal it

segments = pattern.split("*")     # "a*b*c" -> ["a", "b", "c"];  "*x" -> ["", "x"]
# n stars give n + 1 segments and n captures; the first and last segments will anchor the ends

Step 2: Anchor the first and last segments

The first segment must be a prefix of the line, and the last a suffix. If either fails, there is no match. This also fixes the region the captures live in: everything between the end of the first segment and the start of the last. Track it with two indices, pos (the first free character) and end (one past the last free character).

line = "[2024-01-01] user=amy did login"

  first segment "["   must start the line   ->  ok,  pos = 1
  last segment  ""    must end the line      ->  ok,  end = 31   (empty suffix always matches)
  every capture lives inside line[pos .. end] = line[1 .. 31]

when the ends do not line up, stop right here:
  extract("GET *", "POST /x")  ->  "GET " is not a prefix of "POST /x"  ->  no match

first, last = segments[0], segments[-1]
if not line.startswith(first) or not line.endswith(last):
    return None                    # the two ends do not line up, so nothing can match
pos = len(first)                   # first free index, just past the anchored prefix
end = len(line) - len(last)        # one past the last free index, before the anchored suffix

Step 3: Scan the middle segments, capturing the gaps

Walk the middle segments in order. For each, find its next occurrence at or after the current position; the text you skipped is that *'s capture. Take each literal at its leftmost match: because the tail is already pinned to the end of the line, grabbing a literal early never blocks a later one, so there is nothing to backtrack. The final * takes whatever remains before the last anchor.

pos = 1
  find "] user=" from 1  ->  at 11;  capture 1 = line[1:11]  = "2024-01-01",  pos = 18
  find " did "   from 18 ->  at 21;  capture 2 = line[18:21] = "amy",         pos = 26
  the last * takes the rest         capture 3 = line[26:31] = "login"

# each middle literal, left to right
for seg in segments[1:-1]:
    idx = line.find(seg, pos)
    if idx == -1 or idx + len(seg) > end:
        # a required literal is missing
        return None
    # the gap before it is this *'s capture
    captures.append(line[pos:idx])
    pos = idx + len(seg)

Watch the pattern lock onto the line: the literals (blue) snap to their positions and the gaps between them (green) become the captures:

1 / 6

# O(n * m) worst case | O(number of captures) extra space
def extract(pattern, line):
    # n stars -> n + 1 literal segments
    segments = pattern.split("*")
    # no wildcard: it must match exactly
    if len(segments) == 1:
        return [] if line == pattern else None
    first, last = segments[0], segments[-1]
    # the first and last literals are anchored to the ends of the line
    if not line.startswith(first) or not line.endswith(last):
        return None
    pos = len(first)
    end = len(line) - len(last)
    # the two anchors overlap
    if pos > end:
        return None
    captures = []
    # each middle literal, left to right
    for seg in segments[1:-1]:
        idx = line.find(seg, pos)
        if idx == -1 or idx + len(seg) > end:
            return None
        # the gap before it is this *'s capture
        captures.append(line[pos:idx])
        pos = idx + len(seg)
    # the last * takes the remainder
    captures.append(line[pos:end])
    return captures

Part 2: Add the ? Wildcard

Extend the tool with ?, which matches exactly one character (any character) and is not captured. So user=??? matches user=amy but not user=al.

extract(pattern, line):

  extract("user=??? *", "user=amy did login")  ->  ["did login"]
  extract("a?c", "abc")                         ->  []          (matches, but ? captures nothing)
  extract("a?c", "ac")                          ->  no match    (? needs one character)
  extract("*.???", "file.log")                  ->  ["file"]

With ? inside the segments, plain string equality and find no longer work. Replace them with a ?-aware check: a segment matches at a position when every character lines up, treating ? as a match for anything. Everything else, anchor the two ends and scan the middle for its leftmost match, stays exactly the same.

does "a?c" match at position p?   compare char by char, ? matches anything

  "a?c" at "abc"[0..3]:  a==a, ?==b (ok), c==c   ->  yes
  "a?c" at "aXc"[0..3]:  a==a, ?==X (ok), c==c   ->  yes
  "a?c" at "abd"[0..3]:  a==a, ?==b (ok), c!=d   ->  no

def matches_at(line, pos, seg):
    # does seg (with ? matching any char) sit exactly at line[pos:]?
    if pos < 0 or pos + len(seg) > len(line):
        return False
    return all(pc == "?" or pc == lc for pc, lc in zip(seg, line[pos:pos + len(seg)]))

Here is matches_at walking the tiny example a?c against abc column by column, the one subtlety that trips people up (? needs a character), and the same check running inside the full extract on a real log line:

1 / 7

def matches_at(line, pos, seg):
    # does seg (with ? matching any char) sit exactly at line[pos:]?
    if pos < 0 or pos + len(seg) > len(line):
        return False
    return all(pc == "?" or pc == lc for pc, lc in zip(seg, line[pos:pos + len(seg)]))

def extract(pattern, line):
    segments = pattern.split("*")
    # no *: the whole pattern must match at 0
    if len(segments) == 1:
        return [] if len(line) == len(pattern) and matches_at(line, 0, pattern) else None
    first, last = segments[0], segments[-1]
    if not matches_at(line, 0, first) or not matches_at(line, len(line) - len(last), last):
        return None
    pos = len(first)
    end = len(line) - len(last)
    if pos > end:
        return None
    captures = []
    for seg in segments[1:-1]:
        idx = -1
        # leftmost position where seg matches
        for p in range(pos, end - len(seg) + 1):
            if matches_at(line, p, seg):
                idx = p
                break
        if idx == -1:
            return None
        captures.append(line[pos:idx])
        pos = idx + len(seg)
    captures.append(line[pos:end])
    return captures

Complexity Analysis

• Time: O(n * m) worst case, where n is the line length and m the pattern length. Each middle segment is searched for from left to right, and in the worst case (many near-misses of a long segment) each search scans much of the line. In practice, with distinctive literals between the stars, it is close to linear.
• The ? version has the same bound. The only change is a per-position character check instead of a library find, which does not change the asymptotics.
• Space: O(number of captures), one string per *. Beyond the output, the matcher keeps only a couple of indices, no recursion and no DP table.
• Why no backtracking is needed: because the last literal is anchored to the end, each middle literal can safely take its leftmost match. Grabbing it as early as possible leaves the most room for the literals that follow, so a greedy left-to-right scan never has to undo a choice.

Final Notes

1. Split on the wildcard first. The instinct is to write a character-by-character matcher. Resist it: splitting on * turns a fuzzy pattern into a list of hard literals, and the whole problem becomes "line these literals up in order."
2. Anchor both ends, then the middle is free. The first segment is a prefix, the last a suffix. Say that out loud before you code; it is what makes the middle scan a simple left-to-right walk with no backtracking.
3. Leftmost is safe here, and be ready to say why. Because the tail is pinned to the end of the line, taking each middle literal at its earliest position never blocks a later one. That one sentence is the difference between guessing and knowing your greedy is correct.
4. Name the empty-segment cases. A pattern that starts or ends with * gives an empty first or last segment, and an empty segment is a prefix and suffix of everything. Handling that falls out for free once you split, but calling it out shows you thought about the edges.
5. Keep ? a one-line change. Swapping the exact-match check for a ?-aware one is all Part 2 needs. Designing Part 1 so a single helper is the only thing that changes is the kind of structure an interviewer notices.