N-gram Search With Wildcards | Dataford Interview Questions

Describe how you would implement n-gram searching with wildcard indexing.

Implement search_with_wildcard_index(documents, query, n). documents is a list of strings, query is a case-insensitive substring pattern, and ? matches exactly one character. Return the sorted zero-based indices of documents containing the pattern. The index should use fixed-length n-grams and wildcard variants, then verify candidates to avoid false positives.

Constraints

0 <= documents.length <= 1000
0 <= len(documents[i]) <= 10000
0 <= len(query) <= 10000
2 <= n <= 5
The query contains lowercase or uppercase letters and the wildcard character ?.
A wildcard matches exactly one character.

Function Signature

def search_with_wildcard_index(documents, query, n):

Your question is N-gram Search With Wildcards. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Describe how you would implement n-gram searching with wildcard indexing.

Constraints

0 <= documents.length <= 1000
0 <= len(documents[i]) <= 10000
0 <= len(query) <= 10000
2 <= n <= 5
The query contains lowercase or uppercase letters and the wildcard character ?.
A wildcard matches exactly one character.

Function Signature

def search_with_wildcard_index(documents, query, n):

Your question is N-gram Search With Wildcards. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.