Service Now·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

ServiceNow SWE interview with a dynamic programming problem on wildcard pattern matching. Pretty standard algorithmic round, nothing too surprising, but the problem had some tricky edge cases that caught me slipping.

Questions Asked (1)

Implement wildcard pattern matching between a string and a pattern that supports '?' (matches any single character) and '*' (matches any sequence of characters), where the pattern must cover the entire input string.

Algorithms & Data Structures

Author's notes

I jumped straight to recursion and got a working solution but it was obviously exponential.

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 with O(m*n) time and space, and finally discuss potential optimizations like using two pointers for linear space. Walk through a few examples to demonstrate correctness and handle tricky cases like multiple consecutive '*'.

Pro tip: Mention that you can optimize the DP space to O(n) by using two rows, and that greedy two-pointer approach works for this specific wildcard matching (unlike regex) because '*' is independent. This shows deeper understanding and practical optimization skills.

1. Clarify requirements and edge cases

Ask about input constraints, character set, and whether the pattern can be empty. Discuss edge cases like empty string, empty pattern, patterns with only '*', and consecutive '*'.

2. Define DP state and recurrence

Define dp[i][j] as whether the first i characters of string match the first j characters of pattern. Derive recurrence: if pattern[j-1] is '?' or matches string[i-1], dp[i][j] = dp[i-1][j-1]; if pattern[j-1] is '*', dp[i][j] = dp[i-1][j] (match one char) or dp[i][j-1] (match empty).

3. Implement DP with base cases

Initialize dp[0][0] = true, dp[0][j] = dp[0][j-1] if pattern[j-1] is '*', and dp[i][0] = false for i>0. Fill the table iteratively and return dp[m][n].

4. Analyze complexity and optimize space

State time complexity O(m*n) and space O(m*n). Propose space optimization to O(n) using two rows or O(1) with greedy two-pointer approach, explaining the trade-offs.

5. Test with examples and discuss alternatives

Walk through examples like s='adceb', p='*a*b' and s='acdcb', p='a*c?b'. Mention greedy two-pointer algorithm as an alternative with O(m+n) time and O(1) space, and discuss when to use which.

Key Points to Mention

Dynamic programming state definition and recurrence relation
Base case initialization for empty string and pattern
Handling of '?' and '*' characters in recurrence
Time and space complexity analysis (O(m*n) time, O(m*n) or O(n) space)
Greedy two-pointer approach for O(m+n) time and O(1) space
Edge cases: empty string, empty pattern, consecutive '*', pattern with only '*'

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