InternDoor

How often a value shows up between two places

Mediumdesign · binary search · hashingDesign a class

Reported in interviews at (where)

RangeCounter(arr) keeps the array arr.

count(left, right, value) returns how many times value appears among arr[left], arr[left + 1], ..., arr[right].

There can be many calls on a long array, so walking through the range on every call is too slow for the largest tests: aim for O(log n) per call.

Example 1
Input
["RangeCounter","count","count","count"]
[[[4,9,4,4,2,9]],[0,3,4],[1,5,9],[4,4,7]]
Output
[null,3,2,0]

Places 0 to 3 hold 4, 9, 4, 4: three 4s. Places 1 to 5 hold both 9s. Place 4 holds a 2, not a 7.

Limits

  • 1 <= arr.length <= 100000
  • 1 <= arr[i], value <= 10000
  • 0 <= left <= right < arr.length
  • at most 20000 calls to count

Hints

Hint 1

In the constructor, list the places where each value appears. Reading the array from the start makes every list sorted.

Hint 2

The count is the number of places in that list from left to right: two binary searches.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.