Data Structures & Algorithms — How They Work Inside Cheat Sheet

Data Structures & Algorithms — How They Work Inside

Big-O and how to measure algorithms, arrays and dynamic arrays, linked lists, stacks and queues, hash tables (how hashing and collisions work), trees, binary search trees, heaps, tries, graphs, searching, sorting algorithms step by step, recursion, two pointers and sliding window, greedy, dynamic programming and backtracking — with C# code and where .NET and SQL Server use each one.

Complexity ladder

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!). For n = 10⁶: O(n log n) OK, O(n²) not.

Pick the structure

Index access → array/List · key lookup → Dictionary/HashSet · LIFO → Stack · FIFO → Queue · min/max fast → PriorityQueue · sorted + range → SortedDictionary / B-tree index · prefix → Trie · relationships → graph adjacency list.

Sorting facts

Merge: n log n always, stable, O(n) space. Quick: n log n avg, n² worst, in place. Heap: n log n, O(1) space. Insertion: great for tiny/nearly sorted. .NET Array.Sort = introsort (unstable); LINQ OrderBy = stable.

Patterns

Two pointers · sliding window · prefix sums · binary search (also on the answer) · BFS (shortest unweighted) · DFS/backtracking · heap for top-K · hash map for counting/lookups · DP for overlapping subproblems · greedy when locally optimal is globally optimal.

Interview method

Clarify → examples → brute force + Big-O → optimise → code → test edge cases → state time/space.