eBay·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

eBay Software Engineer coding round, one algorithmic problem about wildcard pattern matching against a dictionary. Pretty focused session, no fluff, just the problem and complexity analysis at the end.

Questions Asked (1)

Given a dictionary of words and a pattern string containing lowercase letters, '?' (matches exactly one character), and '.' (matches one or more characters), return all words from the dictionary that fully match the pattern. Also explain your approach to handling the variable-length '.' token and report your overall time complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The '?' part was fine, that's basically just length-checking a slot.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and edge cases, then propose a dynamic programming solution that handles '?' and '.' by tracking pattern positions and word indices. Explain how DP states represent whether a prefix of the pattern matches a prefix of the word, and how '.' transitions consume one or more characters. Finally, analyze the time complexity as O(N * L * M) where N is dictionary size, L is average word length, and M is pattern length.

Pro tip: Mention that you can optimize by pre-grouping words by length and only checking words whose length falls within the min/max possible lengths determined by the pattern, reducing unnecessary DP computations.

1. Clarify requirements and edge cases

Ask about pattern constraints, empty strings, case sensitivity, and whether '.' can match zero characters (it matches one or more). Confirm that the entire word must match the entire pattern.

2. Define DP state and transitions

Let dp[i][j] be true if the first i characters of the word match the first j characters of the pattern. For a letter or '?', transition from dp[i-1][j-1] if characters match. For '.', transition from any dp[k][j-1] where k < i (since '.' consumes one or more characters).

3. Implement and optimize DP

Use a 2D boolean array or two 1D arrays for space optimization. For '.', instead of iterating over all k, maintain a running OR of previous states to achieve O(1) transition per cell.

4. Iterate over dictionary and collect matches

For each word, run the DP and if dp[word.length][pattern.length] is true, add the word to the result list. Optionally, pre-filter words by length bounds derived from the pattern.

5. Analyze time and space complexity

Time: O(N * L * M) where N is number of words, L is max word length, M is pattern length. Space: O(L * M) for DP table, or O(M) with optimized 1D arrays. Mention that pre-filtering can reduce N.

Key Points to Mention

Dynamic programming state definition and transitions for '?' and '.'
Handling variable-length '.' by allowing transitions from any previous position (or using running OR for optimization)
Time complexity O(N * L * M) and space complexity O(L * M) or O(M) with optimization
Edge cases: empty pattern, empty word, pattern with only '.', word shorter than minimum possible length
Optimization: pre-filter words by length bounds (min length = number of non-'.' tokens, max length = infinity if '.' present, else exact length)
Alternative approaches: recursion with memoization, or converting pattern to regex (but note performance implications)

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.