How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at TikTok during technical interviews.

Find k-th largest element in array | TikTok Coding Question

Q: Find k-th largest element in array

This question evaluates array manipulation, selection algorithms, in-place partitioning techniques, and complexity analysis within the domain of coding and algorithms.

Find k-th largest element in array

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given an unsorted array of integers `nums` and a positive integer `k`. Design an efficient algorithm to find the **k-th largest** element in the array. The k-th largest element is the element that would appear in position `len(nums) - k` if the array were sorted in non-decreasing order. - Example: - Input: `nums = [3, 2, 1, 5, 6, 4]`, `k = 2` - Output: `5` (the sorted array is `[1, 2, 3, 4, 5, 6]`, so the 2nd largest is 5) Assumptions and requirements: - `1 <= k <= len(nums)`. - The array may contain duplicate values. - Aim for an algorithm with good **average-case** time complexity (better than fully sorting the array if possible). Tasks: 1. Describe the algorithm you would use to find the k-th largest element, ideally using an in-place partitioning approach inspired by quicksort. 2. Write the core logic in code (in the language of your choice). 3. Analyze the **average-case time complexity** and **space complexity** of your algorithm, and briefly explain why the average-case complexity holds.

Quick Answer: This question evaluates array manipulation, selection algorithms, in-place partitioning techniques, and complexity analysis within the domain of coding and algorithms.

You are given an unsorted array of integers `nums` and a positive integer `k`. Return the k-th largest element in the array, where duplicates count as separate elements. In other words, if the array were sorted in non-decreasing order, you should return the value at index `len(nums) - k`. You should aim for an efficient algorithm using an in-place partitioning strategy inspired by quicksort (Quickselect), rather than fully sorting the array.

Constraints

1 <= len(nums) <= 100000
-1000000000 <= nums[i] <= 1000000000
1 <= k <= len(nums)
The array may contain duplicate values

Examples

Input: ([3, 2, 1, 5, 6, 4], 2)

Expected Output: 5

Explanation: Sorted order is [1, 2, 3, 4, 5, 6], so the 2nd largest element is 5.

Input: ([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)

Expected Output: 4

Explanation: Sorted order is [1, 2, 2, 3, 3, 4, 5, 5, 6], so the 4th largest element is 4.

Input: ([7], 1)

Expected Output: 7

Explanation: With only one element, the 1st largest is 7.

Input: ([-1, -5, -3, -2], 3)

Expected Output: -3

Explanation: Sorted order is [-5, -3, -2, -1], so the 3rd largest element is -3.

Input: ([2, 2, 2, 2], 2)

Expected Output: 2

Explanation: All elements are equal, so every rank corresponds to the value 2.

Input: ([9, 1, 8, 2], 4)

Expected Output: 1

Explanation: The 4th largest element is the smallest element in the array, which is 1.

Solution

def solution(nums, k):
    import random

    target = len(nums) - k
    left, right = 0, len(nums) - 1

    while left <= right:
        pivot_index = random.randint(left, right)
        pivot_value = nums[pivot_index]

        nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
        store_index = left

        for i in range(left, right):
            if nums[i] < pivot_value:
                nums[store_index], nums[i] = nums[i], nums[store_index]
                store_index += 1

        nums[store_index], nums[right] = nums[right], nums[store_index]

        if store_index == target:
            return nums[store_index]
        elif store_index < target:
            left = store_index + 1
        else:
            right = store_index - 1

    return -1

Time complexity: Average-case O(n), worst-case O(n^2). Space complexity: O(1) auxiliary space.

Hints

The k-th largest element is the same as the element at index `len(nums) - k` in the array sorted in ascending order.
Use a partition step like quicksort: place one pivot in its final sorted position, then continue only on the side that contains the target index.

Quick Overview

This question evaluates array manipulation, selection algorithms, in-place partitioning techniques, and complexity analysis within the domain of coding and algorithms.