Coding - Grep With Context Lines

The Grep with Context Lines problem is a classic software engineering interview question, frequently reported in technical screens for companies like xAI and Verily. It tests your ability to handle data streams, manage memory efficiently, and handle overlapping output ranges. 0 1 2

1. Problem Statement

Implement a simplified version of the Unix grep command that supports the context flag (-C or --context).

• Input: lines: A stream or array of strings representing a document. pattern: The target string or regex to search for. k: An integer representing the number of lines of context to show before and after each match.
• Output: Print (or return) every line that matches the pattern, along with the k lines immediately preceding it and the k lines immediately following it.
• Constraint: If context windows for two different matches overlap, they should be merged into a single continuous block of output to avoid printing the same line multiple times.

2. Implementation Strategy (Online Algorithm)

When implemented as an online algorithm (processing lines one by one), the challenge is that you don't know if a line needs to be printed until you see a match later, or you might need to keep printing lines after a match has already passed. Glassdoor +1 1 2

Step 1: Manage "Before" Context

Use a Circular Buffer (or a Deque) of size k to store the most recent lines. When a match is found, print all lines currently in the buffer.

Step 2: Manage "After" Context

Maintain a counter lines_to_print. When a match is found, set this counter to k. While the counter is >0is greater than 0>0, continue printing every incoming line and decrement the counter.

Step 3: Handle Overlaps

If a new match is found while the lines_to_print counter is still active, simply reset the counter to k. This naturally merges the context windows without duplicate printing.

3. Common Follow-ups at xAI

Interviewers at xAI often extend this problem to test system-level thinking: 0

• Streaming Input: How do you handle a file too large to fit in memory? (Requires the circular buffer approach mentioned above).
• Multithreading: How would you parallelize the search if you have a massive file and a multi-core machine? (Divide the file into chunks, but be careful with matches near the chunk boundaries).
• Large Context (kk𝑘): If kk𝑘 is very large, a simple buffer might be inefficient. How would you optimize storage?

Answer

The core of the problem is implementing a sliding window (usually via a circular buffer) to track preceding lines and a counter to track succeeding lines, ensuring that overlapping blocks are merged into a single output stream.

How would you like to handle extremely large files where the context kk𝑘 might exceed available RAM?

[0] - Grep With Context Lines | 1Point3Acres [1] - Implement grep with context as an online algorithm. - Glassdoor [2] - Implement grep with context as an online algorithm. - Glassdoor