← Chime Interview Insights

Chime·Backend Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026Remote

Summary

Chime backend interview with a coding round that had two parts to the same problem. The first part was manageable but the second part with shuffled input caught me off guard and I spent way too long on it.

Questions Asked (2)

Q1

Given an integer n and a string formed by concatenating n-1 numbers from the range 1 to n in sorted order, find the missing number.

Algorithms & Data Structures
Author's notes

Part one felt doable.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem: the string is a concatenation of numbers from 1 to n with one missing, but the concatenation makes it ambiguous to parse. The key insight is to use the sum of integers from 1 to n and subtract the sum of the digits in the string, but that doesn't directly give the missing number because digits are not numbers. Instead, we need to consider that the string is formed by concatenating the decimal representations of the numbers. The missing number can be found by comparing the expected concatenated string with the given string, but that's inefficient. A better approach is to use the fact that the sum of the numbers from 1 to n is n(n+1)/2, and the sum of the digits in the string is the sum of the digits of all numbers except the missing one. However, the sum of digits is not directly the sum of numbers. So we need to parse the string to extract the numbers, but the parsing is ambiguous because numbers can have multiple digits. The problem is essentially: given a string that is the concatenation of a permutation of a subset of {1,...,n} of size n-1 in sorted order, find the missing number. Since the numbers are in sorted order, the string is the concatenation of the sorted numbers except one. We can iterate through possible missing numbers and check if the concatenation of the remaining numbers matches the string. But that's O(n^2) if done naively. A more efficient way is to use the fact that the string is sorted, so we can parse it by trying to match numbers in increasing order. We can use a greedy approach: start from 1, try to match the next number in the string, if it matches, move to the next number; if not, that number is missing. But careful: the missing number could be at the end. So we can iterate from 1 to n, and for each number, check if its string representation is a prefix of the remaining string. If it is, consume it; if not, that number is missing. This works because the numbers are in sorted order and we know the range. So the algorithm is: initialize expected = 1, index = 0; while index < len(s): if str(expected) is a prefix of s[index:], then index += len(str(expected)), expected += 1; else, the missing number is expected, break. If we reach the end, the missing number is n. This is O(n) time and O(1) space. We should also handle edge cases like n=1 (empty string, missing number is 1) and n=2 (string is either '1' or '2', missing is the other).

Pro tip: Mention that the problem is essentially about parsing a sorted concatenation, and that a greedy approach works because the numbers are in increasing order. Also, clarify that the string is formed by concatenating the decimal representations, so multi-digit numbers are possible. This shows attention to detail.

1. Clarify the problem and constraints

Confirm that the string is a concatenation of n-1 distinct numbers from 1 to n in sorted order, and that numbers are concatenated as decimal strings. Ask about edge cases like n=1 or n=2.

2. Identify the key insight

Since the numbers are in sorted order, the string is a sorted concatenation. We can parse it by greedily matching the expected next number in the sequence.

3. Design the algorithm

Iterate expected number from 1 to n, and maintain a pointer in the string. If the string representation of the expected number matches the substring at the pointer, advance the pointer and increment expected; otherwise, the expected number is missing.

4. Handle edge cases and complexity

If the loop completes without finding a missing number, the missing number is n. The algorithm runs in O(n) time and O(1) space, which is optimal.

5. Test with examples

Walk through examples like n=5, missing 3: string '1245' -> expected 1 matches, expected 2 matches, expected 3 does not match '4', so missing is 3. Also test n=1 (empty string) and n=2 (string '1' or '2').

Key Points to Mention

  • The string is a concatenation of decimal representations, so multi-digit numbers are possible.
  • The numbers are in sorted order, which allows a greedy parsing approach.
  • Time complexity is O(n) and space complexity is O(1).
  • Edge cases: n=1 (empty string, missing 1), n=2 (string '1' or '2'), and missing number at the end.
  • The algorithm can be implemented by comparing string prefixes without converting the entire string to numbers.
  • Clarify that the input string length is not necessarily n-1 because numbers can have multiple digits.

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

Q2

Same problem as above but now the numbers were shuffled before concatenation. Find the missing number from the resulting unsorted string.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

This is where I got stuck.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Since the numbers are shuffled, we cannot rely on order. Instead, use the mathematical property that the sum of the original sequence is known, and the sum of the shuffled string's digits (or numbers) can be computed. The missing number is the difference between the expected sum and the actual sum. Alternatively, if the string contains concatenated numbers without separators, we need to parse the string into possible numbers, which may require backtracking or a greedy approach based on the known range.

Pro tip: Clarify the input format first: are the numbers concatenated as strings without delimiters, or are they space-separated? This drastically changes the solution. Also, mention that if the range is 1 to n, the sum formula n(n+1)/2 gives O(1) expected sum, making the solution efficient.

1. Clarify the problem constraints

Ask about the input format: are numbers separated by spaces or concatenated directly? What is the range of numbers (e.g., 1 to n)? Are there leading zeros? This determines the parsing strategy.

2. Determine expected sum

If the original sequence is known (e.g., 1 to n), compute the expected sum using the formula n(n+1)/2. If the sequence is arbitrary, you need the original set of numbers.

3. Parse the shuffled string

If numbers are concatenated without delimiters, use backtracking to try all possible partitions into valid numbers within the known range. If delimiters exist, simply split and convert to integers.

4. Compute actual sum and find missing

Sum the parsed numbers and subtract from the expected sum. The difference is the missing number. If parsing is ambiguous, ensure the missing number is consistent across all valid partitions.

5. Analyze time and space complexity

Discuss the complexity: O(n) for sum and split, but O(2^n) for backtracking in the worst case. Mention optimizations like pruning or using a set for validation.

Key Points to Mention

  • Summation approach: expected sum minus actual sum gives the missing number.
  • Handling concatenated numbers without delimiters requires parsing/backtracking.
  • Time complexity: O(n) for simple cases, exponential for ambiguous parsing.
  • Edge cases: leading zeros, numbers with multiple digits, empty string.
  • Alternative: use XOR if numbers are 1 to n and no duplicates, but sum is simpler.
  • Trade-offs: parsing ambiguity vs. assuming delimiters; memory vs. time.

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