DSAInterview questions and answers

Big-O describes the worst-case growth rate of an algorithm's time or space as input size n grows. It ignores constants and lower-order terms — O(2n) and O(n) are the same class. The point is comparing how algorithms scale, not exact runtimes.

O(1) constant < O(log n) logarithmic < O(n) linear < O(n log n) — typical good sorts < O(n²) — nested loops < O(2ⁿ) — naive recursion on subsets < O(n!) — permutations. Each step is a meaningful jump; n=1M is fine for O(n log n) but devastating for O(n²).

Array: contiguous memory, O(1) random access by index, cache-friendly, but O(n) to insert in the middle (must shift). Linked list: scattered memory, O(n) random access, O(1) insert/remove if you already have the node, pointer overhead. For nearly all real workloads, arrays win.

When you need O(1) average lookup, insert, and delete by key, and you don't care about order. Hash maps are the workhorse of most algorithms — counting frequencies, deduplicating, mapping between values, caching. Worst-case is O(n) on bad collisions but rare in practice.

A LIFO (Last-In-First-Out) data structure. Operations: push (add to top), pop (remove from top), peek (look at top) — all O(1). Used for function call frames, undo/redo, balanced parentheses, expression evaluation, and DFS implementations.