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 Onsite rounds at SoFi.

What role is this question designed for?

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

Find Kth Unique Maximum | SoFi Coding Question

Find Kth Unique Maximum

Company: SoFi

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given two integer arrays sorted in non-decreasing order. Each array may contain duplicates, and the same value may appear in both arrays. Find the k-th distinct largest integer across the combined values of both arrays. Example: - nums1 = [1, 2, 4, 4, 5] - nums2 = [2, 4, 6] The distinct values in descending order are [6, 5, 4, 2, 1], so: - k = 1 -> 6 - k = 2 -> 5 - k = 3 -> 4 - k = 4 -> 2 - k = 5 -> 1 Clarify what should be returned if there are fewer than k distinct values.

Quick Answer: This question evaluates algorithmic problem-solving skills related to sorted arrays, deduplication, and order-statistics across combined datasets, measuring competence with array manipulation and distinctness reasoning.

You are given two integer arrays, nums1 and nums2, each sorted in non-decreasing order. The arrays may contain duplicates, and the same value may appear in both arrays. Consider all values from both arrays together, remove duplicates, and sort the remaining distinct values in descending order. Return the k-th distinct largest value. If there are fewer than k distinct values across both arrays, return -1. Example: nums1 = [1, 2, 4, 4, 5] nums2 = [2, 4, 6] Distinct values in descending order: [6, 5, 4, 2, 1] So k = 1 -> 6, k = 2 -> 5, k = 3 -> 4.

Constraints

0 <= len(nums1), len(nums2) <= 100000
-1000000000 <= nums1[i], nums2[i] <= 1000000000
Both arrays are sorted in non-decreasing order
1 <= k <= 200000

Examples

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

Expected Output: 6

Explanation: The distinct values are [6, 5, 4, 2, 1]. The 1st distinct largest value is 6.

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

Expected Output: 4

Explanation: The distinct values are [6, 5, 4, 2, 1]. The 3rd distinct largest value is 4.

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

Expected Output: 3

Explanation: Only nums2 contributes values. The distinct values in descending order are [5, 3, 2], so the 2nd is 3.

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

Expected Output: 4

Explanation: The value 5 appears in both arrays but must be counted once. The distinct values are [5, 4, 1], so the 2nd distinct largest value is 4.

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

Expected Output: -4

Explanation: The distinct values in descending order are [0, -1, -3, -4, -5]. The 4th distinct largest value is -4.

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

Expected Output: -1

Explanation: There is only one distinct value, 2, so a 2nd distinct largest value does not exist.

Input: ([], [], 1)

Expected Output: -1

Explanation: There are no values at all, so no k-th distinct largest value exists.

Hints

Because both arrays are already sorted, try scanning from the end instead of building and sorting a new combined list.
When you pick a value, skip every copy of that value in both arrays so it is counted only once.

Quick Overview

This question evaluates algorithmic problem-solving skills related to sorted arrays, deduplication, and order-statistics across combined datasets, measuring competence with array manipulation and distinctness reasoning.