Meta·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Meta coding interview, one question the whole session. Algorithmic problem with a tight efficiency constraint, felt like they wanted to see if you'd actually think about it or just brute force it.

Questions Asked (1)

Given a non-negative integer, perform at most one swap of two digits to produce the largest possible value. Solve it in linear time relative to the number of digits.

Algorithms & Data Structures

Author's notes

My first instinct was the naive approach, try every pair of digits, which is obviously not O(L).

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify that the input is a non-negative integer and we can swap at most one pair of digits. Then, devise a linear-time algorithm by scanning from the right to track the maximum digit seen so far and the best swap candidate, ensuring we pick the leftmost digit that can be swapped with a larger digit to its right to maximize the number.

Pro tip: Mention that leading zeros are not a concern because swapping to increase the number will never introduce a leading zero unless the number is zero, and emphasize that the algorithm must handle the case where no swap improves the number (e.g., digits are non-increasing).

1. Clarify requirements and edge cases

Confirm that the input is a non-negative integer, we can perform at most one swap, and we want the largest possible value. Discuss edge cases: single-digit number, all digits same, digits in non-increasing order (e.g., 54321), and numbers with zeros.

2. Convert to digit array

Convert the integer to a string or array of digits to allow easy manipulation and indexing. This also helps in discussing time complexity relative to the number of digits.

3. Design linear-time algorithm

Scan from right to left, keeping track of the maximum digit seen so far and its index. For each digit, if it is less than the maximum digit seen, record it as a potential swap candidate (the leftmost such digit will yield the largest increase).

4. Perform swap and return result

If a swap candidate is found, swap it with the rightmost occurrence of the maximum digit to its right. If no candidate, return the original number. Convert the digit array back to an integer.

5. Analyze complexity and test

State that the algorithm runs in O(n) time and O(n) space (or O(1) extra space if using string manipulation). Walk through a few examples to verify correctness, such as 2736 -> 7236, 9973 -> 9973, 98368 -> 98863.

Key Points to Mention

Linear time complexity O(n) where n is the number of digits, achieved by a single pass from right to left.
Greedy strategy: swap the leftmost digit that has a larger digit to its right with the largest possible digit to its right.
Handling edge cases: no swap needed (digits non-increasing), single digit, and numbers with zeros.
Space complexity: O(n) for digit array, but can be optimized to O(1) extra space if using string manipulation in languages like Python.
Correctness proof: swapping the leftmost smaller digit with the maximum digit to its right maximizes the number because it increases the most significant digit possible.
Avoiding unnecessary swaps: if no larger digit exists to the right of any digit, return the original number.

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