Tries & Advanced Strings interview questions

Prefix trees, autocomplete, and pattern matching for search-heavy roles.

3 questions in Data Structures & Algorithms.

Data Structures & AlgorithmsA 26-minute read on how the topic fits together, before the questions.Data structures and algorithms fundamentals54 short answers on one page, for revising rather than studying.

medium2

mediumCodingConcept

You need to find a substring in linear time and the interviewer will not accept a library call. What do you compute, and what goes wrong on a collision?

Rabin-Karp computes a polynomial hash of the pattern and a rolling hash of each text window, updated in constant time per step modulo a large prime. Equal hashes only nominate a candidate, so you compare characters before reporting it. Skip that check and a collision is a wrong answer; keep it and collisions cost time.

5 minmid, senior

mediumDesignCoding

Design the data structure behind a search box's autocomplete. Why a trie, and when would you not use one?

A trie stores one node per character, so finding a prefix is a walk of length k and its completions are the subtree below it. It costs far more memory than the strings themselves, so a hash map still wins for exact lookup and a sorted array with binary search wins for a static dictionary.

6 minmid, senior, staff

hard1

hardCodingConcept

Find every occurrence of a pattern in a text without ever moving backwards through the text. What does your precomputed table hold?

Precompute, for each prefix of the pattern, the length of the longest proper prefix of the pattern that is also a suffix of that prefix. On a mismatch you fall back to that length instead of rewinding the text, which is what turns the quadratic naive scan into a linear one.

5 minmid, senior, staff