Question 1

What is Big O notation and why does it matter?

Accepted Answer

Big O describes how an algorithm's runtime or memory usage grows as input size increases, ignoring constant factors and hardware specifics. It matters because it lets you compare algorithms' scalability independent of any particular machine.

Question 2

What's the time complexity of binary search, and what's required for it to work?

Accepted Answer

O(log n). The input must be sorted — binary search repeatedly halves the search space by comparing the target to the middle element.

Question 3

When would you use a hash map instead of an array?

Accepted Answer

When you need fast (average O(1)) lookups, insertions, or deletions by a key that isn't a small contiguous integer index — e.g. counting word frequency, or checking set membership, where array index-based access doesn't apply.

Question 4

What is the difference between a stack and a queue?

Accepted Answer

A stack is LIFO (last-in, first-out) — think of a stack of plates, you take from the top. A queue is FIFO (first-in, first-out) — like a line, first person in is first served.

Question 5

Explain the two-pointer technique with an example.

Accepted Answer

Two pointers traverse a data structure (often a sorted array) from different positions simultaneously, moving based on a condition, to avoid nested loops. Example: to check if a sorted array has two numbers summing to a target, start one pointer at the beginning and one at the end, moving them inward based on whether the current sum is too high or too low.

Question 6

What's the time complexity of inserting into a balanced binary search tree?

Accepted Answer

O(log n) — because the tree's height is logarithmic in the number of nodes when balanced, so each insertion only needs to traverse that height.

Question 7

What is recursion, and what's a common pitfall?

Accepted Answer

Recursion is a function calling itself to solve a smaller instance of the same problem, with a base case to stop. The common pitfall is missing or incorrect base cases, causing infinite recursion and a stack overflow, or redundant recomputation (which memoization/dynamic programming fixes).

Question 8

What's the difference between depth-first search (DFS) and breadth-first search (BFS)?

Accepted Answer

DFS explores as far as possible down one branch before backtracking (typically using a stack or recursion). BFS explores all neighbors at the current depth before going deeper (using a queue). BFS is used for shortest-path-in-unweighted-graph problems; DFS is often simpler for exhaustive search/backtracking.

Question 9

What is the space-time tradeoff, and when would you accept using more memory?

Accepted Answer

It's the idea that you can often reduce runtime by using more memory (e.g. caching/memoization) or vice versa. You'd accept more memory usage when the algorithm runs frequently and speed matters more than memory constraints, e.g. caching expensive computation results.

Question 10

How would you detect a cycle in a linked list?

Accepted Answer

Floyd's cycle detection ("tortoise and hare"): use two pointers, one moving one step at a time and one moving two steps at a time. If there's a cycle, the fast pointer will eventually lap the slow pointer and they'll meet; if there's no cycle, the fast pointer reaches the end (null).

Data Structures & Algorithms Interview Questions

Data Structures & Algorithms Interview Questions