Chime·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Chime software engineer interview with a pretty clever string/number puzzle that had two parts. The second part is where things get interesting and a bit annoying.

Questions Asked (1)

You're given an integer n and a digit string formed by concatenating the numbers 1 through n in order, but one number k is missing. Part A: find k when the order is preserved. Part B: find k when the digits are shuffled into arbitrary order. No delimiters between numbers. Walk through your approach and complexity for both parts.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Part A felt manageable pretty quickly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

For Part A, use the fact that the total length of the concatenated string is known, so the missing number can be found by comparing the expected length with the actual length and using binary search or arithmetic to locate the missing number. For Part B, since order is lost, use digit frequency counts: compute the expected digit counts for 1..n, subtract the actual counts, and deduce the missing number from the difference, handling carries and multi-digit numbers carefully.

Pro tip: Clarify with the interviewer whether n is given as part of the input or must be inferred; in Part B, the missing number might be ambiguous if multiple numbers have the same digit multiset, so discuss how to resolve ambiguity (e.g., by assuming uniqueness or using additional constraints).

1. Understand the problem and constraints

Restate the problem: we have a string formed by concatenating 1..n with one number k missing. For Part A, order is preserved; for Part B, digits are shuffled. Ask about constraints: range of n, whether n is given, and if the missing number is guaranteed unique.

2. Part A: Order preserved approach

Compute the expected total length of the concatenated string for 1..n. Compare with actual length to determine the number of digits of k. Then parse the string sequentially, comparing each number to the expected sequence; when a mismatch occurs, identify k. Alternatively, use binary search on the position to find the missing number efficiently.

3. Part A: Complexity analysis

The parsing approach is O(n) time and O(1) extra space. Binary search can reduce time to O(log n) by leveraging the monotonicity of cumulative digit counts, but requires careful handling of digit boundaries.

4. Part B: Shuffled digits approach

Compute the expected frequency of each digit (0-9) in the concatenation of 1..n. Compute the actual frequencies from the given string. The difference gives the digit multiset of k. Then find the number k that has exactly that multiset and is in the range 1..n. If multiple candidates, discuss ambiguity resolution.

5. Part B: Complexity and edge cases

Computing expected frequencies takes O(n) time (or O(log n) with digit DP) and O(1) space. Finding k from the digit multiset can be done by checking numbers with the same length, which is O(n) in worst case. Discuss edge cases: leading zeros, numbers with repeated digits, and n=1.

Key Points to Mention

Digit counting and frequency analysis for Part B
Binary search on cumulative digit counts for Part A
Handling multi-digit numbers and carries in digit frequency differences
Ambiguity in Part B when multiple numbers share the same digit multiset
Time and space complexity trade-offs between the two parts
Edge cases: n=1, missing number is 1 or n, numbers with zeros

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