Kth

I went over the "Kth largest element" problem, and I thought to my self "huh, I solved it with heap, what's the catch?" Turns out, some interviews were not happy with O(N log K) and wanted an average case of o(n). So now I am spending an hour trying to understand quick select. Same thing for LC 50 (Pow (x,n)). Apparently, some interviews they specifically want a certain solution, and are not happy with yours even if it is optimized. Are there any other easy / medium problems to be aware of, that have similar cases? Please share them below, I'd be curious to see your experience.