Frequency Counting

Frequency counting is the moment hashing becomes more than lookup. Instead of asking whether a key exists, you ask how often it appears. That small change powers validation, grouping, inventory reconciliation, observability metrics, abuse detection, ranking, and many of the most common DSA interview problems.

A Counter Is a Map From Key to Count

A set can tell you that user-42 appeared. A counter can tell you user-42 appeared 19 times. A hash map can store that count using the key as identity and the value as an integer. The repeated operation is simple: read the current count, add one, and write it back.

Scenario: Fraud Burst Detection

A fraud system receives login attempts. A single failed attempt is not enough evidence. Repeated failed attempts from the same IP, device, account, or card fingerprint may be a signal. A frequency counter summarizes those repeated observations so the system can trigger investigation or rate limiting.

Same Pattern in Java, Python, and JavaScript

The following code counts event names. This exact shape appears in analytics, logs, inventory, anagram checks, voting, ranking preparation, and grouping problems.

import java.util.*;

class EventCounter {
    static Map<String, Integer> countEvents(List<String> events) {
        Map<String, Integer> counts = new HashMap<>();
        for (String event : events) {
            counts.put(event, counts.getOrDefault(event, 0) + 1);
        }
        return counts;
    }
}

Fixed Array Counter vs Hash Map Counter

Counter shape depends on key space. If the prompt guarantees lowercase English letters, a 26-slot array is compact and fast. If keys are usernames, product IDs, tokens, IPs, or arbitrary Unicode text, a hash map is safer because the key space is dynamic.

Normalize Before Counting

Counters only reflect the keys you feed them. If 'Error', 'error', and ' error ' should be treated as the same event, normalize before counting. If they should remain distinct, preserve them. This is a product rule, not a syntax choice.

Where Frequency Counting Shows Up

• Anagram and permutation validation.
• Inventory reconciliation and stock movement checks.
• Top searched terms and ranking candidate preparation.
• Rate-limit and fraud feature extraction.
• Log aggregation, observability metrics, and alert thresholds.
• Grouping records by status, category, user, project, or time bucket.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Given two strings, return whether they are anagrams after lowercasing and keeping only letters a-z.
• Given an integer array, return all values that appear more than floor(n / 3) times.
• Given event names and k, return the k most frequent event names.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

class ValidAnagram {
    static boolean isAnagram(String left, String right) {
        String a = left.toLowerCase().replaceAll("[^a-z]", "");
        String b = right.toLowerCase().replaceAll("[^a-z]", "");
        if (a.length() != b.length()) return false;

        int[] counts = new int[26];
        for (char ch : a.toCharArray()) counts[ch - 'a']++;
        for (char ch : b.toCharArray()) {
            int index = ch - 'a';
            counts[index]--;
            if (counts[index] < 0) return false;
        }
        return true;
    }
}

import java.util.*;

class MajorityNByThree {
    static List<Integer> majorityElement(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int value : nums) {
            counts.put(value, counts.getOrDefault(value, 0) + 1);
        }

        List<Integer> result = new ArrayList<>();
        int threshold = nums.length / 3;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() > threshold) result.add(entry.getKey());
        }
        return result;
    }
}

import java.util.*;

class TopKEvents {
    static List<String> topK(List<String> events, int k) {
        Map<String, Integer> counts = new HashMap<>();
        for (String event : events) {
            counts.put(event, counts.getOrDefault(event, 0) + 1);
        }

        List<String> names = new ArrayList<>(counts.keySet());
        names.sort((a, b) -> {
            int byCount = Integer.compare(counts.get(b), counts.get(a));
            return byCount != 0 ? byCount : a.compareTo(b);
        });
        return names.subList(0, Math.min(k, names.size()));
    }
}

Solved modelWorked Interview Answer

Count normalized event names from a product analytics stream. Normalize keys before counting if the product treats casing or spaces as equivalent. Use a map from normalized event name to count.

import java.util.*;

class NormalizedCounter {
    static Map<String, Integer> count(List<String> events) {
        Map<String, Integer> counts = new HashMap<>();
        for (String event : events) {
            String key = event.trim().toLowerCase(Locale.ROOT);
            counts.put(key, counts.getOrDefault(key, 0) + 1);
        }
        return counts;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Using a set when duplicate count is the signal.
• Counting before normalization or tenant scoping.
• Choosing a fixed array counter without a fixed key-space guarantee.
• Ignoring high-cardinality keys in streams.
• Forgetting integer overflow or counter reset/TTL policy in long-running systems.

Execution guardrailQuick-Start Checklist

• Define the counted unit.
• Define normalization and scope.
• Choose fixed array or hash map.
• State time, memory, and cardinality.
• Explain whether counts are exact, windowed, persisted, or approximate.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice valid anagram, majority element, and top-k frequent elements.
• Review map/set cost models from Lessons 13 and 14.
• Study heaps later because top-k frequency often combines counters with priority queues.