← Capital One Interview InsightsSoftware Engineer

Capital One·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Capital One SWE interview with a single algorithmic problem that looked deceptively clean on the surface but had enough edge cases to trip you up if you weren't careful about the cyclic indexing.

Questions Asked (1)

Q1

Given an array and an integer t (where 0 <= t < array length), a cyclic left-shift moves t elements from the end to the front. Can you determine whether any of the t possible shift operations produces a descending-order array, before completing a full rotation?

Algorithms & Data Structures
Author's notes

I went straight to brute force first, just simulating each shift and checking order, which works but felt embarrassing to say out loud.

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. To check if any shift yields a descending array, you can either simulate all t shifts (O(n^2) worst-case) or use a more efficient approach by finding the rotation point where the array becomes descending. The key is to identify if the array can be rotated to be strictly descending, which is equivalent to checking if the array is a rotation of a descending sorted array.

Pro tip: Mention that you can solve this in O(n) time by finding the minimum element and checking if the array is descending from that point, but be careful with duplicates and edge cases like t=0 or t=n-1. Also, note that the problem asks for any of the t possible shifts, not all, so early termination is possible.

1. Clarify the problem and constraints

Restate the problem to ensure understanding: given an array and integer t (0 <= t < n), a cyclic left-shift by t moves the last t elements to the front. Determine if any shift in 1..t produces a strictly descending array. Ask about duplicates, array size, and whether t is inclusive.

2. Brute-force simulation (baseline)

For each shift from 1 to t, perform the shift and check if the resulting array is descending. This takes O(t * n) time. Mention this as a starting point but note it's inefficient for large inputs.

3. Optimized approach using rotation point

A descending array rotated left by t is equivalent to the original array being a rotation of a descending sorted array. Find the index of the maximum element (or minimum) and check if the array is descending from that point. Alternatively, check if the array has exactly one 'ascent' (where a[i] < a[i+1]) and that ascent is at the rotation point.

4. Handle edge cases and duplicates

Consider cases where the array is already descending (t=0), all elements equal, or duplicates that might break strict descending order. Clarify if 'descending' means strictly descending or non-increasing.

5. Analyze time and space complexity

The optimized approach runs in O(n) time and O(1) space. Discuss trade-offs and potential pitfalls, such as off-by-one errors in rotation indices.

Key Points to Mention

  • Definition of cyclic left-shift and how it relates to rotation
  • Brute-force vs. optimized solution and their time complexities
  • Condition for an array to be a rotation of a descending array (exactly one ascent)
  • Handling duplicates and strict vs. non-strict descending order
  • Edge cases: t=0, t=n-1, empty array, single element
  • Early termination: if a descending rotation is found before t, return true

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