Core Array, String, Hash Map, Sliding Window, and Binary Search Patterns

What's being tested

These problems test frequency-counting and anagram/signature reasoning for strings, efficient sliding-window checks over substrings, and membership lookups using hash maps. Interviewers probe algorithmic choices (O(n) vs O(n·k)), correct edge-case handling, and clean iteration/parsing for large inputs.

Patterns & templates

• Sliding window on contiguous substrings — O(n) two-pointer expand/contract; maintain counts and window invariants to avoid re-scanning.

• Frequency signature via fixed-size arrays or Counter — store counts as tuples or serialized keys for O(1) comparison on alphabet-limited strings.

• Hash set / map for membership — pre-hash dictionary words or signatures to get average O(1) membership tests during enumeration.

• Bitmask / digit mask for digits 0–9 — represent presence with a 10-bit int, enabling O(1) union/intersection checks across numbers.

• Two-pointer on arrays for monotonic constraints — move left/right and maintain aggregate (sum/count) for O(n) feasibility checks.

• Binary search over answer space — convert "max size" questions to monotone predicate, run O(n) check per mid for total O(n log n).

• Single-pass string parsing for snake_case→camelCase — build result in-place, handle separators and capitalization in O(n) time and O(1) extra space.

Common pitfalls

Pitfall: Comparing full count arrays per window naïvely makes algorithms O(n·k); instead update counts incrementally on pointer moves.

Pitfall: Forgetting to canonicalize signatures (order or normalized tuple) causes false negatives when checking anagram membership.

Pitfall: Not validating separators/edge cases (empty string, consecutive underscores) in parsing tasks leads to incorrect outputs or crashes.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.