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
-
Bellman-Ford algorithm for shortest paths
Theory Implementation Practice problems
-
Kruskal’s algorithm for minimum spanning trees (MST)
Theory Implementation Practice problems
-
Knuth-Morris-Pratt algorithm for substring search
Theory Implementation Practice problems
-
Rabin-Karp algorithm for substring search
Theory Implementation Practice problems
-
Boyer-Moore 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 built-in 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 non-primitive 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