Meta·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Jun 2026

Summary

Meta SWE coding round with two back-to-back problems, one algorithmic and one design-heavy. The second question especially felt like it kept growing the longer I talked, which was both interesting and a little exhausting.

Questions Asked (2)

Given two non-negative integers as decimal strings, return their sum as a string without using any built-in big-integer libraries. Walk through the function signature, edge cases, example inputs and outputs, and time/space complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I've done grade-school addition in code before so the core loop wasn't the problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the function signature and constraints, then simulate grade-school addition by iterating from the least significant digit with a carry. Handle edge cases like empty strings, leading zeros, and unequal lengths, and analyze time/space complexity.

Pro tip: Mention that you can optimize space by reusing the longer string or using a StringBuilder, and discuss trade-offs between iterative and recursive approaches. Also, proactively ask about input validation and whether the output should preserve leading zeros.

1. Clarify requirements and signature

Confirm input types (non-negative decimal strings), output type (string), and constraints (no built-in big integer libraries). Define the function signature, e.g., string addStrings(string num1, string num2).

2. Outline algorithm

Explain the two-pointer approach from the end of both strings, computing sum digit by digit with a carry. Build the result in reverse and then reverse it, or prepend to a StringBuilder.

3. Identify edge cases

List edge cases: empty strings, strings with leading zeros, one string longer than the other, carry at the end (e.g., '99' + '1' = '100'), and very long strings (performance).

4. Walk through examples

Provide concrete examples like '123' + '456' = '579', '99' + '1' = '100', and '0' + '0' = '0'. Trace the algorithm step by step to demonstrate correctness.

5. Analyze complexity

State time complexity O(max(n, m)) where n and m are lengths of the input strings, and space complexity O(max(n, m)) for the output string. Mention that space can be O(1) extra if modifying input is allowed.

Key Points to Mention

Two-pointer technique starting from the least significant digit
Carry propagation and handling final carry
Edge cases: empty strings, leading zeros, unequal lengths
Time complexity O(max(n, m)) and space complexity O(max(n, m))
Avoiding built-in big integer libraries by manual digit manipulation
Potential optimization: reuse longer string or use StringBuilder for efficiency

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Design a weighted random city picker: given a list of city names and their populations, implement an init function and a pickCity function that returns each city with probability proportional to its population. Target O(n) preprocessing and O(log n) or better per pick. Also discuss how you'd validate randomness, avoid precision issues with large population totals, and support dynamic updates like insertions, deletions, and population changes.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

Prefix sums plus binary search got me through the core of it pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a prefix-sum array with binary search for O(n) init and O(log n) pick. For dynamic updates, discuss a Fenwick tree (BIT) with O(log n) updates and picks, and address precision and validation with concrete techniques.

Pro tip: Mention using 64-bit integers for prefix sums to avoid floating-point precision issues, and propose a chi-squared test to validate randomness—this shows depth beyond the basic algorithm.

1. Clarify requirements and constraints

Ask about input size, update frequency, precision requirements, and whether the city list is static or dynamic. This determines the choice of data structure.

2. Propose static solution

Describe building a prefix-sum array of populations in O(n) time, then for each pick, generate a random number in [0, total) and binary search for the city. This gives O(log n) per pick.

3. Address dynamic updates

For insertions, deletions, and population changes, suggest a Fenwick tree (BIT) to maintain prefix sums, enabling O(log n) updates and O(log n) picks. Mention that a balanced BST with subtree sums is an alternative.

4. Discuss precision and validation

Use 64-bit integers for sums to avoid overflow and floating-point errors. Validate randomness via chi-squared test or by comparing empirical frequencies to expected probabilities over many trials.

5. Analyze trade-offs and edge cases

Compare prefix-sum + binary search vs. Fenwick tree in terms of update frequency, memory, and implementation complexity. Handle edge cases like zero populations, empty list, and total population overflow.

Key Points to Mention

Prefix-sum array with binary search for O(n) init and O(log n) pick.
Fenwick tree (BIT) for dynamic updates with O(log n) insert, delete, update, and pick.
Use 64-bit integers for population sums to avoid overflow and precision loss.
Random number generation: use uniform distribution over [0, total) and handle boundaries correctly.
Validation: chi-squared test or empirical frequency comparison to expected probabilities.
Edge cases: zero populations, empty city list, and total population exceeding 2^53 (JavaScript) or 2^63 (64-bit).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.