Katkat
Back

Implement Prefix Match Filter

DatadogSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of prefix-based string matching, data structure design (hash-based sets and trie/prefix tree), and algorithmic competencies including efficient in-memory storage and deduplication of matches.

Design a data structure that stores a collection of prefix strings. Then, given a list of input strings, return every string that begins with at least one stored prefix.

Requirements:

  • Support addPrefix(prefix) to store a prefix.
  • Support checking whether a given string matches any stored prefix.
  • Given a list of strings, output each matching string exactly once, even if multiple prefixes match it.

Example:

  • Stored prefixes: ["ab", "cat", "pre"]
  • Input strings: ["abc", "dog", "prefix", "cater", "zoo"]
  • Output: ["abc", "prefix", "cater"]

Follow-up:

  1. First discuss or implement a straightforward hash-based approach.
  2. Then optimize the solution using a trie (prefix tree).
  3. Compare the time and space complexity of both approaches.