Category: Algorithms & Data structures

Generate permutations in sorted order
Let’s talk about permutations. They’re an interesting topic in combinatorics and come up in programming puzzles from time to time. There is a relatively intuitive recursive algorithm for generating all permutations for a list of elements, which goes like this: Full code: https://pl.kotl.in/nK_VtUpvn This algorithm is succinct and elegant, but the permutations are generated in…

Segment Tree
Theory Implementation With lazy propagation Practice problems

BellmanFord algorithm for shortest paths
Theory Implementation Practice problems

Kruskal’s algorithm for minimum spanning trees (MST)
Theory Implementation Practice problems

KnuthMorrisPratt algorithm for substring search
Theory Implementation Practice problems

RabinKarp algorithm for substring search
Theory Implementation Practice problems

BoyerMoore algorithm for substring search
Theory Implementation Practice problems

C++ split & replace
It’s hard to believe, but after many revisions of the C++ standard, we still don’t have builtin implementations for basic operations like split and replace. See the discussions on Stack Overflow for split and replace. Here are my basic implementations, they should work for most purposes. Split Replace Some tests These implementations seem short and…

C++: Unordered maps and sets for nonprimitive types
Since C++ 11, we can use unordered sets and unordered maps. However, these data structures only seem to work with primitive types and strings. If you need a pair or a vector as the key, you’re out of luck. Fortunately, it’s possible to use unordered containers with other types, we just have to do some…

QuickSelect
Theory Implementation in C++ Practice