0

Grep with context lines

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Grep with context lines

Companies: Google, Snowflake

Difficulty: Medium

Problem statement

Implement a simplified grep. You get a list of text lines, a search string target, and a non-negative integer k. Return every line that contains target, together with up to k lines before it and up to k lines after it.

def grep_with_context(lines: list[str], target: str, k: int) -> list[str]: ...

Rules:

  • A line matches if target appears anywhere in it as a case-sensitive substring, including inside a longer word. "log" matches "catalog" but not "LOG".
  • Context windows stop at the start and end of the input.
  • Each line appears at most once in the result, even if it is in the context of several matches.
  • The result keeps the original line order.

Constraints: 0 <= len(lines) <= 10^5, each line up to 10^3 characters, 0 <= k <= 10^5.

Example 1

lines  = ["boot ok", "disk warn", "net ok", "cpu ok", "fan warn", "done"]
target = "warn", k = 1
output = ["boot ok", "disk warn", "net ok", "cpu ok", "fan warn", "done"]

The windows are lines 0-2 and 3-5. Together they cover every line, each once.

Example 2

lines  = ["a", "bx", "c", "d", "e", "fx", "g"]
target = "x", k = 0
output = ["bx", "fx"]

Be ready for follow-ups: different before/after counts, a -- separator between groups, and input too large to hold in memory.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Clarify first. The input is a list of lines, a pattern, and a context size k. Return every line that matches, plus up to k lines before and after each match. Pin down these points before coding:

  • Matching is a case-sensitive substring test. "err" matches "stderr" and "error", but not "ERR". There is no regex and no whole-word rule unless the interviewer adds one.
  • No duplicates. A line inside the context of two matches appears once.
  • Original order. The output keeps the document order. It is not grouped per match.
  • Edges. Context windows are clipped at the first and last line. k = 0 means "matches only". An empty pattern matches every line (Python's "" in s is True). Ask whether that is what they want.

Brute force. For each match at index i, add every index in [i - k, i + k] to a set. Then sort the set and return those lines. This is correct, but a dense file with a large k touches each line up to 2k + 1 times, so the cost is O(n * k) plus a sort.

Optimal: one forward pass with a high-water mark. Matches are found in increasing order, so their windows start in increasing order too. Keep next_out, the first index not yet written to the output. For a match at i:

  1. The window is [max(0, i - k), min(n - 1, i + k)].
  2. Start writing at max(window_start, next_out), so nothing already written is written again.
  3. Write up to the window end, then set next_out = window_end + 1.

This is the "merge overlapping intervals" idea, done on the fly. Because windows arrive sorted by start, a single cursor is enough. No set and no sort are needed.

Invariant. After a match at i is handled, the output is exactly the sorted, de-duplicated union of the windows of all matches up to i, and next_out is one past the last index written. Each line is written at most once, so the output work is O(n) no matter how large k is.

Streaming version (common Part 2). If the input is a stream or a huge file, keep only the last k lines in a deque (the "before" buffer) and a counter after_left of trailing lines still owed. On a match, flush the deque, write the line, and set after_left = k. On a non-match, write the line if after_left > 0 and decrement; otherwise push it into the deque. A line in the deque was never written, and a written line is never pushed, so there are no duplicates. Memory is O(k) lines.

Code

from __future__ import annotations

from collections import deque
from typing import Iterable, Iterator


def grep_with_context(lines: list[str], target: str, k: int) -> list[str]:
    """Return matching lines plus up to k lines of context, each line once, in order."""
    if k < 0:
        raise ValueError("k must be non-negative")
    n = len(lines)
    result: list[str] = []
    next_out = 0  # first index not yet written
    for i, line in enumerate(lines):
        if target not in line:
            continue
        start = max(i - k, next_out)
        end = min(n - 1, i + k)
        result.extend(lines[start:end + 1])
        next_out = end + 1
    return result


def grep_stream(
    lines: Iterable[str], target: str, before: int, after: int,
    separator: str | None = None,
) -> Iterator[tuple[int, str]]:
    """Streaming grep with -B/-A context and O(before) memory.

    Yields (line_number, text). If separator is set, yields (-1, separator)
    between groups that are not adjacent, like grep's "--".
    """
    buf: deque[tuple[int, str]] = deque(maxlen=before)
    after_left = 0
    last_written = -2  # index of the last line written; -2 means none yet
    for idx, line in enumerate(lines):
        if target in line:
            pending = list(buf) + [(idx, line)]
            buf.clear()
            after_left = after
        elif after_left > 0:
            pending = [(idx, line)]
            after_left -= 1
        else:
            buf.append((idx, line))
            continue
        for j, text in pending:
            if separator is not None and last_written >= 0 and j != last_written + 1:
                yield (-1, separator)
            yield (j, text)
            last_written = j


if __name__ == "__main__":
    doc = ["alpha", "beta error", "gamma", "delta", "epsilon", "zeta error", "eta", "theta"]
    assert grep_with_context(doc, "error", 1) == [
        "alpha", "beta error", "gamma", "epsilon", "zeta error", "eta"]
    assert grep_with_context(doc, "error", 2) == doc  # windows overlap and merge
    assert grep_with_context(doc, "error", 0) == ["beta error", "zeta error"]
    assert grep_with_context(doc, "Error", 3) == []  # case-sensitive
    assert grep_with_context([], "x", 5) == []
    assert grep_with_context(["ab", "cab", "d"], "ab", 0) == ["ab", "cab"]
    assert grep_with_context(["a", "b", "x", "c"], "x", 100) == ["a", "b", "x", "c"]
    assert grep_with_context(["x", "x", "x"], "x", 1) == ["x", "x", "x"]
    out = list(grep_stream(doc, "error", 1, 1, separator="--"))
    assert [t for _, t in out] == [
        "alpha", "beta error", "gamma", "--", "epsilon", "zeta error", "eta"]
    out = list(grep_stream(doc, "error", 0, 2))
    assert [i for i, _ in out] == [1, 2, 3, 5, 6, 7]
    for k in range(5):  # stream matches the list version on symmetric context
        assert [t for _, t in grep_stream(doc, "error", k, k)] == grep_with_context(doc, "error", k)
    print("ok")

Complexity

Let n be the number of lines, L the average line length, m the pattern length, and R the number of lines returned.

  • grep_with_context: the match test is O(L) on average with Python's substring search (O(L * m) worst case for a naive search; O(L + m) with KMP). Total time O(n * L) for matching plus O(R) for output. Each line is copied into the output at most once, so the output cost does not depend on k. Extra space O(1) beyond the O(R) result.
  • Brute force with a set: O(n * L + M * k + R log R), where M is the number of matches, and O(R) extra space for the set.
  • grep_stream: O(L) per line, O(before) lines of memory for the buffer, results produced as soon as each line is decided.

Test cases

Using doc = ["alpha", "beta error", "gamma", "delta", "epsilon", "zeta error", "eta", "theta"], target "error":

  • k = 1 -> ["alpha", "beta error", "gamma", "epsilon", "zeta error", "eta"] (two separate groups; "delta" and "theta" are left out).
  • k = 2 -> the whole document. The windows [0, 3] and [3, 7] share "delta", which appears once.
  • k = 0 -> ["beta error", "zeta error"].
  • Target "Error" -> [] (case-sensitive).
  • Empty input [] -> [].
  • ["ab", "cab", "d"], target "ab", k = 0 -> ["ab", "cab"] (substring inside a longer word counts).
  • ["a", "b", "x", "c"], target "x", k = 100 -> all four lines (window clipped at both ends).
  • ["x", "x", "x"], k = 1 -> ["x", "x", "x"] (adjacent matches, every line once).
  • Streaming with before = 1, after = 1, separator "--" -> alpha, beta error, gamma, --, epsilon, zeta error, eta.
  • Streaming with before = 0, after = 2 -> line indices 1, 2, 3, 5, 6, 7.

Follow-ups

  1. Different before and after counts (-B and -A). Use window [i - before, i + after] in the list version. In the stream version the deque size is before and the counter resets to after. Nothing else changes.
  2. Group separators and line numbers. Print -- between groups that are not adjacent, and prefix each line with its number (12: for a match, 12- for context, as real grep does). Track the last index written; a gap means a new group. grep_stream above already does the separator.
  3. Input too large for memory, or a live stream (tail -f | grep). Use the streaming version: O(before) memory, and each line is emitted as soon as it is known to be in or out. Discuss that "after" lines can be emitted immediately, while "before" lines must be buffered because you cannot know yet whether they will be needed.
  4. Faster or richer matching. For a long pattern or many lines, precompute a KMP failure table once and reuse it, so each line is O(L) worst case. For several patterns, use Aho-Corasick. For regex, compile once. For case-insensitive search, compare casefold() versions, and ask about Unicode.
  5. Many files or a very large file in parallel. Split the file into chunks and grep each in parallel, but each chunk must also read before lines from the previous chunk and after lines from the next, or windows that cross a boundary are wrong. Merge the per-chunk outputs by line number and remove overlaps at the seams.

Interviewer expectations

Mid-level (L4)

  • Asks about case sensitivity, duplicates, order, and window clipping before coding.
  • Gets a correct answer, even with a set plus sort, and handles k = 0, empty input, and matches near the edges.
  • Walks through an example where two windows overlap and shows each line appears once.

Senior (L5)

  • Sees that windows arrive sorted and merges them with one cursor, with no set and no sort, and states the invariant.
  • Gives the complexity in terms of n, L, and output size, and explains why it does not depend on k.
  • Moves to the streaming version with a bounded deque when asked about large input, and handles -A/-B and separators cleanly.

Staff (L6+)

  • Talks about the substring-search choice (built-in vs KMP vs Aho-Corasick vs regex) and when each matters.
  • Designs a chunked parallel grep with correct handling of context across chunk boundaries.
  • Discusses real-world details: encodings, very long lines, binary files, output buffering, and the latency of live streams.

Sign in to comment, vote or remix.