Katkat
Back

Find best-matching binary pattern with wildcards

GoogleSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to efficiently match a query string against a dictionary of patterns containing wildcards and determine the best match based on predefined precedence rules.

Problem Description

Given a dictionary of patterns (strings containing '0', '1', and the wildcard '?') and a query string (consisting of '0' and '1'), find the best matching pattern. A pattern matches the query if every character in the pattern is either equal to the corresponding character in the query or is a '?'.

If multiple patterns match, the 'best' match is defined by these criteria in order:

  1. The match with the fewest wildcards ('?') used in the pattern.
  2. If there is still a tie, choose the pattern that appeared earliest in the provided patterns list.

Function Signature

def find_best_match(patterns: list[str], query: str) -> str:
    # Returns the best matching pattern or None if no match exists

Examples

Example 1:

  • patterns: ["0?1", "1?1", "011"]
  • query: "011"
  • Result: "011"
  • Explanation: Both "0?1" and "011" match. "011" has 0 wildcards, while "0?1" has 1. Thus, "011" is better.

Example 2:

  • patterns: ["0?0", "?10"]
  • query: "000"
  • Result: "0?0"
  • Explanation: Both match. Both have 1 wildcard. "0?0" appears first in the list.

Constraints

  • len(patterns) <= 10,000
  • len(query) = 1).

Hints

Hint 1

A brute-force approach compares the query against every pattern; consider if this is sufficient given the constraints or if a pre-processing step is needed.

Hint 2

For the tie-breaking rule, ensure you track both the wildcard count and the original index of each pattern.

Hint 3

If the number of patterns is large and you need to perform multiple queries, consider if a Trie or a bitmask-based approach could optimize the matching process.

Follow-up questions

  • How would your solution change if the patterns were of variable lengths?
  • If you had to process 1 million queries against the same set of patterns, how would you optimize the system for performance?
  • What if the wildcard '?' represented a match for '0' or '1' but had an associated cost, and you wanted to minimize the total cost rather than just the count of wildcards?