Stream output until stop token appears
Quick Overview
This question evaluates streaming string processing and pattern-matching skills, specifically handling token detection across chunk boundaries, boundary conditions, and time/space efficiency. It is commonly asked in the Coding & Algorithms domain to assess practical application-level competence in stream-processing algorithms rather than purely theoretical understanding.
You are implementing a simplified streaming conversational AI output filter.
Text arrives in chunks (strings) in order. There is a special stop token (e.g., "<END>"). Your job is to output only the text that occurs before the first stop token, and ignore everything from the stop token onward.
Task
Given:
-
chunks: a list of strings representing the stream chunks in arrival order -
stopToken: a non-empty string (e.g.,"<END>")
Return a list of strings representing what should be emitted to the user:
-
Emit all content
before
the first occurrence of
stopToken. -
Do
not
include
stopTokenitself. -
If
stopTokenoccurs in the middle of a chunk, emit only the prefix before it. - Once the stop token is detected, ignore all remaining input.
Examples
- Stop token fully contained in a chunk:
-
chunks = ["hello", "how are you<END>", "HAPPY"] -
Output:
["hello", "how are you"]
- Stop token may be split across chunk boundaries (truncated in one chunk and completed in the next):
-
chunks = ["hello", "how are you<E", "ND>HAPPY"] -
Output:
["hello", "how are you"]
Requirements / Constraints
- Treat input as a stream: you should not rely on concatenating the entire stream into one giant string.
- Aim for O(total characters) time.
-
Extra space should be small (e.g., proportional to
len(stopToken)).
(You may assume ASCII/UTF-8 strings; exact character set is not important as long as matching is consistent.)