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

What role is this question designed for?

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

Find median of two sorted arrays | Rippling Coding Question

Find median of two sorted arrays

Company: Rippling

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given two sorted arrays of integers `nums1` and `nums2` in non-decreasing order. Let the lengths be `m = nums1.length` and `n = nums2.length`. Either array may be empty, but not both at the same time. If you were to conceptually merge them into a single sorted array `merged` of length `m + n`, the **median** is defined as: - If `m + n` is odd: the element at index `(m + n) / 2` (0-based) in `merged`. - If `m + n` is even: the average of the two middle elements at indices `(m + n) / 2 - 1` and `(m + n) / 2` in `merged`. ### Task Implement a function that returns the median of the two sorted arrays **without actually merging them**. - **Function signature (conceptual):** - Input: `nums1: integer[]`, `nums2: integer[]` - Output: `median: float` (or double) ### Constraints (you may assume) - `0 ≤ m, n ≤ 10^5` - `m + n ≥ 1` - Each array is individually sorted in non-decreasing order. - Integer values fit in a 32-bit signed integer range. - Target time complexity: **O(log(m + n))**. - Extra space complexity: **O(1)** beyond input storage.

Quick Answer: This question evaluates algorithmic problem-solving skills related to sorted arrays and median computation, testing competency in handling numeric order properties and complexity analysis within the Coding & Algorithms domain.

You are given two sorted arrays of integers, nums1 and nums2, in non-decreasing order. Either array may be empty, but not both. If the two arrays were conceptually merged into one sorted array, the median is: - the middle element when the total length is odd - the average of the two middle elements when the total length is even Return the median without actually merging the arrays. Your solution should run in logarithmic time relative to the smaller array.

Constraints

0 <= len(nums1), len(nums2) <= 10^5
len(nums1) + len(nums2) >= 1
Each array is sorted in non-decreasing order
Integer values fit in a 32-bit signed integer range
Target time complexity: O(log(min(m, n)))
Extra space complexity: O(1)

Examples

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

Expected Output: 2.0

Explanation: The combined sorted array would be [1, 2, 3], so the middle element is 2.

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

Expected Output: 2.5

Explanation: The combined sorted array would be [1, 2, 3, 4], so the median is (2 + 3) / 2 = 2.5.

Input: ([], [1])

Expected Output: 1.0

Explanation: Only one element exists in total, so that element is the median.

Input: ([0, 0], [0, 0])

Expected Output: 0.0

Explanation: The combined sorted array is [0, 0, 0, 0], and the two middle values are both 0.

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

Expected Output: -2.5

Explanation: The combined sorted array is [-5, -3, -2, -1], so the median is (-3 + -2) / 2 = -2.5.

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

Expected Output: 6.0

Explanation: The combined sorted array has 11 elements, so the median is the element at index 5, which is 6.

Hints

Try binary searching on the smaller array instead of thinking about merging both arrays.
A valid partition is one where every element on the left side is less than or equal to every element on the right side.

Quick Overview

This question evaluates algorithmic problem-solving skills related to sorted arrays and median computation, testing competency in handling numeric order properties and complexity analysis within the Coding & Algorithms domain.