Introduction to Knowing What to Track
Explore the knowing what to track pattern to efficiently count frequencies in data structures like arrays and strings. Understand how to use hash maps and arrays for frequency counting and apply these techniques to real-world problems such as product recommendations, DNA analysis, and clickstream data. This lesson prepares you to recognize when to apply frequency tracking to optimize problem-solving in coding interviews.
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 ...