Implement string matching with follow-up
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given a text T and a pattern P, implement a function firstIndex(T, P) that returns the starting index of the first occurrence of P in T, or -1 if absent. Aim for O(|T| + |P|) time and O(|P|) extra space. Discuss how you would handle Unicode and very long inputs. Follow-up: extend your solution to support searching for k patterns P1..Pk simultaneously and return all starting indices for each pattern; outline the data structure and runtime trade-offs.
Quick Answer: This question evaluates understanding of efficient string-matching techniques, handling of Unicode and very long inputs, and design of data structures for simultaneous multi-pattern search, within the Coding & Algorithms domain.