Scale Engineer

Frequency Tracker

Med
#2423Time: `add`: O(1) amortized. `deleteOne`: O(N), where N is the total number of elements. `hasFrequency`: O(N), as it requires a full scan of the list.Space: O(N), to store all the numbers in the list, where N is the total number of elements.
Patterns
Design
Data structures
Hash Table

Prompt

Design a data structure that keeps track of the values in it and answers some queries regarding their frequencies.

Implement the FrequencyTracker class.

  • FrequencyTracker(): Initializes the FrequencyTracker object with an empty array initially.
  • void add(int number): Adds number to the data structure.
  • void deleteOne(int number): Deletes one occurrence of number from the data structure. The data structure may not contain number, and in this case nothing is deleted.
  • bool hasFrequency(int frequency): Returns true if there is a number in the data structure that occurs frequency number of times, otherwise, it returns false.

 

Example 1:

Input
["FrequencyTracker", "add", "add", "hasFrequency"]
[[], [3], [3], [2]]
Output
[null, null, null, true]

Explanation
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(3); // The data structure now contains [3]
frequencyTracker.add(3); // The data structure now contains [3, 3]
frequencyTracker.hasFrequency(2); // Returns true, because 3 occurs twice

Example 2:

Input
["FrequencyTracker", "add", "deleteOne", "hasFrequency"]
[[], [1], [1], [1]]
Output
[null, null, null, false]

Explanation
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(1); // The data structure now contains [1]
frequencyTracker.deleteOne(1); // The data structure becomes empty []
frequencyTracker.hasFrequency(1); // Returns false, because the data structure is empty

Example 3:

Input
["FrequencyTracker", "hasFrequency", "add", "hasFrequency"]
[[], [2], [3], [1]]
Output
[null, false, null, true]

Explanation
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.hasFrequency(2); // Returns false, because the data structure is empty
frequencyTracker.add(3); // The data structure now contains [3]
frequencyTracker.hasFrequency(1); // Returns true, because 3 occurs once

 

Constraints:

  • 1 <= number <= 105
  • 1 <= frequency <= 105
  • At most, 2 * 105 calls will be made to add, deleteOne, and hasFrequency in total.

Approaches

3 approaches with complexity analysis and trade-offs.

This naive approach uses a simple list to store all the numbers as they are added. While add is simple, deleteOne and hasFrequency are inefficient as they require scanning the list.

Algorithm

  • Initialize an ArrayList to store numbers.
  • For add(number), append the number to the list.
  • For deleteOne(number), find and remove one instance of the number from the list.
  • For hasFrequency(frequency), create a temporary frequency map by iterating through the list. Then, check if any value in the map equals the target frequency.

Walkthrough

In this method, we use a standard java.util.ArrayList to maintain the collection of numbers.

  • add(number): This operation is straightforward; we just append the new number to the end of the list. This is an O(1) amortized operation.
  • deleteOne(number): To delete a number, we must first find it in the list. The list.remove(Object) method performs a linear scan, resulting in O(N) time complexity, where N is the number of elements in the list.
  • hasFrequency(frequency): This is the most expensive operation. For each call, we must determine the frequency of every unique number in the current list. This can be done by using a temporary HashMap to build a frequency map from scratch by iterating over the entire list, and then checking if any number has the desired frequency. This also takes O(N) time.

Due to the O(N) complexity of deleteOne and hasFrequency, this approach is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error.

import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map; class FrequencyTracker {    private List<Integer> data;     public FrequencyTracker() {        data = new ArrayList<>();    }     public void add(int number) {        data.add(number);    }     public void deleteOne(int number) {        data.remove(Integer.valueOf(number));    }     public boolean hasFrequency(int frequency) {        Map<Integer, Integer> counts = new HashMap<>();        for (int num : data) {            counts.put(num, counts.getOrDefault(num, 0) + 1);        }        for (int count : counts.values()) {            if (count == frequency) {                return true;            }        }        return false;    }}

Complexity

Time

`add`: O(1) amortized. `deleteOne`: O(N), where N is the total number of elements. `hasFrequency`: O(N), as it requires a full scan of the list.

Space

O(N), to store all the numbers in the list, where N is the total number of elements.

Trade-offs

Pros

  • Very simple to conceptualize and implement.

  • Low memory overhead if the list is compact.

Cons

  • The deleteOne operation is slow (O(N)).

  • The hasFrequency operation is very slow (O(N)) and inefficient if called frequently.

Solutions

class FrequencyTracker { private Map < Integer , Integer > cnt = new HashMap <>(); private Map < Integer , Integer > freq = new HashMap <>(); public FrequencyTracker () { } public void add ( int number ) { int f = cnt . getOrDefault ( number , 0 ); if ( freq . getOrDefault ( f , 0 ) > 0 ) { freq . merge ( f , - 1 , Integer: : sum ); } cnt . merge ( number , 1 , Integer: : sum ); freq . merge ( f + 1 , 1 , Integer: : sum ); } public void deleteOne ( int number ) { int f = cnt . getOrDefault ( number , 0 ); if ( f == 0 ) { return ; } freq . merge ( f , - 1 , Integer: : sum ); cnt . merge ( number , - 1 , Integer: : sum ); freq . merge ( f - 1 , 1 , Integer: : sum ); } public boolean hasFrequency ( int frequency ) { return freq . getOrDefault ( frequency , 0 ) > 0 ; } } /** * Your FrequencyTracker object will be instantiated and called as such: * FrequencyTracker obj = new FrequencyTracker(); * obj.add(number); * obj.deleteOne(number); * boolean param_3 = obj.hasFrequency(frequency); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem