The Dictionary Problem: Fast Lookups in Large Collections

From arrays to hash tables and BSTs: the trade-offs behind a classic problem.

Hi Friends,

Welcome to the 168th issue of the Polymathic Engineer newsletter.

Let’s say you are building a spell checker that runs directly in the browser. You have a dictionary of over 100,000 words, and every time the user types something, you need to quickly check if the word exists in your dictionary. If it doesn’t, you underline it in red.

The feature…