Introduction to the Knowing What to Track pattern

Let’s go over the Knowing What to Track pattern, its real-world applications, and some problems we can solve with it.

We'll cover the following

About the pattern

Imagine you work for a big online shop like Amazon, and you need to suggest products to users based on their purchase history. There is a massive database with millions of users and the items they’ve bought. To find out which products are popular among each user, a count for each product purchased is required. Doing it manually with traditional methods would be highly inefficient and time-consuming. Therefore, you would need to set up a system that automatically keeps track of how often each product is purchased by each user. It’s like having a digital tally counter for every product and every user. This way, when it’s time to make recommendations, you can do it efficiently because you already have a clear picture of which products each user prefers.

This is exactly what the knowing what to track pattern does. It involves counting the occurrences of elements in a given data structure, mostly an array or a string, and using this frequency information to solve the problem efficiently. The pattern can be divided into two main phases:

  • Counting phase: This is to iterate through the elements of the data structure and count the frequency of each element. We can use different data structures to achieve this, such as hash maps, dictionaries, arrays, or even simple variables.

  • Utilization phase: Once the frequencies are calculated, we can use this information to solve the specific problem at hand. This could involve any task that benefits from knowing the frequency of elements, such as:

    • Find the most frequent element.

    • Identify elements that occur only once.

    • Check if two arrays are permutations of each other.

    • Check if the player wins the game.

Let’s analyze how we can use the two most common data structures—hash map and array—for frequency counting. The hash map stores elements as keys and their frequencies as values. While iterating over the data structure, for each element encountered, we update its frequency as follows:

  • If the element is already a key in the hash table, its frequency value is incremented by 1.

  • Otherwise, the element is added to the hash table with a frequency of 1.

Let’s look at the following illustration to understand how we can use hash maps to keep the counts of given data:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.