How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find best-matching binary pattern with wildcards

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

## Problem You are building a rule engine that maps an input binary string to a configuration value. You are given a list of rules in **priority order** (earlier rules have higher priority). Each rule is: - **pattern**: a string consisting of characters: - `'0'` matches the character `0` - `'1'` matches the character `1` - `'*'` matches **any binary substring of any length**, including the empty substring (i.e., like regex `.*`) - (optional, if present) `'.'` matches **exactly one** binary character (`0` or `1`) - **value**: an associated identifier to return (integer/string) Given an input string `s` (containing only `0` and `1`), implement a function: ```text match(s) -> value | null ``` that returns the value of the **best** rule that matches `s`. ### Best-rule selection 1. Prefer the matching rule with the **longest pattern string length** (number of characters in the pattern, counting `*` as one character). 2. If multiple matching rules have the same maximum length, choose the one that appears **earliest** in the original rules list. 3. If no rule matches, return `null`. ### Example Rules (in order): 1. `"10*1" -> A` 2. `"0*" -> B` 3. `"*11" -> C` Queries: - `match("10001")` matches rule 1 (`"10" + "00" + "1"`), returns `A`. - `match("01110")` matches rule 2, returns `B`. - `match("111")` matches rule 3 (`"" + "11"` after matching the first `1` via `*`), returns `C`. ## What to implement Design an API that supports: - **Preprocess**: ingest the list of `(pattern, value)` rules once. - **Query**: answer `match(s)`. State any assumptions and target time complexity for preprocessing and per-query matching (e.g., handle many queries efficiently).

Quick Answer: This question evaluates pattern-matching and string-algorithm skills, including handling wildcards and variable-length matches, priority-based rule selection, and the design of preprocessing and query-time data structures.

You are given a list of rules in original priority order. Each rule is a pair (pattern, value), where value is a string identifier and pattern contains only '0', '1', '*', and optionally '.'. A pattern matches an entire binary query string if: '0' matches only '0', '1' matches only '1', '.' matches exactly one binary character, and '*' matches any binary substring of any length, including the empty substring. Among all matching rules, choose the one with the longest original pattern length. If multiple matching rules have the same maximum length, choose the one that appeared earlier in the original rules list. If no rule matches, return None for that query. Consecutive '*' characters are allowed; they behave like a single '*' for matching, but every '*' still counts toward the original pattern length used for tie-breaking. Implement solution(rules, queries), which preprocesses the rules once and returns the best match for every query string.

Constraints

1 <= len(rules) <= 500
1 <= len(queries) <= 500
1 <= len(pattern) <= 500
0 <= len(query) <= 500
Sum of all pattern lengths <= 2 * 10^4
Sum of all query lengths <= 2 * 10^4
Each pattern contains only '0', '1', '*', and '.'
Each query contains only '0' and '1'

Examples

Input: ([('10*1', 'A'), ('0*', 'B'), ('*11', 'C')], ['10001', '01110', '111', '101'])

Expected Output: ['A', 'B', 'C', 'A']

Explanation: '10001' matches '10*1', '01110' matches '0*', '111' matches '*11', and '101' matches '10*1' with '*' taking the empty substring.

Input: ([('1.0', 'X'), ('10*', 'Y'), ('1*0', 'Z')], ['110', '1000'])

Expected Output: ['X', 'Y']

Explanation: For '110', both '1.0' and '1*0' match and both have length 3, so the earlier rule '1.0' wins. For '1000', both '10*' and '1*0' match with the same length, so the earlier rule '10*' wins.

Input: ([('.', 'ONE'), ('*', 'ANY'), ('0', 'ZERO')], ['', '0', '1'])

Expected Output: ['ANY', 'ONE', 'ONE']

Explanation: The empty string is matched only by '*'. For '0' and '1', both '.' and '*' match with length 1, so the earlier rule '.' wins.

Input: ([('1*0', 'SHORT'), ('1**0', 'LONGER'), ('1.0', 'DOT')], ['10', '110'])

Expected Output: ['LONGER', 'LONGER']

Explanation: Both '1*0' and '1**0' match these queries, but the original pattern '1**0' has length 4, so it beats '1*0' with length 3.

Input: ([('01', 'A'), ('1.1', 'B')], ['0', '1110'])

Expected Output: [None, None]

Explanation: Neither query fully matches any rule.

Hints

If you sort rules by (-original_pattern_length, original_index), then the first rule that matches a query is automatically the correct answer.
Use the classic greedy wildcard matcher with two pointers and the most recent '*' position. Treat '.' the same way you would treat a single-character wildcard.

Quick Overview

This question evaluates pattern-matching and string-algorithm skills, including handling wildcards and variable-length matches, priority-based rule selection, and the design of preprocessing and query-time data structures.