dsa-interview-patterns

name

dsa-interview-patterns

description

Classic coding interview patterns including two pointers, sliding window, binary search variants, fast/slow pointers, prefix sums, interval merging, and monotonic stack. Use when: solving array or string problems under interview constraints, recognising which pattern fits a given input shape, implementing cursor-based pagination, analysing date-range or sorted time-series queries, reviewing LINQ chains for hidden complexity, or teaching pattern-first problem solving.

DSA Interview Patterns

When to Use

• Approaching a new problem and needing to identify which pattern applies
• Implementing or reviewing two-pointer, sliding window, or binary search logic
• Teaching pattern-first problem solving (recognise the shape, apply the template)
• Reviewing pagination cursor logic or date-range query strategies
• Analysing activity log aggregation for hidden O(n²) in prefix sum candidates
• Preparing for technical interviews with common pattern recognition

Two Pointers

Two pointers move through a collection — usually from both ends toward the middle, or both from the start at different speeds.

Same-Direction (Fast / Slow)

// Remove duplicates from sorted array in-place (O(n) time, O(1) space)
int slow = 0;
for (int fast = 1; fast < nums.Length; fast++)
{
    if (nums[fast] != nums[slow])
        nums[++slow] = nums[fast];
}
return slow + 1;

Opposite-Direction (Converging)

// Two-sum on sorted array (O(n) time)
int left = 0, right = nums.Length - 1;
while (left < right)
{
    int sum = nums[left] + nums[right];
    if (sum == target)  return (left, right);
    if (sum < target)   left++;
    else                right--;
}

When to Use Two Pointers

• Input is sorted or can be sorted
• Looking for a pair / triplet satisfying a condition
• Removing elements in-place
• Comparing characters from both ends of a string (palindrome check)

Sliding Window

A window is a contiguous sub-sequence. Sliding window avoids the O(n²) of checking all pairs/windows by maintaining and updating a running state as the window slides.

Fixed-Size Window

// Maximum sum of any subarray of length k — O(n)
int windowSum = 0;
for (int i = 0; i < k; i++)
{
    windowSum += nums[i];
}
int maxSum = windowSum;
for (int i = k; i < nums.Length; i++)
{
    windowSum += nums[i] - nums[i - k];
    maxSum = Math.Max(maxSum, windowSum);
}

Variable-Size Window

// Longest substring with at most k distinct characters — O(n)
int left = 0, maxLen = 0;
var freq = new Dictionary<char, int>();
for (int right = 0; right < s.Length; right++)
{
    freq[s[right]] = freq.GetValueOrDefault(s[right]) + 1;
    while (freq.Count > k)
    {
        freq[s[left]]--;
        if (freq[s[left]] == 0) freq.Remove(s[left]);
        left++;
    }
    maxLen = Math.Max(maxLen, right - left + 1);
}

Biotrackr Anchor — Pagination as Sliding Window

PaginationResponse<T> in Biotrackr APIs is a fixed-size sliding window over a sorted dataset. Cosmos DB continuation tokens are variable-size window cursors — the boundary is a bookmark, not a numeric offset:

Fixed: pageNumber=3, pageSize=20 → offset = 40, length = 20
Cursor: continuationToken="{etag}" → start after last seen item

Teaching angle: Cursor-based pagination avoids "page drift" when items are inserted mid-pagination. It is the variable-size window pattern: the window start is pinned to the last seen item, not a fixed numeric offset.

Binary Search

Binary search works on any monotone function — not just sorted arrays. The key is: "does the condition hold for all values on one side?"

Template

// Generalised binary search — finds leftmost position where condition is true
int left = 0, right = boundary;
while (left < right)
{
    int mid = left + (right - left) / 2;
    if (Condition(mid)) right = mid;       // condition true → search left half
    else                left = mid + 1;    // condition false → search right half
}
return left; // leftmost true position

Biotrackr Anchor — Date-Range Queries on Sorted Time-Series

Activity, sleep, and vitals data in Biotrackr are stored sorted by date. A range query /range/{startDate}/{endDate} on sorted records is binary search applied twice:

find first index where date >= startDate   →  binary search left boundary
find last  index where date <= endDate     →  binary search right boundary

Teaching angle: Cosmos DB range queries on indexed date fields use a B-tree for O(log n) boundary location — the same concept as binary search, implemented in a tree.

Fast/Slow Pointers

Fast pointer moves at 2× the speed of slow. Useful for cycle detection and finding the middle of a linked list.

Floyd's cycle detection:
slow moves 1 step at a time
fast moves 2 steps at a time

If they meet: cycle exists
If fast reaches null: no cycle

When to Use Fast/Slow

• Detect cycle in a linked list (Floyd's algorithm)
• Find the middle node of a linked list
• Detect duplicate in an array treated as implicit linked list (Floyd's on values)

Prefix Sum

A prefix sum array P where P[i] = nums[0] + ... + nums[i] allows O(1) range sum queries:

// Build prefix sum — O(n)
int[] prefix = new int[nums.Length + 1];
for (int i = 0; i < nums.Length; i++)
    prefix[i + 1] = prefix[i] + nums[i];

// Query sum of [left, right] — O(1)
int rangeSum = prefix[right + 1] - prefix[left];

Biotrackr Anchor — Activity Log Aggregation

Biotrackr.Activity.Api returns activity records by date. Aggregating total steps over a date range without prefix sums requires summing each record in the range: O(k) where k is the range size. With a pre-built prefix sum over sorted daily totals, any range aggregate is O(1) after O(n) preprocessing.

Teaching angle: Build the prefix sum once; answer all range queries in O(1). The trade-off is O(n) space. When you have many range queries on static data, prefix sums are the right tool.

Pattern Recognition Guide

Use the input shape to identify the right pattern:

Input Shape	Common Patterns
Sorted array, find target	Binary search
Sorted array, find pair satisfying condition	Two pointers (converging)
Array, longest/smallest subarray satisfying condition	Sliding window
Linked list, detect cycle or find middle	Fast/slow pointers
Array, range sum queries	Prefix sum
Array of intervals, merge or insert	Sort by start, linear sweep
Matrix, find path or connected region	BFS or DFS
String, all permutations/combinations	Backtracking
Scheduling with priorities	Heap / priority queue
"Nearest greater element"	Monotonic stack

Monotonic Stack

A monotonic stack maintains elements in a consistently increasing or decreasing order. Useful for "next greater/smaller element" problems in O(n).

// Next greater element for each item — O(n)
var result = new int[nums.Length];
var stack = new Stack<int>(); // stores indices
for (int i = 0; i < nums.Length; i++)
{
    while (stack.Count > 0 && nums[stack.Peek()] < nums[i])
        result[stack.Pop()] = nums[i];
    stack.Push(i);
}
// Remaining indices have no greater element → result stays 0

When to reach for monotonic stack: "For each element, find the first element to its left/right that is larger/smaller." This pattern appears in histogram problems, stock span, and trapping rainwater.