Exercise 24: Fast URL Search

We will end the section on data structures and algorithms with a performance measurement challenge that applies your data structures to an actual problem. I've written a few web servers in my time, and one problem that constantly comes up is matching URL paths to "actions". You'll find this problem in every web framework, web server, and anything that has to "route" information based on a key that is hierarchical. When your web server receives the URL /do/this/stuff/, it has to figure out if each part is possibly attached to some kind of action or configuration. If you configured a web application at /do/, then what should your web server do with /this/stuff/? Should it consider that a failure or pass it to the web application? What if there's a directory at /do/this/? And, how do you detect bad URLs quickly so you're not processing giant requests that don't exist?

This kind of hierarchical search comes up frequently enough that it's a good final test of your ability to apply algorithms and data structures to problems as well as a test of your ability to do performance analysis.