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 Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

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

Implement string sum and weighted city picker

Quick Overview

Implement string sum and weighted city picker evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

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.

Quick Answer: Implement string sum and weighted city picker evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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

Examples

Input: ('123', '456')

Expected Output: '579'

Explanation: Simple per-column addition with no carry.

Input: ('99', '1')

Expected Output: '100'

Explanation: Carry ripples through every column and produces a new leading digit.

Input: ('0', '0')

Expected Output: '0'

Explanation: Zero plus zero; the loop runs once, no carry.

Input: ('1', '999')

Expected Output: '1000'

Explanation: Different lengths; carry propagates past the shorter operand.

Input: ('50000', '50000')

Expected Output: '100000'

Explanation: Equal lengths producing a carry-out at the top.

Input: ('0', '12345')

Expected Output: '12345'

Explanation: Vastly different lengths; the shorter operand contributes only padding zeros.

Input: ('999999999999999999', '1')

Expected Output: '1000000000000000000'

Explanation: Long carry chain across an 18-digit operand, beyond 64-bit range — confirms no integer overflow.

Hints

Walk both strings from the least-significant (rightmost) digit toward the most-significant.
Keep a single `carry` variable; at each step add the two digits (treating a missing digit as 0) plus carry.
Continue while either index is valid OR carry is still non-zero — that final carry is how "99" + "1" becomes "100".
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

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

Expected Output: 'NYC'

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

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

Expected Output: 'NYC'

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

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

Expected Output: 'LA'

Explanation: LA owns draws 4..5; r=4 is its lower boundary.

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

Expected Output: 'LA'

Explanation: r=5 is LA's upper boundary.

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

Expected Output: 'SF'

Explanation: SF owns only draw 6 (its single unit of population).

Input: (['Solo'], [10], 7)

Expected Output: 'Solo'

Explanation: Single city owns the entire range 1..10.

Input: (['A', 'B'], [5, 5], 5)

Expected Output: 'A'

Explanation: Equal weights; r=5 is the last draw of A's range (1..5).

Input: (['A', 'B'], [5, 5], 6)

Expected Output: 'B'

Explanation: r=6 is the first draw of B's range (6..10).

Input: (['A', 'B', 'C'], [0, 4, 0], 1)

Expected Output: 'B'

Explanation: Zero-weight cities A and C are skipped; only B can be selected.

Input: (['A', 'B'], [1, 1], 3)

Expected Output:

Explanation: r=3 exceeds total=2, so the draw is out of range -> None.

Hints

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

Quick Overview