Katkat
Back

Implement string matching with follow-up

DoorDashSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

A DoorDash software-engineer coding screen on string matching: implement firstIndex(T, P) in O(|T| + |P|) time and O(|P|) space using KMP, then handle follow-ups on naive vs KMP vs Rabin–Karp, Unicode and very long inputs, edge cases, wildcard ('?'/'*') matching, and simultaneous multi-pattern search via Aho–Corasick. Includes corrected, complete solutions and complexity trade-offs.

Question

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 P does not occur. Aim for O(|T| + |P|) time and O(|P|) extra space.

Be ready to extend the solution through the following follow-ups:

  1. Algorithm comparison. Compare the naive (brute-force) approach to KMP and Rabin–Karp. Explain the time and space complexity of each and when you would choose one over another.
  2. Robustness. How would you handle Unicode text (multi-byte / combining characters) and very long inputs? Discuss correctness and memory considerations.
  3. Edge cases. Walk through the important edge cases: empty pattern, empty text, pattern longer than text, and highly repetitive patterns (e.g. P = "aaaa" in T = "aaaaaa").
  4. Wildcards. Extend the matcher to support two wildcard characters in the pattern: ? matches any single character, and * matches any (possibly empty) sequence of characters. Describe the matching semantics and complexity.
  5. Multi-pattern search. Extend the solution to search for k patterns P1..Pk in T simultaneously and return all starting indices for each pattern. Outline the data structure you would use and the runtime / space trade-offs versus running a single-pattern matcher k times.