The general problem is string searching; there are many algorithms and approaches depending on the nature of the application.
- Knuth-Morris-Pratt, searches for a string within another string
- Boyer-Moore, another string within string search
- Aho-Corasick; searches for words from a reference dictionary in a given arbitrary text
Some advanced index data structures are also used in other applications. Suffix trees are used a lot in bioinformatics; here you have one long reference text, and then you have many arbitrary strings that you want to find all occurrences for. Once the index (i.e. the tree) is built, finding patterns can be done quite efficiently.
For an interview answer, I think it's better to show breadth as well. Knowing about all these different algorithms and what specific purposes they serve best is probably better than knowing just one algorithm by heart.
No comments:
Post a Comment