PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

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.

  • hard
  • Rippling
  • Coding & Algorithms
  • Software Engineer

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.

Constraints

  • 0 <= len(a), len(b) <= 200000
  • At least one of the arrays is non-empty
  • -10^6 <= element value <= 10^6
  • Both arrays are already sorted in non-decreasing order

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.

Hints

  1. Try partitioning the smaller array and infer the matching partition in the larger array.
  2. A correct partition makes every element on the left side less than or equal to every element on the right side.

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

  1. Think of each day as a graph where path products represent conversion multipliers.
  2. 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

  1. Treat each existing `1` cell as a graph node and run DFS or BFS over valid neighbors only.
  2. 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

  1. In an unweighted graph, shortest paths from a source can be found with BFS.
  2. 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

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

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement a Searchable Logger Pipeline - Rippling (hard)
  • Implement an In-Memory File System - Rippling
  • Compare Complete and Partial Poker Hands - Rippling (medium)
  • Implement Courier Delivery Cost Tracking - Rippling (medium)
  • Implement Article Vote Tracking - Rippling (medium)