A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

Chapter 20

These are the solutions to the exercises found in the section ​Exercises​.

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 over the other array. As we encounter each athlete, we do an O(1) lookup in the hash table to see if that athlete already ...