Educational Cards
Learn from video content, text, and interactive tasks
Filters
Implementation: Selection Sort Step
Implement finding the minimum index in a subarray. ## Where used Ensures that in-place mutations...
Java String and indexOf
In Java, String.indexOf operates either naively or with JVM optimizations. For teaching purposes,...
Implementation: naive search
Implement the naive search and return the first index or -1. ## Where used Reference implementation...
KMP Idea: Prefix Function
KMP precomputes a longest-prefix-suffix table (pi) for the pattern. In case of a mismatch, the...
Rough Regex and Costs
Regex are powerful but can backtrack and become expensive. For fixed exact patterns, KMP or indexOf...
Naive Text Search
Naive search checks for each position in the text whether the pattern matches. On a mismatch, it...
Complexity of naive search
Let n be the text length and m be the pattern length. Naive search is O(n m) in the worst case...
Hashing: Idea and Buckets
Hashing maps keys to bucket indices. The expected access time is O(1) when the hash function...
hashCode contract in sets
HashSet/HashMap: first hashCode for the bucket, then equals within the chain. Contract: equals true...
Coarse Open Addressing
Open addressing stores entries directly in the table and searches for alternative slots in case of...
Collisions: Chaining
Chaining stores colliding entries in a list (or a tree) per bucket. Insertion depends on the...
Load Factor and Rehash
The load factor is n / capacity. If it exceeds a threshold, the table reallocates (rehash): new...