Tag: Algorithm
42 posts
-
C++ std::reverse, reverse_copy and rotate: Reordering Ranges in Place
Reverse ranges in place or into a copy with std::reverse and reverse_copy; rotate segments with std::rotate — palindromes, string reversal, and array.
-
Implementing Data Structures in C++: Linked List, BST, and Hash Table, and the Bugs Each One Hides
Implementing a linked list, binary search tree, and open-addressing hash table in C++ from scratch, with the problems textbook versions skip: copy semantics and double deletes, recursion depth on sorted input, deletion in linear probing, and cache behavior.
-
Cache Eviction Beyond LRU: FIFO, Clock, Random and MRU in C++ with a Trace Simulator
FIFO, LRU, Clock, Random and MRU eviction implemented in C++ and replayed on the same traces: Bélády's anomaly, loops larger than the cache, scans and skew.
-
std::set_union, set_intersection and set_difference on Sorted Ranges: Duplicates, Comparators and Silent Wrong Output
How the STL set algorithms merge two sorted ranges in one pass, how they treat duplicates, and why unsorted input or a mismatched comparator fails silently.
-
The Strategy Pattern in C++: Virtual Classes vs Function Pointers vs Lambdas vs std::function
Strategy pattern in C++: polymorphic strategies, function pointers, lambdas, std::function—sorting and compression examples; performance trade-offs.
-
C++ STL Algorithms Basics: Replacing Hand-Written Loops with sort, find_if, transform and accumulate
Replace hand-written loops with std::sort, find, find_if, count_if, transform, accumulate—iterator ranges, erase-remove, lower_bound on sorted data.
-
C++17 Parallel Algorithms: Execution Policies, Toolchain Support, and Why Exceptions Call terminate
Using std::execution::par and par_unseq with sort, transform and reduce: what each policy permits, TBB and compiler support, data races, std::terminate on exceptions, and when it pays off.
-
Preparing for C++ Coding Interviews: 7 Problem Types, Must-Know STL and a Day-Of Checklist
Preparing for C++ coding tests and interviews: seven common problem types, the STL you need, time complexity budgets, fast I/O, and the mistakes behind TLE, WA and MLE.
-
Why std::remove Doesn't Shrink Your Vector: Erase-Remove, std::erase_if and the Moved-From Tail
How std::remove and remove_if really work, why size stays the same, what is left in the tail, and when to use C++20 std::erase_if, list::remove or unique.
-
std::replace, replace_if and replace_copy in C++: The v[0] Aliasing Bug, Type Deduction Errors and Substring Replacement
How std::replace, replace_if and replace_copy work, why passing v[0] as the old value stops replacing, the int/double deduction error, and substring replace.
-
C++ Search Algorithms: find, binary_search, lower_bound, and upper_bound
Choose between linear find and binary search on sorted ranges; use lower_bound, upper_bound, and equal_range for positions and equal-key runs in C++.
-
C++ Sorting: std::sort, stable_sort, partial_sort and nth_element
Compare C++ std::sort, stable_sort, partial_sort, and nth_element: custom comparators, partial sorts, median selection, and practical STL sorting patterns.
-
Two Pointers: Turning O(n²) Pair Searches into O(n), and Why It Works
The two pointers technique explained through why each move is safe: sorted pair sums, 3Sum, container with most water, in-place removal, and positive-only subarray sums, plus the input conditions each pattern silently depends on.
-
Sliding Window Technique: Fixed vs Variable Windows and When to Shrink
Sliding window algorithm optimizes fixed and variable-length contiguous ranges by sliding one position at a time in O(n).
-
Fixing TLE: Reading Constraints and Cutting Time Complexity in Coding Interviews
How to read N and Q to pick a target complexity, spot hidden O(N) steps inside loops, and replace nested loops with sorting, hashing, prefix sums or windows.
-
How to Prepare for Coding Tests: Core Patterns, Data Structures and Time Management
How to prepare for coding tests: which algorithms and data structures to learn first, spotting problem patterns, pacing a two-hour exam, and Python vs C++.
-
Hash Tables and Python dict: Hash Functions, Collisions and Why O(1) Is Only Average
Hash tables for coding interviews: how hash functions and collision resolution work, using Python dict and collections effectively, and the mistakes that turn O(1) lookups slow.
-
Binary Trees and BSTs: Traversals, Recursion Depth, Validation and Serialization
Binary trees for interviews: why the BST property covers whole subtrees, skewed trees and RecursionError, iterative traversals, level order, and serialization.
-
Graph Representation: Adjacency List vs Matrix, Building Graphs from Input, and Cycle Detection
Graph representation for interviews: adjacency list vs matrix memory, grids and edge lists, index bugs in graph building, cycle detection, topological sort.
-
Bubble, Selection and Insertion Sort: Time Complexity and Why Insertion Sort Wins on Nearly Sorted Data
Bubble, selection and insertion sort in Python with their time complexity, why insertion sort wins on nearly sorted data, and how Timsort fits in.
-
Quick Sort, Merge Sort and Heap Sort: How O(n log n) Sorting Works and When Each Wins
Quick, merge and heap sort in Python: how each reaches O(n log n), when quick sort degrades to O(n^2), which are stable or in-place, and Kth largest.
-
Sorting Problems: Multi-Key Sorts, Custom Comparators, and When Sorting First Solves the Problem
Sorting interview problems in Python: stable multi-key sorts, cmp_to_key comparators, why sort-by-end greedy works, and comparator bugs that fail submissions.
-
Binary Search: Lower/Upper Bound, Binary Search on the Answer, and Off-by-One Traps
Binary search beyond "find x in a sorted array": loop invariants that keep bounds correct, lower and upper bound, binary search on the answer, and the off-by-one and infinite-loop bugs that fail interviews.
-
BFS vs DFS: Choosing a Graph Traversal for Shortest Paths, Components and Cycles
BFS and DFS in Python for interviews: why BFS finds shortest paths, when to mark nodes visited, recursion limits, iterative DFS order bugs and grid patterns.
-
Backtracking: Pruning the Search Tree for Permutations, N-Queens and Sudoku
How backtracking prunes a search tree, why you undo instead of copy, and how pruning order and constraint checks decide whether permutations, N-Queens, and Sudoku finish in milliseconds or never.
-
Dynamic Programming: Memoization vs Tabulation and How to Spot a DP Problem
Dynamic programming from first principles: when it is valid, defining the state, memoization vs tabulation, lru_cache recursion limits, and table sizing bugs.
-
DP Patterns: Defining the State, Choosing Loop Order, and Recognizing Knapsack, LCS, and LIS
Dynamic programming patterns explained through the decisions that make them work: what dp[i] means, why 0-1 knapsack loops backward, why loop order turns combinations into permutations, and why the LIS tails array is not the LIS.
-
DP Problem Walkthroughs: Make One, Knapsack, Edit Distance, LIS and Partition With Reconstruction
Worked DP problems from state to reconstruction: recovering the path, items and edit script, and why rolling arrays break reconstruction unless you keep choices.
-
Greedy Algorithms: When the Locally Best Choice Works and How to Prove It
Why greedy works for interval scheduling and fractional knapsack but fails for coins {1,3,4} and 0/1 knapsack: exchange arguments, counterexamples, stress tests.
-
Algorithm Optimization Case Studies
Real-world case studies of solving TLE in competitive programming. Learn optimization techniques to improve from O(n²) to O(n log n), and O(n³) to O(n).
-
BFS vs DFS: How Each Works, Complexity and Which to Use for Which Problem
Compare BFS and DFS from the perspective of working principles, time complexity, and space complexity.
-
Arrays vs Linked Lists for Coding Interviews: Access Costs, Two Pointers and Common Traps
Arrays and linked lists for coding interviews: how their time complexities differ, the two-pointer and prefix-sum techniques that show up most, and practice problems by difficulty.
-
Stacks and Queues in Interviews: LIFO/FIFO Patterns, Monotonic Stacks and Deques
Stacks and queues for coding interviews: LIFO and FIFO behavior, the problem patterns they solve (bracket matching, BFS, monotonic stacks), and the mistakes that cost points.
-
C++ Copy Algorithms: std::copy, copy_if, copy_n
Copy and move ranges safely in C++ with std::copy, copy_if, copy_n, copy_backward, and remove_copy. Hand-written copy loops work, but the algorithm versions make intent explicit and avoid off-by-one and overlap bugs.
-
C++ count, count_if, all_of, any_of and none_of: Counting and Checking Conditions
Count matching values and predicates with std::count and count_if; learn all_of, any_of, none_of, empty ranges, and short-circuit behavior in C++.
-
C++ Generate Algorithms: std::fill and std::generate
Fill C++ containers with std::fill, std::generate, and std::iota, including fill_n/generate_n with back_inserter, indirect sorting with iota, proper C++11 random number generation, and common capture-by-value pitfalls.
-
C++ STL Algorithms: sort, find, transform, and the Mistakes That Give Wrong Results
C++ STL algorithm core summary. Frequently used functions like sort, search, transform, and tips to prevent mistakes and make selections.
-
C++ MinMax Algorithms: std::min, max, minmax_element & clamp
Use std::min, max, minmax, min_element, max_element, minmax_element, and C++17 std::clamp — two-value vs range APIs, iterators, and performance notes.
-
C++ <numeric>: accumulate vs reduce, transform_reduce, Scans and the Init-Type Trap
How std::accumulate, reduce, transform_reduce, partial_sum and the scans differ: evaluation order, associativity, init value type, overflow, parallel policies.
-
C++ partition, stable_partition and partition_point: Splitting Ranges by a Predicate
std::partition, stable_partition, partition_point and partition_copy in C++: splitting ranges by a predicate, keeping order, finding the boundary, 3-way splits.
-
C++ next_permutation and prev_permutation: All Permutations, Duplicates and Combinations
How std::next_permutation works, why you sort first, how duplicates are handled, correct k-permutation and nCk loops, ranges versions and the k-th permutation.
-
10 Classic Coding Test Problems Solved in C++: From Two Sum to Dijkstra
Ten classic coding test problems in C++ with STL solutions and time complexity, from Two Sum and binary search to coin change, LIS, knapsack and Dijkstra.