Implement Prefix Match Filter

Q: Implement Prefix Match Filter

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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:

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

Implement Prefix Match Filter

Quick Overview

Comments (0)