Found in
search engines
Articles
SRT
Algorithm
Exponential search
Steps 1, 2, 4, 8, … until you overshoot, then binary search: when the bound is unknown or the answer is near.
2⌊log₂ i⌋ + 1 questions to position i
1 problem
STR
Algorithm
The Burrows–Wheeler transform
A permutation that compresses a text and serves as an index to it: backward search, LF, and read alignment.
O(m) to count a pattern, O(m + k·s) for k positions
2 problems
STR
Algorithm
Edit distance
The fewest insertions, deletions and substitutions between two strings: an m × n table and the alignment read from it.
O(m · n)
2 problems
SYS
Data structure
Inverted index and BM25
A dictionary “word → documents that contain it”: a query reads a few short lists instead of all the texts.
O(total length of the query words' lists); AND by galloping O(m·log(n/m))
2 problems
Problems
Often together
compression 3 interviews 3 searching 2 binary search 2 classic 2 bioinformatics 2 in production 2 suffix structures 1 string matching 1 similarity 1 dynamic programming 1 matrix 1