Katkat
Back

Solve Two Sorted-Array Tasks

InstacartMachine Learning Engineer · Technical Screen
HardMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently merge and find elements in sorted arrays, focusing on optimal time complexity and edge case handling.

Problem Statement

You are working with order history data represented as two sorted integer arrays, arr1 and arr2, of sizes n and m respectively. Perform the following two tasks:

Task 1: Find the K-th Smallest Element

Given both arrays, find the K-th smallest element across the combined set of all elements in arr1 and arr2. You must solve this with a time complexity better than O(n + m).

Task 2: Count Common Elements

Find the total number of unique elements that appear in both arr1 and arr2 (the size of the intersection). Your solution should be efficient, especially when one array is significantly smaller than the other.

Function Signature

def solve_sorted_tasks(arr1: list[int], arr2: list[int], k: int) -> tuple[int, int]:
    # Returns (k_th_smallest, intersection_count)
    pass

Examples

Input: arr1 = [1, 3, 5], arr2 = [2, 3, 6], k = 3
Output: (3, 1)
Explanation: Combined sorted array is [1, 2, 3, 3, 5, 6]. The 3rd element is 3. Intersection is {3}.

Input: arr1 = [1, 4, 8], arr2 = [2, 5, 9], k = 1
Output: (1, 0)

Constraints

  • 0 <= n, m <= 10^5
  • 1 <= k <= n + m
  • Arrays are sorted in non-decreasing order.
  • Consider cases where arrays contain duplicates.

Hints

Hint 1

For Task 1, use a binary search approach on the partition point of the arrays to achieve O(log(min(n, m))) time complexity.

Hint 2

For Task 2, leverage the two-pointer technique to traverse both arrays simultaneously in linear time.

Hint 3

Think about how the behavior changes if one array is empty or if k is equal to the total number of elements.

Follow-up questions

  • How would your Task 2 implementation change if the arrays were not sorted?
  • If you were asked to find the median of the two combined arrays instead of the k-th element, how would you adjust the logic?
  • What would be the memory complexity of your solutions, and can you optimize the space if the arrays are stored on disk?