Where a number stands in a stream
Numbers arrive one at a time. Build StreamRank, which can say at any moment how many of the numbers so far are at most a given number: the number's rank.
StreamRank() starts with no numbers.
track(x) takes in x. The same number may arrive many times, and every copy counts.
rank(x) returns how many of the numbers taken in so far are less than or equal to x. x itself does not have to have arrived.
Keeping the numbers sorted in a plain list makes each track cost O(n). Aim for O(log m) per call, where m is the largest number allowed.
- Input
["StreamRank","track","rank","track","track","rank","rank","rank","rank"]
[[],[7],[7],[2],[7],[6],[7],[100],[0]]- Output
[null,null,1,null,null,1,3,3,0]
With 7, 2 and 7 taken in: one of them is at most 6, all three are at most 7, and none is at most 0.
- Input
["StreamRank","rank","track","track","rank"]
[[],[5],[0],[0],[0]]- Output
[null,0,null,null,2]
Both copies of 0 count.
Limits
0 <= x <= 100000at most 20000 calls after the constructor
Hints
Hint 1
The numbers are small (at most 100000), so keep a count for every possible value. rank(x) is then a sum of the counts from 0 to x.
Hint 2
A binary indexed (Fenwick) tree adds 1 to one count and sums a prefix of the counts, each in O(log m).
Where this was reported
- Meta, SDE on-campus interview, 2019 (Code360)
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.
