Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Uber SWE coding round, one question that apparently shows up constantly on 1point3acres. Not much else to say about the setup.

Questions Asked (1)

LeetCode 1053 (Previous Permutation With One Swap): given an array of positive integers, return the lexicographically largest permutation that is smaller than the given array, after exactly one swap. If no such permutation exists, return the original array.

Algorithms & Data Structures

Author's notes

High-frequency question apparently, which made me more nervous than I should've been.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Scan from right to left to find the first index i where nums[i] > nums[i+1], as this is the point where a swap can create a smaller permutation. Then find the largest value to the right of i that is smaller than nums[i], choosing the rightmost occurrence if duplicates exist, and swap them. If no such i exists, the array is already the smallest permutation, so return it unchanged.

Pro tip: Emphasize that picking the rightmost occurrence of the largest smaller value ensures the result is the lexicographically largest possible after the swap. Also, mention that the algorithm runs in O(n) time and O(1) space, which is optimal.

1. Identify the pivot

Traverse the array from right to left and find the first index i where nums[i] > nums[i+1]. If no such index exists, the array is already the smallest permutation, so return it as is.

2. Find the swap candidate

Among the elements to the right of i, find the largest value that is strictly less than nums[i]. If there are multiple occurrences, choose the rightmost one to maximize the resulting permutation.

3. Perform the swap

Swap nums[i] with the chosen element. This yields the lexicographically largest permutation smaller than the original.

4. Return the result

Return the modified array. If no swap was performed, return the original array.

Key Points to Mention

Lexicographical order and how to compare permutations.
The importance of scanning from right to left to find the first decreasing pair.
Handling duplicates by selecting the rightmost occurrence of the largest smaller value.
Time complexity: O(n) single pass; space complexity: O(1) in-place.
Edge cases: strictly increasing array (no previous permutation), strictly decreasing array, and arrays with duplicates.
Proof of correctness: why the algorithm yields the lexicographically largest smaller permutation.

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