Implement string sum and weighted city picker

Part A — Add two numbers represented as strings: Given two non‑negative integers provided as decimal strings s and t, return their sum as a string without using built‑in big‑integer types. Assume no leading zeros except for the string "0". Specify the function signature, outline edge cases (e.g., vastly different lengths, long carries, very large inputs up to 10^5 digits), provide a few example I/O pairs, and analyze time and space complexity.

Part B — Design a weighted random city picker: You are given a list of pairs (cityName, population). Implement an API with init(cities, populations) and pickCity() such that pickCity() returns a city with probability equal to its population divided by the total population. Achieve O(n) preprocessing and O(log n) (or better) per pick. Discuss how you would validate randomness, handle large totals without precision loss, and extend the design to support dynamic updates (population changes, insertions, deletions), including complexity trade‑offs.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Add Two Numbers Represented as Strings

Given two non-negative integers provided as decimal strings s and t, return their sum as a string. You may not convert the whole strings to a built-in big-integer type and add — process the digits manually. Assume there are no leading zeros except for the value "0" itself.

The inputs can be very large (up to 10^5 digits), so an O(max(|s|, |t|)) digit-by-digit addition with carry propagation is required.

Examples:

• s = "123", t = "456" -> "579"
• s = "99", t = "1" -> "100" (carry ripples through)
• s = "0", t = "12345" -> "12345" (vastly different lengths)

This is the classic 'add strings' problem (Meta phone screen, Part A).

Constraints

• 1 <= |s|, |t| <= 10^5
• s and t contain only digits '0'-'9'
• No leading zeros except the literal "0"
• Do not convert the entire string to a built-in big integer to add

Hints

1. Walk both strings from the least-significant (rightmost) digit toward the most-significant.
2. Keep a single carry variable; at each step add the two digits (treating a missing digit as 0) plus carry.
3. Continue while either index is valid OR carry is still non-zero — that final carry is how "99" + "1" becomes "100".
4. Build the result in reverse, then reverse it once at the end (O(n)) rather than prepending each digit (O(n^2)).

Weighted Random City Picker (Deterministic Core)

You are given a list of cities and their populations. A weighted picker pickCity() must return a city with probability equal to its population divided by the total population, using O(n) preprocessing and O(log n) per pick.

The standard implementation builds the prefix sums of the populations, draws a uniform integer r in [1, total], and binary-searches for the first city whose cumulative population is >= r. City i then 'owns' exactly population[i] of the total integer draw values, which is precisely its target probability.

Because the random draw itself is not deterministic, this problem asks you to implement the verifiable core: pickCityForDraw(cities, populations, r) — given the draw value r, return the city it maps to (or None if r is out of range or the total is 0). Get this right and wrapping it with a uniform RNG over [1, total] yields the full weighted picker.

Follow-ups to discuss: validating randomness (chi-squared / empirical frequency tests), avoiding precision loss on huge totals (use integer draws, not floats), and supporting dynamic updates (a Fenwick/BIT or balanced BST over weights gives O(log n) update + pick; an alias table gives O(1) pick but O(n) rebuild on updates).

Constraints

• 1 <= n <= 10^5 cities
• 0 <= population[i]; populations and cities are parallel arrays of equal length
• 1 <= r <= total = sum(populations) for a valid draw; otherwise return None
• Cities with population 0 must never be selected

Examples

Example 1

Input: (['NYC', 'LA', 'SF'], [3, 2, 1], 1)
Output: 'NYC'

Explanation: NYC owns draws 1..3; r=1 is the lower boundary of NYC.

Example 2

Input: (['NYC', 'LA', 'SF'], [3, 2, 1], 3)
Output: 'NYC'

Explanation: r=3 is the upper boundary of NYC's range (1..3).

Hints

1. Build a prefix-sum array where prefix[i] = population[0] + ... + population[i]; city i owns the half-open count range (prefix[i-1], prefix[i]].
2. For a draw r, you want the FIRST index whose prefix sum is >= r — that is exactly bisect_left on the prefix array.
3. Use integer draws over [1, total] rather than a float in [0, 1) to avoid precision loss when totals are huge.
4. A zero-population city contributes no new range (its prefix equals the previous one), so bisect_left naturally skips it — never selecting it.
5. For dynamic updates, replace the static prefix array with a Fenwick tree (BIT): O(log n) point update and O(log n) weighted search.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Part A — Add two numbers represented as strings: Given two non‑negative integers provided as decimal strings s and t, return their sum as a string without using built‑in big‑integer types. Assume no leading zeros except for the string "0". Specify the function signature, outline edge cases (e.g., vastly different lengths, long carries, very large inputs up to 10^5 digits), provide a few example I/O pairs, and analyze time and space complexity. Part B — Design a weighted random city picker: You are given a list of pairs (cityName, population). Implement an API with init(cities, populations) and pickCity() such that pickCity() returns a city with probability equal to its population divided by ...

Recommended Approach

Precompute prefix sums of positive weights. To pick, draw a uniform integer or float r in [1, total] and binary-search the first prefix sum >= r. The interval length assigned to each index equals its weight, so probability is proportional to weight.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Preprocessing: O(n) time and O(n) space. Pick: O(log n). For extremely high query volume, alias sampling can reduce pick time to O(1) with O(n) preprocessing.

Edge Cases and Tests

Single weight, very large total weight, invalid zero/negative weights, reproducible random seeds in tests, and empirical distribution checks.