Software Engineer interview questions

Big O notation expresses how an algorithm's time or memory use scales with input size.

• It ignores constants and lower-order terms so engineers can compare approaches independently of hardware.
• An O(n) scan eventually outscales an O(n^2) nested loop, even when the slower approach wins on tiny inputs.
• It helps predict when code that handles 100 rows will become too slow or memory-hungry at a million rows.

Arrays favor fast indexed access, while linked lists favor insertion or deletion at already known nodes.

• An array stores elements contiguously, providing O(1) indexing and cache-friendly iteration.
• Inserting into an array's middle is O(n) because later elements shift, while a linked-list update at a known node is O(1).
• Reaching the k-th linked-list element takes O(n), so arrays fit random access and linked lists fit frequent edits at known positions.

A hash table achieves average O(1) lookup by hashing a key directly to a bucket in an underlying array.

• Direct bucket access avoids scanning every stored entry.
• Uniform hash distribution and a low load factor keep only a few entries in each bucket.
• O(1) is an average rather than a guarantee, because poor hashing or a high load factor can degrade lookup toward O(n).

A hash-table collision occurs when distinct keys map to the same bucket index.

• Separate chaining stores colliding entries in a small collection within the bucket and scans it during lookup.
• Open addressing probes other slots through methods such as linear, quadratic, or double hashing.
• Java HashMap uses chaining and can convert long chains into balanced trees to keep worst-case lookup near O(log n).

A stack removes items in LIFO order, while a queue removes them in FIFO order.

• A stack returns the most recently pushed item first, as in nested function calls or browser back navigation.
• A queue returns the earliest enqueued item first, as in print jobs or tasks waiting for workers.
• Both can provide O(1) insertion and removal, but they remove items from different ends of the sequence.

Binary search finds a target in sorted data by discarding half of the remaining range after each comparison.

• It compares the target with the middle element and runs in O(log n) time.
• The data must already be sorted by the search key, or the decision to discard either half is invalid.
• Sorting first costs O(n log n), so binary search is especially useful for repeated searches over the same sorted data.

Search in a balanced binary search tree takes O(log n) because each comparison discards an entire subtree.

• The number of search steps is bounded by the tree's height.
• A balanced tree keeps that height proportional to log n.
• An unbalanced tree can degenerate into a linked list with O(n) search, so AVL and red-black trees actively maintain balance.

Recursion is a technique in which a function solves a problem by calling itself with a smaller version of that problem.

• A base case must stop the recursive calls.
• A recursive case must reduce the input and make progress toward the base case.
• A missing or unreachable base case causes unbounded calls and eventually a stack overflow because every call consumes stack memory.

A tree is a constrained kind of graph, while a graph can represent more general connections.

• A graph contains nodes and edges and may be directed or undirected, cyclic or acyclic.
• A tree is connected, has no cycles, and has exactly one path between every pair of nodes.
• A tree with n nodes has n minus one edges, so every tree is a graph but most graphs are not trees.

Breadth-first search explores level by level, while depth-first search follows one branch before backtracking.

• BFS uses a queue and finds shortest paths in an unweighted graph.
• DFS uses a stack or recursion and suits cycle detection, topological sorting, and exploration of all paths.
• Both take O(V + E), but BFS memory follows the widest level while DFS memory follows the deepest path.

Quicksort partitions an array around a pivot and recursively sorts the two resulting parts.

• Elements smaller than the pivot move left and larger elements move right.
• Good pivots produce roughly even partitions and an average complexity of O(n log n).
• Consistently choosing an extreme element causes O(n^2) behavior, although randomized or median-of-three pivots make this unlikely in practice.

A stable sorting algorithm preserves the relative order of elements that compare as equal.

• Stability matters when sorts are applied by multiple keys in sequence.
• After sorting by date and then stably by name, records with equal names retain their date order.
• Merge sort is stable while naive quicksort is not, so algorithm choice can determine whether a later sort preserves an earlier ordering.

Stack memory holds short-lived call data, while heap memory holds dynamically allocated data with more flexible lifetimes.

• The stack stores call frames, local variables, and return addresses and releases them automatically in LIFO order.
• Stack allocation is fast but limited in size, whereas the heap is larger but slower and can suffer fragmentation or leaks.
• Heap data can outlive the function that created it, while stack data is normally tied to its scope and call lifetime.

I would check a palindrome with two pointers moving inward from opposite ends of the string.

• Each step compares the current pair of characters and returns false on the first mismatch.
• The approach takes O(n) time and O(1) extra space, unlike creating a reversed copy with O(n) extra memory.
• If the definition requires it, I would first normalize letter case and ignore non-alphanumeric characters.

Floyd's tortoise-and-hare algorithm detects a linked-list cycle without extra storage.

• One pointer advances by one node per step while another advances by two.
• If a cycle exists, the fast pointer eventually laps and meets the slow pointer; reaching null means there is no cycle.
• The algorithm uses O(n) time and O(1) space, unlike a visited-node hash set that requires O(n) memory.

A stack is the natural structure for undo because the latest action must be reversed first.

• Every action pushes its previous state or an inverse command onto the undo stack.
• Undo pops and applies the top entry, matching LIFO order.
• A second stack enables redo by storing undone actions until they need to be replayed.

Appending to a dynamic array is O(1) amortized because expensive resizes happen increasingly rarely.

• A full array typically doubles its capacity and copies all n existing elements in O(n).
• Exponential growth leaves many cheap O(1) appends between consecutive resizes.
• Spreading the total copying cost across all appends yields a constant average cost per operation.

A set is an unordered collection of unique elements designed for fast membership checks.

• A hash-table-backed set usually tests membership in O(1), while a list requires an O(n) scan.
• A set is preferable when duplicates must be removed or presence must be checked repeatedly.
• Typical uses include deduplicating user IDs and recording visited values during graph traversal.

Repeated string concatenation is often slow because immutable strings must be copied into a new value after every append.

• In Java and Python, building a growing string this way inside a loop can cost O(n^2) overall.
• A mutable buffer such as Java StringBuilder, or a Python list combined with str.join, accumulates pieces cheaply.
• Creating the final string only once at the end reduces the total work to O(n).

A heap is a priority-queue structure that keeps its smallest or largest element at the root.

• It provides O(1) access to the extreme element and O(log n) insertion and removal.
• It efficiently returns the next highest-priority item without fully sorting all stored items.
• Common uses include task scheduling, merging sorted streams, and selecting the closest unvisited node in Dijkstra's algorithm.