Instead, the PM might say "We need a system which can count how many unique events of each type has occurred in the last 100k requests, with small impact to time, high accuracy, and up to 100mb of space"

But even that would be unusually specific. It would usually be: "the service breaks sometimes, can you figure it out?" And then the engineers figure out that it's because of unusual event distributions, and they figure out what needs to be done, how much space / time they can afford to do it, etc. For instance, do you trade off accuracy by having a periodic job flush old events out of the map? Do you quantize by time to save space at the cost of resolution?

That's what I do at my job, and that's the kind of question I see in interviews. If a candidate is expecting to have the algorithms dictated to them, then I would not consider them to be a software engineer.. coding up a program from a specification would have been a technician's job 30 years ago (now largely automated by compilers, synthesizers (for HDLs), and other tools). The software engineer should be coming up with solutions, which often involve using algorithms and data structures.