Katkat

Find First Anagram Occurrence

DatabricksBackend Engineer · Technical Screen

Last updated

This question evaluates proficiency in string processing, character-frequency analysis, and efficient substring search techniques, measuring competency in algorithmic reasoning and implementation for pattern matching.

Given two strings text and pattern, return the starting index of the first substring in text that is an anagram of pattern. If no such substring exists, return -1.

A substring is an anagram of pattern if it has exactly the same character frequencies as pattern, possibly in a different order.

Assume the input strings contain lowercase English letters unless otherwise specified.

Example:

text = "cbaebabacd"
pattern = "abc"

The substrings of length 3 are checked from left to right. The first substring that is an anagram of "abc" is "cba", so the answer is 0.

Follow-up: Explain how your approach would scale if text were extremely large, streamed in chunks, or distributed across multiple machines.