Implement string sum and weighted city picker

Q: Implement string sum and weighted city picker

This question evaluates a candidate's competency in numeric string manipulation and algorithmic design for probabilistic sampling, specifically big‑integer arithmetic implemented via strings and weighted random selection over dynamic datasets.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Implement string sum and weighted city picker

Overview

Comments (0)