A google question

help
1

I got a google interview type question from facebook:

You are given an array and an integer k. Find the Kth largest integer in that array.

Expected time complexity - O(n)
Expected space complexity - O(1)

I was shocked by the fact that the time complexity can be O(n) ! :hushed: :astonished:
Can someone please explain?

2 Likes
2

I know that there is a function in STL called as nth_element but I don’t know how it is implemented , it’s Time complexity is O(N)

3

I believe it’s QuickSelect using median of medians as a pivot strategy; not sure if it’s O(1) space, though (standard QuickSelect is in-place - not sure how the pivoting strategy affects this).

Edit:

Hmmm … maybe nth_element doesn’t use this: c++ - nth_element implementations complexities - Stack Overflow . Also it can throw bad_alloc, so presumably not O(1).

3 Likes
4

I’m a beginner, so please can you explain elaborately? But thank you for help

5

This is actually vague question as there is a technique called quick select which works like quick short but it has worst case time complexity O(n²) so using that is risky and also in best case also amortized time complexity is O(n). I think the interviewer is just checking if you know the technique. I would recommend using heap or sorting for this problem if came in some contest.