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 role is this question designed for?

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

Solve path and inventory problems | Robinhood Coding Question

Quick Overview

This question evaluates algorithmic problem-solving skills around numeric robustness and stateful stream processing, specifically testing reasoning about path-dependent multiplicative scores with sign changes and inventory reconciliation with fractional quantities and compensation tracking.

Solve path and inventory problems

Company: Robinhood

Role: Software Engineer

Category: Coding & Algorithms

Interview Round: Onsite

The coding rounds contained two algorithmic exercises: 1. **Maximum multiplier path** You are given an `m x n` grid of integers. Start at the top-left cell with score `1`. Whenever you enter a cell, multiply your current score by that cell's value. You may move only **right** or **down** until you reach the bottom-right cell. Return the **maximum possible final product**. Because the grid may contain negative values, your solution should correctly handle sign changes. 2. **Fractional inventory processor** You are given an initial inventory map `inventory[item_id]`, where quantities may be fractional decimals. Then you receive a stream of events in chronological order. Each event is `(item_id, type, quantity)`, where `type` is either `restock` or `consume`. - A `restock` event adds quantity back to the item. - A `consume` event removes quantity from available inventory. - Inventory may never go below zero. - If a `consume` request is larger than the available amount, fulfill as much as possible and record the remaining amount as `compensate[item_id]`. - Future `restock` events must first pay down any outstanding `compensate[item_id]` before increasing available inventory. Return the final `inventory` and final `compensate` values for all items. Discuss how you would avoid floating-point precision issues and analyze the time complexity.

Quick Answer: This question evaluates algorithmic problem-solving skills around numeric robustness and stateful stream processing, specifically testing reasoning about path-dependent multiplicative scores with sign changes and inventory reconciliation with fractional quantities and compensation tracking.

Part 1: Maximum Multiplier Path

You are given a rectangular grid of integers. You start with score 1 before the top-left cell. Each time you enter a cell, multiply your current score by that cell's value, so the top-left and bottom-right cells are both included exactly once. From the top-left cell, you may move only right or down until you reach the bottom-right cell. Return the maximum possible final product. Because negative values can flip signs, a path with the largest intermediate product is not always optimal.

Constraints

1 <= m, n <= 200
-10 <= grid[i][j] <= 10
The grid is rectangular.
The exact answer may exceed 64-bit integer range; use arbitrary-precision integers if needed.

Examples

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

Expected Output: 12

Explanation: The best path is down then right: 1 * 1 * 3 * 4 = 12.

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

Expected Output: 1080

Explanation: The optimal path is down, right, right, down: -1 * 4 * 5 * -6 * 9 = 1080.

Input: ([ [-5] ],)

Expected Output: -5

Explanation: Edge case: with one cell, you must take that value.

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

Expected Output: 0

Explanation: Any path avoiding zero is negative here, so a path through the zero cell gives the maximum product 0.

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

Expected Output: -8

Explanation: Both paths have negative products; the less negative one is -8.

Hints

At each cell, keep track of both the maximum product and the minimum product that can reach it.
A negative cell can turn the smallest previous product into the largest new product.

Part 2: Fractional Inventory Processor

You are given an initial inventory map where quantities are non-negative decimal strings, and a chronological list of events. Each event is (item_id, type, quantity), where type is either 'restock' or 'consume'. A restock first pays down any outstanding compensation for that item; only the remaining quantity increases available inventory. A consume removes as much as possible from available inventory; if the request is larger than what is available, the unfilled amount is added to compensation. Inventory can never go below zero. Return a tuple (final_inventory, final_compensate) for every item that appears in the initial inventory or in any event. To avoid floating-point precision issues, process quantities exactly, such as by converting them to fixed-point integers.

Constraints

0 <= number of initial items <= 200000
0 <= number of events <= 200000
item_id is a string
All quantities are non-negative decimal strings with at most one decimal point
No scientific notation is used in the input

Examples

Input: ({'apple': '5.5'}, [('apple', 'consume', '2.25'), ('apple', 'restock', '1'), ('apple', 'consume', '10'), ('apple', 'restock', '4.75')])

Expected Output: ({'apple': '0'}, {'apple': '1'})

Explanation: The last restock first reduces the outstanding compensation from 5.75 to 1 before any inventory can increase.

Input: ({'x': '1.2', 'y': '0'}, [('x', 'consume', '1.5'), ('y', 'restock', '2.3'), ('x', 'restock', '0.1'), ('y', 'consume', '1.1')])

Expected Output: ({'x': '0', 'y': '1.2'}, {'x': '0.2', 'y': '0'})

Explanation: Item x ends with unpaid compensation, while item y ends with positive inventory.

Input: ({'solo': '2.5'}, [])

Expected Output: ({'solo': '2.5'}, {'solo': '0'})

Explanation: Edge case: with no events, inventory stays unchanged and compensation is zero.

Input: ({}, [('z', 'consume', '1.5'), ('z', 'restock', '0.4'), ('z', 'restock', '2')])

Expected Output: ({'z': '0.9'}, {'z': '0'})

Explanation: The first restock partially pays compensation; the second clears it and leaves 0.9 in inventory.

Input: ({'p': '0.3'}, [('p', 'consume', '0.1'), ('p', 'consume', '0.2')])

Expected Output: ({'p': '0'}, {'p': '0'})

Explanation: This case highlights why exact decimal handling matters: the final quantity should be exactly zero.

Hints

Using Python floats can introduce errors like 0.1 + 0.2 != 0.3. Consider exact arithmetic.
If you scale every quantity by the maximum number of decimal places appearing in the input, all updates become integer additions and subtractions.

Quick Overview