Kth Largest Element in an Array at Amazon — Interview Guide

• A min-heap of size k holds the k largest seen; the root is the answer. O(n log k).
• Quickselect partitions around a pivot and recurses into the side containing the k-th index. Expected O(n).
• Quickselect's worst case is O(n²); randomize the pivot or use median-of-medians to avoid it.

import random
def find_kth_largest(nums, k):
    k = len(nums) - k
    def qs(l, r):
        piv = random.randint(l, r)
        nums[piv], nums[r] = nums[r], nums[piv]
        p = l
        for i in range(l, r):
            if nums[i] < nums[r]:
                nums[i], nums[p] = nums[p], nums[i]; p += 1
        nums[p], nums[r] = nums[r], nums[p]
        if p == k: return nums[p]
        return qs(l, p - 1) if p > k else qs(p + 1, r)
    return qs(0, len(nums) - 1)

• Customer obsession — start from the customer and work backward.
• Ownership — think long-term and act on behalf of the whole company.
• Bias for action — make decisions with incomplete data and ship.
• Dive deep — understand the details behind any metric you cite.
• Deliver results — focus on the right inputs and hit commitments.