Sorting and Searching Algorithms Questions

Approach (two pointers)

• Use left/right pointers on the sorted array. Move pointers inward; when sum equals target, record the value pair and skip duplicates to ensure unique pairs. This is O(n) time and O(1) extra space (output excluded).

Code

from typing import List, Tuple

def unique_pairs(nums: List[int], target: int) -> List[Tuple[int,int]]:
    res = []
    i, j = 0, len(nums) - 1
    while i < j:
        s = nums[i] + nums[j]
        if s == target:
            res.append((nums[i], nums[j]))
            # skip duplicates for left
            left_val = nums[i]
            while i < j and nums[i] == left_val:
                i += 1
            # skip duplicates for right
            right_val = nums[j]
            while i < j and nums[j] == right_val:
                j -= 1
        elif s < target:
            i += 1
        else:
            j -= 1
    return res

Explanation & Complexity

• Why: Sorted order lets us adjust pointers deterministically.
• Time: O(n) — each element visited at most once.
• Space: O(1) extra (output excluded).
• Edge cases: empty array, single element, all duplicates, negative numbers. This implementation handles them by pointer checks.

Approach overview

For backend services I almost always prefer the language’s standard-library sort (Python sorted, Java Arrays.sort, Node Array.prototype.sort) unless I have a compelling special-case need. Below I compare trade-offs relevant to production server-side code.

Performance

• Stdlib: Highly optimized, often using hybrid algorithms (Timsort in Python, Dual-Pivot Quicksort / Merge variants in Java) with excellent average/worst behavior and native C/VM speed.
• Custom: Rarely matches tuned implementations; useful only for very specific workloads (e.g., integer radix sort for huge numeric arrays).

Stability

• Stdlib: Many languages provide stable sorts (Python’s Timsort, Java’s Arrays.sort for objects uses stable merge in newer JDKs). Stability matters for multi-key sorts without extra allocations.
• Custom: You must ensure stability if required—easy to get wrong.

Maintainability

• Stdlib: Simple, readable, and well-tested. Future maintainers expect library usage.
• Custom: Increases code surface, test burden, and risk of bugs—adds cognitive load during code reviews.

Comparator correctness

• Stdlib: Rely on documented comparator contracts (transitive, consistent). Libraries validate some violations, but incorrect comparators can cause exceptions or undefined ordering.
• Custom: Must enforce comparator properties and handle nulls/NaNs explicitly.

Edge-case behavior

• Stdlib: Handles empty arrays, singletons, large sizes, and many pathological patterns robustly. Language docs specify behavior for NaN, -0, undefined.
• Custom: You must handle these explicitly (overflow, special floats, locale-aware string collation).

When to implement custom

• High-performance hot paths with measurable bottlenecks
• Specialized domain sorts (radix, external/streaming sort for huge datasets)
• Memory constraints requiring in-place or external algorithms

Best practices

• Prefer stdlib; benchmark before custom work (real data).
• If custom, write thorough tests (stability, comparator invariants, extreme inputs) and document why it’s necessary.

Approach (brief)
Use divide-and-conquer: modified merge sort counts inversions while merging. When a left element > right element during merge, it forms inversions with remaining elements in left subarray.

Code (Java)

public class InversionCounter {
  public static long countInversions(int[] arr) {
    if (arr == null || arr.length < 2) return 0L;
    int[] aux = arr.clone();
    return sortCount(arr, aux, 0, arr.length - 1);
  }

  private static long sortCount(int[] a, int[] aux, int lo, int hi) {
    if (lo >= hi) return 0L;
    int mid = lo + (hi - lo) / 2;
    long count = 0;
    count += sortCount(a, aux, lo, mid);
    count += sortCount(a, aux, mid + 1, hi);
    // merge step
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid || j <= hi) {
      if (i > mid) aux[k++] = a[j++];
      else if (j > hi) aux[k++] = a[i++];
      else if (a[i] <= a[j]) aux[k++] = a[i++];
      else { // a[i] > a[j] -> inversions
        aux[k++] = a[j++];
        count += (mid - i + 1);
      }
    }
    System.arraycopy(aux, lo, a, lo, hi - lo + 1);
    return count;
  }
}

Why O(n log n)
Each level of recursion does a linear-time merge across all subarrays (O(n)). There are O(log n) levels, so total time is O(n log n). Space is O(n) for auxiliary array.

Edge cases & notes

• Handles duplicates using <= to avoid counting equal pairs.
• Use long to avoid overflow for large arrays (n up to ~2e9 pairs).

Summary / Endpoint
GET /api/v1/activities
Query params: limit= (int), page= (int, optional for offset), cursor= (string, optional for keyset), sort=timestamp_desc,id_asc (fixed by requirement)

Behavior

• Support offset pagination when page provided (page & limit).
• Prefer keyset when cursor provided: stable, efficient for large datasets, resilient to new inserts.

Cursor design

• Cursor encodes the last record's sort keys: base64("ts|id"), e.g.:

cursor = base64( "2026-03-01T12:34:56Z|12345" )

• For timestamp desc, id asc ordering, keyset WHERE clause uses:

WHERE
  (timestamp < :last_ts)
  OR (timestamp = :last_ts AND id > :last_id)
ORDER BY timestamp DESC, id ASC
LIMIT :limit

DB schema & indexes

• Table: activities(id BIGINT PK, user_id BIGINT, timestamp TIMESTAMPTZ, type TEXT, payload JSONB)
• Index: CREATE INDEX idx_activities_ts_desc_id_asc ON activities (timestamp DESC, id ASC);
  (Postgres ignores DESC in index scan direction but keep for clarity; alternatively a composite B-tree on (timestamp, id).)

Why keyset is preferred

• Time/space: O(limit) vs offset's O(offset+limit) cost; avoids deep skips and avoids degrading queries on high offsets.
• Stability: Using the composite cursor (timestamp,id) and tie-breaker id ensures deterministic ordering even when timestamps duplicate.
• Resilience to inserts: Keyset moves relative to last seen keys; new rows with newer timestamps won't be returned in subsequent pages; avoids missing or duplicating rows that happen when using offset amid concurrent inserts.

Fallback & safety

• Validate/expire cursors, provide next_cursor in response. For small datasets or random-access needs, support offset mode but document performance trade-offs.

Approach (brief)
Binary-search on the smaller array to partition both arrays so left partitions contain k = (m+n+1)//2 elements. Maintain invariant: max(leftA) <= min(rightB) and max(leftB) <= min(rightA). When invariant holds, median is either max(lefts) (odd) or average of max(lefts) and min(rights) (even).

Code

from typing import List
import math

def find_median_sorted_arrays(a: List[int], b: List[int]) -> float:
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    total = m + n
    half = (total + 1) // 2

    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2           # elements from a in left partition
        j = half - i                 # elements from b in left partition

        Aleft = a[i-1] if i > 0 else -math.inf
        Aright = a[i] if i < m else math.inf
        Bleft = b[j-1] if j > 0 else -math.inf
        Bright = b[j] if j < n else math.inf

        if Aleft <= Bright and Bleft <= Aright:
            if total % 2:            # odd
                return float(max(Aleft, Bleft))
            return (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0
        elif Aleft > Bright:
            hi = i - 1
        else:
            lo = i + 1
    raise ValueError("Input arrays not sorted or invalid")

Correctness reasoning
Partitioning ensures left side contains k smallest elements. Binary search on i adjusts relative sizes until cross-boundary order holds (Aleft <= Bright and Bleft <= Aright). When true, extremes of partitions determine median. Using infinities handles empty partitions. Loop runs O(log min(m,n)); only O(1) extra space.

Edge cases

• One array empty (works via infinities).
• All elements on one side equal.
• Even/odd total length handled by half and parity check.