Oracle·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Oracle SWE interview with a pretty meaty algorithms problem. The whole session was focused on one question but they really dug into the details, not just whether you could code it up but whether you understood why it worked.

Questions Asked (1)

Given an integer array (values can be negative) and a target T, find the length of the shortest contiguous subarray with sum at least T. Return -1 if none exists. Walk through your approach, justify its correctness, analyze complexity, and implement an O(n) solution.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This one took me a while to even see the path forward.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a sliding window with a monotonic deque to maintain candidate starting indices, achieving O(n) time. For each right endpoint, update the deque to keep indices with increasing prefix sums, then find the smallest index where prefix sum difference >= T. Track the minimum length and return -1 if none found.

Pro tip: Emphasize that the deque stores indices of increasing prefix sums, allowing efficient removal of dominated candidates. This demonstrates deep understanding of monotonic queues and amortized O(n) analysis.

1. Clarify and Define

Restate the problem: find the shortest contiguous subarray with sum >= T, return -1 if none. Confirm that negative numbers are allowed and that T can be negative.

2. Discuss Naive Approaches

Mention brute-force O(n^2) and prefix-sum with binary search O(n log n) as baselines, then explain why they are suboptimal for large n.

3. Introduce Monotonic Deque

Explain that a deque of indices with increasing prefix sums allows finding the smallest valid start for each end in amortized O(1).

4. Walk Through Algorithm

Iterate right from 0 to n-1: update deque by removing indices with prefix sum >= current prefix sum; then while deque front satisfies prefix[right+1] - prefix[front] >= T, update min length and pop front.

5. Analyze Complexity and Correctness

Argue that each index is added and removed at most once, giving O(n) time and O(n) space. Prove correctness by showing the deque maintains all potentially optimal starts.

Key Points to Mention

Prefix sums enable O(1) subarray sum calculation.
Monotonic deque maintains indices with strictly increasing prefix sums, removing dominated starts.
For each right endpoint, the smallest valid start is at the deque front; popping it after use is safe because later ends yield longer subarrays.
Time complexity O(n) due to amortized O(1) deque operations; space O(n) for prefix sums and deque.
Handle edge cases: T <= 0 (shortest subarray is length 1 if any element >= T, else -1), all negatives, and no valid subarray.
Correctness proof: invariant that deque contains all indices that could be the start of a minimal subarray ending at or after current right.

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