Capital One·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Capital One SWE interview with a tricky array rotation problem. Not the hardest thing I've ever seen but the edge cases were sneaky and I didn't feel great walking out.

Questions Asked (1)

Given an array and an integer t (where t is less than the array length), a cyclic left-shift moves t elements from the end to the front. Can you determine whether, within t such operations, the array reaches a descending order at any point?

Algorithms & Data Structures

Author's notes

Spent the first few minutes just re-reading the problem because the shift direction tripped me up.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem: a cyclic left-shift by t moves the last t elements to the front, and we need to check if the array becomes strictly descending after any number of such shifts up to t. The key insight is that the array can only take on at most t+1 distinct rotations, so we can simulate each rotation and check for descending order, or use a more efficient approach by checking if the array is a rotation of a descending array and if the required shift is within t.

Pro tip: Mention that you can solve this in O(n) time by finding the rotation point where the array would be descending, then verifying if that rotation count is ≤ t. This shows you can optimize beyond brute force.

1. Clarify the operation and constraints

Confirm that a cyclic left-shift by t moves the last t elements to the front, and that we consider up to t operations (i.e., shifts by 0, 1, ..., t). Also note that t < n, where n is the array length.

2. Identify the target condition

Determine what 'descending order' means: strictly descending (each element greater than the next) or non-increasing? Clarify with the interviewer. Assume strictly descending for now.

3. Analyze possible rotations

Recognize that applying k cyclic left-shifts (0 ≤ k ≤ t) produces a rotation of the original array. There are at most t+1 distinct rotations to check.

4. Check for descending order efficiently

For each rotation, checking descending order naively takes O(n), leading to O(t*n) time. Instead, find the unique rotation that could be descending by locating the maximum element and verifying the sequence is strictly decreasing from there. Then check if the required shift is ≤ t.

5. Handle edge cases and conclude

Consider edge cases: array already descending (shift 0), t=0, duplicate elements (if non-increasing allowed), and arrays that cannot be descending. Return true if any valid rotation within t shifts yields descending order, else false.

Key Points to Mention

Cyclic left-shift by t is equivalent to rotating the array left by t positions.
The array can only be descending if it is a rotation of a strictly descending sequence.
There is at most one rotation that can yield a strictly descending array (unless all elements are equal).
The required shift to achieve that rotation can be computed by finding the index of the maximum element.
Time complexity can be O(n) by scanning for the rotation point and verifying the descending property.
Edge cases: t=0, array already descending, duplicate elements, and t ≥ n (though problem states t < n).

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