The original question referred to "target runtime", which I take to me "basic expected performance characteristics." E.g. "Nothing crazy -- should run on a mil

The original question referred to "target runtime", which I take to me "basic expected performance characteristics." E.g. "Nothing crazy -- should run on a million integers or less, in half a second or less, which requiring not much more than the array size (or a small multiple) in extra memory. And worst case should be not too far from average case." From there, I can start to think about the running complexity (or whether it even matters, for the scale given). But if an interviewer won't even tell me that ... I'd assume they're just like making candidates dance, for the sake of making them dance. While they sit back and stare at their phone, and occasionally interrupt with "hints".