Uber·Software Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Phone screen for a SWE role at Uber, basically a warm-up coding round centered on array manipulation. Nothing too wild but the follow-up they throw in can trip you up if you haven't thought about it beforehand.

Questions Asked (2)

Given a sorted integer array that may contain negative numbers, return a new array of the squared values in non-decreasing order. You must do it in linear time, no squaring then sorting.

Algorithms & Data Structures

Author's notes

I knew the two-pointer approach going in, but I fumbled the initialization for a second because I kept second-guessing which end to write into first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a two-pointer technique starting from both ends of the sorted array, comparing absolute values and placing the larger square at the end of the result array. This achieves O(n) time and O(n) space without explicitly sorting.

Pro tip: Clarify that the input array is sorted in non-decreasing order and may contain negative numbers; the key insight is that the largest squared values come from the extremes. Mention that you can optimize space by reusing the input array if allowed, but typically a new array is required.

1. Understand the problem and constraints

Confirm that the array is sorted, may contain negatives, and that the output must be in non-decreasing order of squares. Note the linear time requirement.

2. Identify the two-pointer strategy

Recognize that the largest square must come from either the leftmost (most negative) or rightmost (most positive) element. Use two pointers to compare absolute values.

3. Initialize pointers and result array

Set left pointer at 0, right pointer at n-1, and create a result array of size n. Use a write pointer starting at n-1 to fill from the end.

4. Iterate and fill result

While left <= right, compare absolute values of elements at left and right. Place the larger square at the write position, move the corresponding pointer, and decrement write position.

5. Return the result

After the loop, the result array contains squares in non-decreasing order. Return it.

Key Points to Mention

Two-pointer technique from both ends
Comparing absolute values to determine larger square
Filling result array from the end to avoid extra sorting
Time complexity O(n) and space complexity O(n)
Handling edge cases: empty array, all negatives, all positives, duplicates
Avoiding the naive approach of squaring then sorting (O(n log n))

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

Follow-up: instead of returning the full sorted squares array, how would you find just the K-th smallest square value?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This one I actually had pre-thought, so it went smoother.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify that the input is a sorted array of integers (possibly negative) and we need the K-th smallest square. Then propose a two-pointer approach from both ends to generate squares in sorted order, or a binary search on the value range to count how many squares are ≤ a candidate. Discuss trade-offs between O(n) time with O(1) space (two-pointer) and O(n log n) time with O(1) space (binary search).

Pro tip: Mention that the two-pointer method can be adapted to find the K-th smallest without generating all squares by stopping early, but binary search is often simpler to reason about and avoids potential off-by-one errors. Also, consider edge cases like duplicate squares and negative numbers.

1. Clarify the problem and constraints

Confirm that the input array is sorted in non-decreasing order, may contain negative numbers, and that K is 1-indexed. Ask about the expected time/space complexity and whether duplicates are allowed.

2. Discuss brute force and its limitations

Mention that computing all squares, sorting them, and picking the K-th element takes O(n log n) time and O(n) space, which is suboptimal. This sets the stage for better approaches.

3. Propose the two-pointer approach

Use two pointers starting at both ends of the array, compare absolute values, and generate squares in non-decreasing order. To find the K-th smallest, you can either generate all squares and pick the K-th (O(n) time, O(n) space) or use a modified approach to stop after K steps (O(K) time, O(1) space if not storing all).

4. Propose binary search on value range

The K-th smallest square lies between 0 and max(|first|, |last|)^2. Binary search on the value, and for each candidate, count how many squares are ≤ candidate using two pointers. Adjust the search range based on the count. This takes O(n log(max_value)) time and O(1) space.

5. Compare trade-offs and conclude

Highlight that the two-pointer method is optimal for small K, while binary search is better when K is large or when we want a predictable O(n log M) time. Choose based on constraints and mention potential optimizations like early termination.

Key Points to Mention

The array is sorted, so squares are not necessarily sorted due to negative numbers.
Two-pointer technique leverages the sorted order to merge squares from both ends.
Binary search on the value range requires a counting function that runs in O(n) using two pointers.
Time complexity: two-pointer O(n) or O(K) if stopping early; binary search O(n log M) where M is max absolute value.
Space complexity: O(1) extra space for both approaches if not storing all squares.
Edge cases: K=1, K=n, all negative, all positive, duplicates, and zero.

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