A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Chapter 20

These are the solutions to the exercises found in the section, ​Exercises​. The solutions provided here are in Ruby, but you can find the solutions in JavaScript and Python in the code download.^[19]

1. We can optimize this algorithm if we ask ourselves, “If I could magically find a desired piece of information in O(1) time, can I make my algorithm faster?”

   Specifically, as we iterate over one array, we’d want to “magically” look up that athlete from the other array in O(1) time. To accomplish this, we can first transform one of the arrays into a hash table. We’ll use the full name (that is, the first and last name) as the key, and true (or any arbitrary item) as the value.

   Once we’ve turned one array into this hash table, we then iterate ...