Apple: Unit Ratio Queries Across Independent Unit Families with Modular Answers

Quick Overview

A graph coding problem: given multiplicative conversion factors between units that split into independent families, answer queries for how many units of one unit equal one unit of another, returning the ratio modulo a prime or -1 when the units cannot be converted. It tests graph traversal over a forest and modular arithmetic.

Unit Ratio Queries Across Independent Unit Families with Modular Answers

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

There are `n` units of measure, numbered `0` to `n - 1`. The units fall into several independent families: units in the same family can be converted into one another, but a unit can never be converted into a unit of a different family (for example, length units form one family and temperature units form another). In this problem every conversion is a pure multiplicative factor; scales that also need an offset are out of scope. You are given a list `conversions`, where `conversions[i] = [source, target, factor]` states that one unit of `source` equals exactly `factor` units of `target`. Every conversion also works in reverse: one unit of `target` equals `1/factor` units of `source`. Conversions chain: if one unit of `a` equals 2 units of `b`, and one unit of `b` equals 3 units of `c`, then one unit of `a` equals 6 units of `c`. You are also given a list `queries`, where `queries[j] = [a, b]` asks: how many units of `b` equal one unit of `a`? ### Function Signature ```python def unit_ratios(n: int, conversions: list[list[int]], queries: list[list[int]]) -> list[int]: ``` ### Rules - Two units belong to the same family exactly when a chain of conversions, each usable in either direction, connects them. A unit that appears in no conversion forms a family by itself. - If `a` and `b` belong to the same family, write the exact answer as a fraction `p / q` in lowest terms, and return `(p * q_inv) % 1_000_000_007`, where `q_inv` is the modular multiplicative inverse of `q` modulo the prime `1_000_000_007`. - If `a == b`, the answer is `1`. - If `a` and `b` belong to different families, the answer is `-1`. - Return one answer per query, in the same order as `queries`. ### Constraints - `1 <= n <= 10**5` - `0 <= len(conversions) <= n - 1` - `0 <= source, target <= n - 1` and `source != target` - `1 <= factor <= 10**9` - The conversions contain no cycle: between any two units there is at most one chain of conversions (ignoring direction), and no pair of units is given more than one conversion. Each family is therefore a tree, and the input is never contradictory. - `1 <= len(queries) <= 10**5` - `0 <= a, b <= n - 1` - Every answer is `-1` or an integer in `[0, 1_000_000_006]`, which fits in a 32-bit signed integer. The product of two such residues can reach about `10**18`, which exceeds the 32-bit range, so languages without arbitrary-precision integers need 64-bit arithmetic for intermediate products. ### Examples **Example 1** ```text Input: n = 5 conversions = [[0, 1, 2], [1, 2, 3], [3, 4, 4]] queries = [[0, 2], [2, 0], [1, 0], [3, 4], [4, 3], [0, 4], [2, 2]] Output: [6, 166666668, 500000004, 4, 250000002, -1, 1] ``` Units 0, 1 and 2 form one family, and units 3 and 4 form another. One unit of 0 is 2 units of 1, which is 6 units of 2, so `[0, 2]` gives `6`. The query `[2, 0]` asks for `1/6`, which is `166666668` because `6 * 166666668 = 1000000008`, which is 1 modulo `1_000_000_007`. Likewise `[1, 0]` is `1/2`, giving `500000004`; `[3, 4]` is `4`; `[4, 3]` is `1/4`, giving `250000002`. The query `[0, 4]` crosses families, so it gives `-1`, and `[2, 2]` gives `1`. **Example 2** ```text Input: n = 3 conversions = [[0, 1, 2], [0, 2, 3]] queries = [[1, 2], [2, 1]] Output: [500000005, 666666672] ``` One unit of 1 is `1/2` unit of 0, which is `3/2` units of 2, and `3 * 500000004 = 1500000012`, which is `500000005` modulo `1_000_000_007`. One unit of 2 is `1/3` unit of 0, which is `2/3` units of 1, and `2 * 333333336 = 666666672`. **Example 3** ```text Input: n = 4 conversions = [[0, 1, 1000000000], [1, 2, 1000000000]] queries = [[0, 2], [3, 3], [3, 0]] Output: [49, 1, -1] ``` One unit of 0 is `10**18` units of 2. Since `10**18 = (10**9 + 7) * (10**9 - 7) + 49`, the answer is `49`. Unit 3 appears in no conversion, so it forms its own family: `[3, 3]` gives `1` and `[3, 0]` gives `-1`.

Overview: A graph coding problem: given multiplicative conversion factors between units that split into independent families, answer queries for how many units of one unit equal one unit of another, returning the ratio modulo a prime or -1 when the units cannot be converted. It tests graph traversal over a forest and modular arithmetic.

There are `n` units of measure, numbered `0` to `n - 1`. The units fall into several independent families: units in the same family can be converted into one another, but a unit can never be converted into a unit of a different family (for example, length units form one family and temperature units form another). Every conversion is a pure multiplicative factor; scales that also need an offset are out of scope. You are given a list `conversions`, where `conversions[i] = [source, target, factor]` states that one unit of `source` equals exactly `factor` units of `target`. Every conversion also works in reverse: one unit of `target` equals `1/factor` units of `source`. Conversions chain: if one unit of `a` equals 2 units of `b`, and one unit of `b` equals 3 units of `c`, then one unit of `a` equals 6 units of `c`. You are also given a list `queries`, where `queries[j] = [a, b]` asks: how many units of `b` equal one unit of `a`? Implement `unit_ratios(n, conversions, queries)`. It returns a list with one answer per query, in the same order as `queries`, following these rules: - Two units belong to the same family exactly when a chain of conversions, each usable in either direction, connects them. A unit that appears in no conversion forms a family by itself. - If `a` and `b` belong to the same family, write the exact answer as a fraction `p / q` in lowest terms and return `(p * q_inv) % 1_000_000_007`, where `q_inv` is the modular multiplicative inverse of `q` modulo the prime `1_000_000_007`. - If `a == b`, the answer is `1`. - If `a` and `b` belong to different families, the answer is `-1`. Every answer is `-1` or an integer in `[0, 1_000_000_006]`, so every returned value fits in a 32-bit signed integer. The exact ratio itself can be far larger than any machine integer (Example 3 is already `10**18`), and the product of two residues can reach about `10**18`, which exceeds `2^31 - 1`. Intermediate products therefore need 64-bit arithmetic (`long` in Java, `long long` in C++); in JavaScript keep every intermediate product exact, for example with `BigInt` or a split multiplication. ### Example 1 ```text Input: n = 5 conversions = [[0, 1, 2], [1, 2, 3], [3, 4, 4]] queries = [[0, 2], [2, 0], [1, 0], [3, 4], [4, 3], [0, 4], [2, 2]] Output: [6, 166666668, 500000004, 4, 250000002, -1, 1] ``` Units 0, 1 and 2 form one family, and units 3 and 4 form another. One unit of 0 is 2 units of 1, which is 6 units of 2, so `[0, 2]` gives `6`. The query `[2, 0]` asks for `1/6`, which is `166666668` because `6 * 166666668 = 1000000008`, which is 1 modulo `1_000_000_007`. Likewise `[1, 0]` is `1/2`, giving `500000004`; `[3, 4]` is `4`; `[4, 3]` is `1/4`, giving `250000002`. The query `[0, 4]` crosses families, so it gives `-1`, and `[2, 2]` gives `1`. ### Example 2 ```text Input: n = 3 conversions = [[0, 1, 2], [0, 2, 3]] queries = [[1, 2], [2, 1]] Output: [500000005, 666666672] ``` One unit of 1 is `1/2` unit of 0, which is `3/2` units of 2, and `3 * 500000004 = 1500000012`, which is `500000005` modulo `1_000_000_007`. One unit of 2 is `1/3` unit of 0, which is `2/3` units of 1, and `2 * 333333336 = 666666672`. ### Example 3 ```text Input: n = 4 conversions = [[0, 1, 1000000000], [1, 2, 1000000000]] queries = [[0, 2], [3, 3], [3, 0]] Output: [49, 1, -1] ``` One unit of 0 is `10**18` units of 2. Since `10**18 = (10**9 + 7) * (10**9 - 7) + 49`, the answer is `49`. Unit 3 appears in no conversion, so it forms its own family: `[3, 3]` gives `1` and `[3, 0]` gives `-1`. ### Constraints - `1 <= n <= 10**5` - `0 <= len(conversions) <= n - 1` - `0 <= source, target <= n - 1` and `source != target` - `1 <= factor <= 10**9` - The conversions contain no cycle: between any two units there is at most one chain of conversions (ignoring direction), and no pair of units is given more than one conversion. Each family is therefore a tree, and the input is never contradictory. - `1 <= len(queries) <= 10**5` - `0 <= a, b <= n - 1` - Every answer is `-1` or an integer in `[0, 1_000_000_006]`, which fits in a 32-bit signed integer. The product of two such residues can reach about `10**18`, which exceeds the 32-bit range, so languages without arbitrary-precision integers need 64-bit arithmetic for intermediate products.

Constraints

1 <= n <= 10**5
0 <= len(conversions) <= n - 1
0 <= source, target <= n - 1 and source != target
1 <= factor <= 10**9
The conversions contain no cycle: between any two units there is at most one chain of conversions (ignoring direction), and no pair of units is given more than one conversion. Each family is therefore a tree, and the input is never contradictory.
1 <= len(queries) <= 10**5
0 <= a, b <= n - 1
Every answer is -1 or an integer in [0, 1_000_000_006], which fits in a 32-bit signed integer. The product of two such residues can reach about 10**18, which exceeds the 32-bit range, so languages without arbitrary-precision integers need 64-bit arithmetic for intermediate products (long in Java, long long in C++).

Examples

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

Expected Output: [6, 166666668, 500000004, 4, 250000002, -1, 1]

Explanation: Source Example 1: two families, reciprocal answers 1/6, 1/2 and 1/4 via modular inverses, a cross-family -1 and a self query.

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

Expected Output: [500000005, 666666672]

Explanation: Source Example 2: the path from 1 to 2 goes up to unit 0 and back down, giving 3/2 and 2/3.

Hints

Every conversion can be used in both directions: moving from target back to source divides by the factor instead of multiplying by it.
A chain of factors of 10**9 makes the exact ratio astronomically large, so keep every quantity as a residue modulo 1_000_000_007. Because every factor is between 1 and 10**9, none is divisible by the prime, so every division can be carried out with a modular inverse.
Two units in different families answer -1, while a unit asked about itself answers 1 even when it appears in no conversion.

Approach

Algorithm: treat every conversion [source, target, factor] as two directed adjacency entries: source -> target multiplies by factor, and target -> source divides by factor. Scan units 0..n-1; each unvisited unit becomes the root of a new family and an iterative depth-first search (explicit stack) labels every reachable unit with that root. For every reached unit v it records r[v] = the number of units of v that equal one unit of the root, kept as a pair of residues num[v] / den[v] modulo P = 1_000_000_007: crossing a forward edge multiplies the numerator by factor, crossing a reverse edge multiplies the denominator by factor.

Invariant: when v is labelled, num[v] * inverse(den[v]) is congruent to the exact rational r[v]. Each family is a tree, so v is reached along its unique path from the root and r[v] is exactly the product of the edge ratios along that path; no conflicting second path exists.

Answering a query [a, b]: if a == b return 1; if the two units have different roots return -1. Otherwise one unit of a equals 1 / r[a] root units, which equals r[b] / r[a] units of b, so the answer is num[b] * den[a] times the modular inverse of den[b] * num[a], computed with Fermat's little theorem as x^(P-2) mod P.

Correctness of the modular value: every factor lies in [1, 10**9], below the prime P, so no product of factors is divisible by P and every inverse exists. Reduction modulo P is a ring homomorphism on fractions whose denominator is coprime to P, so the unreduced fraction the search builds (for example 18/8) maps to the same residue as its lowest-terms form p/q (9/4), which is exactly (p * q_inv) % P as required.

Edge cases: units in no conversion are their own family (self query 1, anything else -1); empty conversions; duplicate queries are answered independently in order; residue products reach about 10**18, so Java and C++ use 64-bit integers and JavaScript splits each multiplication so every intermediate stays below 2^53; the explicit stack avoids recursion-depth failures on long chains.

Time complexity:

O(n + m + q log P), where m = len(conversions), q = len(queries) and P = 1_000_000_007

Space complexity:

O(n + m)