[lokeg]

> It's trivial in quadratic time too, of course, although I would expect a candidate for a senior role to be able at least to find the linear solution, if not to start there outright.

I would not call this trivial. The code in your post is incorrect. For example, it cannot find "ababc" within "abababc", since after the first mismatch we skip too much of the haystack.

The real solution to this is Knuth-Morris-Pratt, where we must precompute for every index in the needle the longest needle prefix that fits before it. I would not expect your average interviewee to derive or implement this.

An easier linear time solution (in my opinion) is rolling polynomial hashing. But if you actually expect solutions in an interview you should settle for the naive quadratic algorithm.