Arrays, Sliding Windows, DP And Stack Patterns
Asked of: Software Engineer
Last updated

What's being tested
These problems test array invariants, monotonic stacks, sliding windows, and dynamic programming under tight time constraints. Interviewers are probing whether you can turn a brute-force scan over subarrays or future elements into an O(n) or near-O(n) solution with correct edge-case handling.
Patterns & templates
-
Prefix invariant for permutations — track
max_so_far; prefix0..iforms1..kiffmax_so_far == i + 1, assuming valid permutation input. -
Monotonic stack for next smaller/equal element — maintain increasing stack of indices; pop while
prices[top] >= prices[i];O(n)time,O(n)space. -
Sliding window with frequencies — expand right, update pair count by
freq[x]; contract left while condition still holds; count many subarrays at once. -
Identical-pair counting — adding value
xcreatesfreq[x]new pairs; removing it deletesfreq[x] - 1; avoid recomputing combinations. -
At least k subarrays — when window
[l..r]satisfies condition, all extensions to the right also satisfy it, contributingn - r. -
Dynamic programming for constrained jumps — define
dp[i]as paths to positioni; transition from allowed jump sizes; use modulo arithmetic consistently. -
Prime preprocessing — generate primes ending in
3using Sieve of Eratosthenes up to max jump/position; avoid primality checks inside nested loops.
Common pitfalls
Pitfall: Using
sum(freq[v] choose 2)after every pointer move turns an intendedO(n)sliding window intoO(n * distinct).
Pitfall: For final prices, using strictly smaller instead of smaller-or-equal changes correctness on duplicate prices.
Pitfall: In DP counting, forgetting
mod = 1_000_000_007during each addition can overflow in languages likeJavaorC++.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Implement stream queries and bounded-difference subarraysUber · Software Engineer · Onsite · medium
- Find a Bounded Subarray and Largest SquareUber · Software Engineer · Onsite · medium
- Solve 12 coding interview problemsUber · Software Engineer · Take-home Project · medium
- Solve these algorithmic problemsUber · Software Engineer · Take-home Project · medium
- Check if each prefix forms 1..k permutationUber · Software Engineer · Take-home Project · hard
- Determine balanced k values in a permutationUber · Software Engineer · Take-home Project · medium
- Compute final prices with next smaller discountUber · Software Engineer · Take-home Project · medium
- Solve stock profit and vertical tree traversalUber · Software Engineer · Onsite · medium
- Count paths with prime-ending jumpsUber · Software Engineer · Take-home Project · medium
- Maximize stock profit with one or two tradesUber · Software Engineer · Onsite · hard
- Sort by squares and find k-th smallestUber · Software Engineer · Technical Screen · Medium
- Find leftmost point of maximum brightnessUber · Software Engineer · Take-home Project · Medium
Related concepts
- Arrays, Strings, Hash Maps, And Sliding WindowsCoding & Algorithms
- Array And String AlgorithmsCoding & Algorithms
- Arrays, Intervals, Sliding Windows, And Prefix SumsCoding & Algorithms
- String And Sliding Window AlgorithmsCoding & Algorithms
- Arrays, Strings, Hash Maps, And Frequency CountingCoding & Algorithms
- Sliding Window Frequency MapsCoding & Algorithms