Data Structures & Algorithms — How They Work Inside

In short: It describes how an algorithm's time or memory grows with input size n, ignoring constants and smaller terms.

• O(1) dictionary lookup, O(log n) binary search, O(n) one loop, O(n log n) good sorts, O(n²) nested loops over the same data, O(2ⁿ) all subsets.
• It lets you predict whether a solution scales — e.g. O(n²) on a million items is ~10¹² operations, too slow.

In short: Arrays (and List<T>) store elements contiguously: O(1) index access, cache-friendly iteration, but O(n) inserts/removes in the middle.

• Linked lists store nodes with pointers: O(1) insert/remove at a known node, but O(n) access by position and poor cache locality.
• In practice List<T> wins most of the time; linked lists suit frequent middle insertions with a node reference (LRU caches pair a linked list with a dictionary).

In short: It computes the key's hash code, maps it to a bucket (hash % size), and stores the entry there; lookups recompute the hash, go to the bucket and compare with Equals.

• Collisions are handled by chaining or probing; when the load factor grows, it resizes and rehashes.
• Average O(1) insert/lookup/delete, worst O(n) if many keys collide.
• Keys must have consistent Equals/GetHashCode and shouldn't change while stored.

In short: Stack is LIFO: function call stack, undo/redo, browser back button, expression evaluation, DFS.

• Queue is FIFO: print jobs, request/message queues, thread-pool work items, BFS.
• Both have O(1) push/pop or enqueue/dequeue.

In short: The data must be sorted.

• Compare the target with the middle element; if smaller, search the left half, otherwise the right half; repeat until found or the range is empty — O(log n).
• Compute the middle as lo + (hi - lo) / 2 to avoid overflow.
• Database index seeks work on the same principle over B-tree pages.

In short: Both average O(n log n).

• Merge sort is always O(n log n), stable, but needs O(n) extra memory — good for linked lists and external sorting of huge data.
• Quicksort sorts in place (O(log n) stack), is usually faster in practice thanks to cache locality, but is O(n²) in the worst case with bad pivots and is not stable. .NET's Array.Sort uses introsort to avoid the worst case.

In short: A binary tree where every node's left subtree has smaller keys and right subtree larger keys, so search/insert/delete follow one path: O(height).

• Balanced height is log n; inserting sorted data into a plain BST makes it a linked list with O(n) operations.
• Self-balancing trees (AVL, red-black) and B-trees keep the height logarithmic — SQL Server indexes are B+ trees.

In short: BFS explores level by level using a queue — finds the shortest path in unweighted graphs, uses memory proportional to the widest level.

• DFS goes as deep as possible using recursion or a stack — good for connectivity, cycle detection, topological sort and backtracking, uses memory proportional to depth.
• Both are O(V + E).

In short: DP solves problems with overlapping subproblems and optimal substructure by storing subproblem results (memoisation top-down, or a table bottom-up) so each is computed once.

• Plain recursion may recompute the same subproblem exponentially many times (naive Fibonacci O(2ⁿ) vs DP O(n)).
• Typical DP problems: coin change, knapsack, longest common subsequence, edit distance, climbing stairs.

In short: Nested loops are O(n × m) ≈ 4 × 10¹⁰ comparisons.

• Put one list into a HashSet<int> (O(m)) and check each id of the other list with Contains (O(1) average) — O(n + m), milliseconds.
• Or sort both and merge with two pointers (O(n log n)), or let SQL do it with an indexed JOIN/EXISTS.

In short: A leading wildcard can't use a B-tree index, so every keystroke scans the table.

• Options: prefix search LIKE 'term%' on an indexed column (index seek), a trie or sorted in-memory list of names for prefix lookups, full-text search (SQL Server full-text index, Azure AI Search, Elasticsearch) for word matches, debounce keystrokes and limit to top 10, cache popular prefixes.