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 hard difficulty Coding & Algorithms question, commonly asked during HR 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.

Solve listed algorithm problems | Rippling Coding Question

Quick Overview

This set of problems evaluates algorithmic problem-solving skills across selection and order-statistics, graph algorithms and traversals, connected-component analysis on irregular grids, optimization under exchange-rate transformations, and streaming data-structure design.

Solve listed algorithm problems

Company: Rippling

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: HR Screen

The interview note referenced several independent coding problems. Solve each one independently. 1. **Median of two sorted arrays** You are given two integer arrays `a` and `b`, each already sorted in non-decreasing order. Compute the median of the multiset formed by all elements in both arrays. The target solution should run in `O(log(min(len(a), len(b))))` time. 2. **Maximize value after two days of currency conversions** You start with `1.0` unit of an initial currency `S`. On day 1, you may perform any number of conversions using a set of exchange pairs and rates. On day 2, you may again perform any number of conversions using a different set of exchange pairs and rates. For each listed pair `(u, v)` with rate `r`, you may convert `u -> v` at rate `r` and `v -> u` at rate `1/r`. Determine the maximum amount of currency `S` you can end with after both days. 3. **Find bounding boxes of connected houses in a ragged grid** You are given a 2D grid where rows may have different lengths. Each cell contains either `1` (house) or `0` (empty). Two houses are connected if they are adjacent vertically or horizontally and the neighboring cell actually exists in the ragged grid. For every connected component of houses, return its bounding box as `(min_row, min_col, max_row, max_col)`. 4. **Compute the maximum transfer time in a network** You are given an undirected, unweighted network of servers. Sending a file across one edge takes one unit of time. If a file starts at one endpoint of the network's longest shortest path, what is the maximum time needed for the farthest server to receive it? In other words, compute the diameter of the graph/tree using graph traversal. 5. **Maintain the median of a data stream** Design a data structure supporting: - `add(x)`: insert a number - `median()`: return the median of all inserted numbers The operations should support online processing of a stream of values, with efficient insertion and constant-time median lookup. Explain the expected time and space complexity for each problem.

Quick Answer: This set of problems evaluates algorithmic problem-solving skills across selection and order-statistics, graph algorithms and traversals, connected-component analysis on irregular grids, optimization under exchange-rate transformations, and streaming data-structure design.

Part 1: Median of Two Sorted Arrays

You are given two integer arrays `a` and `b`, each already sorted in non-decreasing order. Return the median of all values from both arrays combined. Your solution should run in `O(log(min(len(a), len(b))))` time. The median is the middle value when the total number of elements is odd, or the average of the two middle values when it is even.

Loading coding console...

Examples

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

Expected Output: 2.0

Explanation: Combined sorted array is [1, 2, 3], so the median is 2.

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

Expected Output: 2.5

Explanation: Combined sorted array is [1, 2, 3, 4], so the median is (2 + 3) / 2.

Input: ([], [5])

Expected Output: 5.0

Explanation: Edge case where one array is empty.

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

Expected Output: 0.0

Explanation: All values are the same, so the median is 0.

Part 2: Maximize Value After Two Days of Currency Conversions

You start with `1.0` unit of an initial currency `S`. On day 1, you may perform any number of conversions using the day 1 exchange list. On day 2, you may again perform any number of conversions using the day 2 exchange list. For every listed pair `(u, v, r)`, you may convert `u -> v` at rate `r` and `v -> u` at rate `1 / r`. Return the maximum amount of currency `S` you can end with after both days. Assume there is no profitable arbitrage cycle within a single day, so the maximum answer is finite.

Constraints

1 <= number of distinct currencies across a day <= 200
0 <= len(day1), len(day2) <= 1000
Each rate is a positive float
No profitable cycle exists within a single day

Examples

Input: ('USD', [('USD', 'EUR', 0.9)], [('USD', 'EUR', 0.8)])

Expected Output: 1.125

Explanation: Day 1: USD -> EUR gives 0.9 EUR. Day 2: EUR -> USD gives 1 / 0.8 = 1.25. Final amount is 0.9 * 1.25 = 1.125.

Input: ('A', [('A', 'B', 2.0), ('B', 'C', 3.0)], [('A', 'C', 4.0), ('B', 'C', 1.0)])

Expected Output: 1.5

Explanation: Best is A -> B -> C on day 1 for 6.0 C, then C -> A on day 2 for 1 / 4 = 0.25, giving 1.5 A.

Input: ('USD', [('EUR', 'JPY', 130.0)], [('EUR', 'GBP', 0.8)])

Expected Output: 1.0

Explanation: Edge case: the starting currency is disconnected on both days, so doing nothing is optimal.

Input: ('USD', [('USD', 'EUR', 0.9), ('USD', 'GBP', 0.7)], [('USD', 'EUR', 0.95), ('USD', 'GBP', 0.5)])

Expected Output: 1.4

Explanation: EUR path returns about 0.947..., but GBP returns 0.7 * 2.0 = 1.4, which is best.

Hints

Think of each day as a graph where path products represent conversion multipliers.
If you know the best multiplier from `S` to every currency on day 1, and the best multiplier from every currency back to `S` on day 2, you can combine them.

Part 3: Find Bounding Boxes of Connected Houses in a Ragged Grid

You are given a 2D grid of `0`s and `1`s, but the grid is ragged: different rows may have different lengths. A cell containing `1` represents a house. Two houses are connected if they are adjacent vertically or horizontally and the neighboring cell actually exists in the ragged grid. For every connected component of houses, return its bounding box as `(min_row, min_col, max_row, max_col)`. Return the list of bounding boxes sorted in lexicographic order.

Constraints

0 <= number of rows <= 200000
Total number of existing cells across all rows <= 200000
Each cell is either 0 or 1

Examples

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

Expected Output: [(0, 0, 1, 0), (0, 2, 0, 2), (2, 1, 2, 1)]

Explanation: There are three components: the left vertical pair, the single top-right house, and the single bottom house.

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

Expected Output: [(0, 0, 1, 1), (2, 1, 2, 2)]

Explanation: The missing cell at row 1, col 1 breaks what would otherwise look connected in a rectangular grid.

Input: ([])

Expected Output: []

Explanation: Edge case: empty grid.

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

Expected Output: [(2, 0, 2, 0)]

Explanation: Only one house exists.

Hints

Treat each existing `1` cell as a graph node and run DFS or BFS over valid neighbors only.
While exploring one component, keep track of min/max row and column indices.

Part 4: Compute the Maximum Transfer Time in a Network

You are given an undirected, unweighted network of servers labeled from `0` to `n - 1`. Sending a file across one edge takes one unit of time. If a file starts at one endpoint of the network's longest shortest path, what is the maximum time needed for the farthest server to receive it? In other words, compute the diameter of the connected graph.

Constraints

1 <= n <= 2000
0 <= len(edges) <= 5000
0 <= u, v < n
The graph is connected

Examples

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

Expected Output: 3

Explanation: A simple path of length 3 has diameter 3.

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

Expected Output: 3

Explanation: The farthest pair is server 4 and server 3, at distance 3.

Input: (1, [])

Expected Output: 0

Explanation: Edge case: a single server has diameter 0.

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

Expected Output: 2

Explanation: In a star, the distance between any two leaves is 2.

Hints

In an unweighted graph, shortest paths from a source can be found with BFS.
For a general graph, computing the diameter exactly can be done by running BFS from every node.

Part 5: Maintain the Median of a Data Stream

Process a stream of numbers online. You need to support two operations: - `add(x)`: insert number `x` - `median()`: return the median of all inserted numbers so far Implement a function that processes a list of operations and returns the results of each `median()` query. Insertion should be efficient, and median lookup should be constant time.

Constraints

1 <= len(operations) <= 200000
Values inserted by `add` are integers
Every `median` operation occurs only after at least one `add`

Examples

Input: ([('add', 1), ('median', None), ('add', 2), ('median', None), ('add', 3), ('median', None)])

Expected Output: [1.0, 1.5, 2.0]

Explanation: The medians after the three queries are 1, then (1+2)/2, then 2.

Input: ([('add', 5), ('add', 15), ('add', 1), ('add', 3), ('median', None)])

Expected Output: [4.0]

Explanation: Sorted values are [1, 3, 5, 15], so the median is (3 + 5) / 2.

Input: ([('add', 7), ('median', None)])

Expected Output: [7.0]

Explanation: Edge case: only one value has been inserted.

Input: ([('add', -1), ('add', -2), ('median', None), ('add', -3), ('median', None)])

Expected Output: [-1.5, -2.0]

Explanation: After two values the median is -1.5; after three values it is -2.

Hints

Keep the smaller half of the numbers in a max-heap and the larger half in a min-heap.
After every insertion, rebalance so the heaps differ in size by at most 1.