Range Frequency Queries

Range Frequency Queries

What is this problem about?

The Range Frequency Queries problem asks you to design a data structure supporting queries: given a range [l, r] and a value, count how many times the value appears in the subarray arr[l..r]. This coding problem uses sorted position lists with binary search for O(log n) per query. The array, hash table, design, binary search, and segment tree interview pattern is the core.

Why is this asked in interviews?

Quora and TikTok ask this because it tests the design skill of precomputing sorted position lists — a simple and elegant approach that answers frequency queries efficiently.

Algorithmic pattern used

Precomputed sorted positions + binary search. During initialization: for each value, store a sorted list of all indices where it appears. For query(l, r, value): use binary search to find how many positions in value's list fall in [l, r]. Answer = bisect_right(positions, r) - bisect_left(positions, l).

Example explanation

arr=[12,33,4,56,22,2,34,33,22,12,34,56]. query(1,2,33): positions of 33 = [1,7]. bisect_right([1,7],2) - bisect_left([1,7],1) = 1-0 = 1.

Common mistakes candidates make

• Linear scan per query (O(n) instead of O(log n)).
• Not precomputing position lists.
• bisect_right vs bisect_left: bisect_right for upper bound, bisect_left for lower bound.
• Off-by-one in range boundaries.

Interview preparation tip

Range frequency queries are a great example of precomputation for query optimization: store sorted positions of each value, answer queries with two binary searches. This O(n log n) preprocessing + O(log n) per query is far better than O(n) per query. Practice similar "range occurrence counting" designs with binary search on precomputed position arrays.