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 Glean.

What role is this question designed for?

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

Find the Kth Largest in Two Sorted Arrays

Quick Overview

This question evaluates proficiency with array manipulation and selection algorithms, specifically understanding order statistics and working with two sorted sequences.

medium
Glean
Coding & Algorithms
Software Engineer

Find the Kth Largest in Two Sorted Arrays

Company: Glean

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given two arrays sorted in ascending order and an integer `k`. Return the `k`th largest element among all elements from both arrays combined. Count duplicates as separate elements. Example: - `a = [0, 1, 4, 5, 6, 7, 8, 10, 13]` - `b = [1, 3, 4, 5, 8, 9, 11, 12]` - `k = 3` The combined elements in descending order begin with `13, 12, 11, 10, ...`, so the answer is `11`.

Quick Answer: This question evaluates proficiency with array manipulation and selection algorithms, specifically understanding order statistics and working with two sorted sequences.

You are given two arrays `a` and `b`, both sorted in ascending order, and an integer `k`. Return the `k`th largest element among all elements from both arrays combined. Duplicates count as separate elements. For example, if the combined sorted order is `[9, 8, 8, 7]`, then the 2nd largest element is `8` and the 3rd largest element is also `8`. Try to use the fact that the arrays are already sorted.

Constraints

0 <= len(a), len(b) <= 200000
1 <= k <= len(a) + len(b)
-1000000000 <= a[i], b[i] <= 1000000000
Both arrays are sorted in non-decreasing order

Examples

Input: ([0, 1, 4, 5, 6, 7, 8, 10, 13], [1, 3, 4, 5, 8, 9, 11, 12], 3)

Expected Output: 11

Explanation: The combined elements in descending order begin as [13, 12, 11, 10, ...], so the 3rd largest is 11.

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

Expected Output: 2

Explanation: Combined descending order is [3, 2, 2, 2, 2, 2, 1]. The 4th largest element is 2.

Input: ([], [5, 6, 7], 2)

Expected Output: 6

Explanation: Only the second array has values. In descending order it is [7, 6, 5], so the 2nd largest is 6.

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

Expected Output: -5

Explanation: Combined descending order is [-1, -2, -3, -5], so the 4th largest is -5.

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

Expected Output: 1

Explanation: There are 6 total elements. Sorted descending they are [9, 8, 4, 3, 2, 1], so the 6th largest is 1.

Hints

The largest remaining element must always be at the end of one of the two arrays.

Loading coding console...