asmhatreandClaude Sonnet 5.5
911aef5515
Co-Authored-By: Claude Sonnet 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_017ic4b6EqSkUWKNBc8i3Q3U
76 lines
3.7 KiB
Markdown
76 lines
3.7 KiB
Markdown
# sliding-window
|
|
|
|
Companion code for the ankurm.com article **Sliding Window and Two Pointers in Java: 12 Interview Problems Solved**.
|
|
|
|
Twelve classic interview problems solved with the two patterns, each cross-checked against an
|
|
obviously-correct brute-force version on seeded random inputs. Every figure and console line in
|
|
the article is quoted from a file in `output/`, which the JUnit tests write while asserting the
|
|
same numbers. There is no `docs/` folder: the explanations live in the article itself.
|
|
|
|
## Versions
|
|
|
|
| Component | Version | Verified against |
|
|
|---|---|---|
|
|
| JDK | Temurin 25.0.5+8 (LTS) | `java -version` |
|
|
| JUnit | 6.1.3 | `junit-bom` `maven-metadata.xml` on Maven Central (latest GA) |
|
|
| Maven | 3.9.x | `mvn -version` |
|
|
|
|
## Quickstart
|
|
|
|
```bash
|
|
cd sliding-window
|
|
export JAVA_HOME=/path/to/jdk-25 PATH="$JAVA_HOME/bin:$PATH"
|
|
./scripts/run-all.sh # runs 11 tests and regenerates output/*.txt
|
|
```
|
|
|
|
The first Maven run must be online so the plugins land in the local cache.
|
|
|
|
## The twelve problems
|
|
|
|
| # | Problem | Pattern | Method |
|
|
|---|---|---|---|
|
|
| 1 | Maximum sum of k consecutive elements | fixed window | `FixedWindow.maxSumSubarray` |
|
|
| 2 | Permutation in string | fixed window + counts | `FixedWindow.permutationInString` |
|
|
| 3 | Sliding window maximum | fixed window + monotonic deque | `FixedWindow.slidingWindowMaximum` |
|
|
| 4 | Longest substring without repeating characters | variable window | `VariableWindow.longestUniqueSubstring` |
|
|
| 5 | Longest substring with at most K distinct characters | variable window | `VariableWindow.longestKDistinct` |
|
|
| 6 | Longest repeating character replacement | variable window | `VariableWindow.characterReplacement` |
|
|
| 7 | Max consecutive ones III | variable window | `VariableWindow.longestOnes` |
|
|
| 8 | Minimum size subarray sum | shrinking window | `VariableWindow.minSubArrayLen` |
|
|
| 9 | Minimum window substring | shrinking window | `VariableWindow.minWindow` |
|
|
| 10 | Two Sum II (sorted input) | opposite-end pointers | `TwoPointers.twoSumSorted` |
|
|
| 11 | 3Sum | sort + pointers | `TwoPointers.threeSum` |
|
|
| 12 | Container with most water | opposite-end pointers | `TwoPointers.maxArea` |
|
|
|
|
## Source layout
|
|
|
|
```
|
|
sliding-window/
|
|
├── pom.xml
|
|
├── scripts/run-all.sh
|
|
├── src/main/java/com/ankurm/interviewlab/slidingwindow/
|
|
│ ├── FixedWindow.java problems 1-3
|
|
│ ├── VariableWindow.java problems 4-9
|
|
│ ├── TwoPointers.java problems 10-12
|
|
│ ├── BruteForce.java slow, obviously-correct references
|
|
│ ├── DryRuns.java instrumented copies that record every step
|
|
│ ├── Complexity.java operation counters (counted, not timed)
|
|
│ └── Pitfalls.java four plausible-looking wrong versions
|
|
├── src/test/java/.../ SolutionsTest, RandomAgreementTest, DryRunTest, ComplexityTest, PitfallsTest
|
|
└── output/*.txt captured real output
|
|
```
|
|
|
|
## Captured output (`output/`)
|
|
|
|
| File | What it shows |
|
|
|---|---|
|
|
| `01-fixed-window-trace.txt` | max-sum window sliding over `[2,1,5,1,3,2]` |
|
|
| `02-longest-unique-trace.txt` | left pointer jumps on `abcabcbb` and the `abba` case |
|
|
| `03-min-window-trace.txt` | grow until valid, shrink until invalid on `ADOBECODEBANC` |
|
|
| `04-sliding-max-deque-trace.txt` | the monotonic deque contents at every step |
|
|
| `05-two-pointers-trace.txt` | Two Sum II and Container With Most Water |
|
|
| `06-all-twelve-results.txt` | one example per problem beside the brute-force answer |
|
|
| `07-random-agreement.txt` | 24,000 seeded comparisons, 0 disagreements |
|
|
| `08-operation-counts.txt` | brute force vs window operation counts at n = 1k..8k |
|
|
| `09-pitfalls.txt` | four classic mistakes, each reproduced |
|