LLM-Oriented String Processing (Technical Phone Screen)

Problem: LLM-Oriented String Processing (Phone Screen) You are given a multi-line conversation text. Implement a post-processing pipeline and extract structured messages. Rules (apply in order) Remove any <<...>> segments (internal markers). Markers can appear anywhere within a single line but never span multiple lines. Collapse consecutive spaces/tabs into a single space. Trim leading/trailing whitespace for each line. Remove empty lines. Parse lines of the form role: content, where role is one of user/assistant/system (case-insensitive). Normalize role to lowercase. Output Return a list of (role, content) tuples in appearance order. Constraints 1 <= |text| <= 2e5 <= 2e4 lines Must run in O(n) time Example Input: System: You are helpful. <<internal>> USER:\tHi there assistant: Hello!<<meta>> How can I help? Output: [("system", "You are helpful."), ("user", "Hi there"), ("assistant", "Hello! How can I help?")] Example Input System: You are helpful. <<internal>> USER: Hi there assistant: Hello!<<meta>> How can I help? Output [("system", "You are helpful."), ("user", "Hi there"), ("assistant", "Hello! How can I help?")]