Algorithms & DS interview questions
56 Algorithms & DS interview questions with answers, from junior to mid level.
Foundations
Core
- Time complexity of binary search on a sorted array?
- Average and worst-case lookup in a hash table?
- Validate a string of brackets like
"([]{})". Data structure? - What does this function return and what are its time/space costs?
- In a Python list,
append(x)andinsert(0, x)cost… - Repeated
x in datachecks inside a loop are slow.datais a list of 1M items. Fix? - How do you approach a coding problem you have never seen in an interview?
- What does Big-O notation describe?
- What is the time complexity?
- What is the time complexity?
- Accessing the 1000th element: array (Python list) vs linked list?
- A stack is…
- A queue is…
- Why must every recursive function have a base case?
- Searching an unsorted list by checking each item one by one is…
- In a tree data structure, what is a leaf?
- What is a graph in computer science?
- What must be true before you can use binary search on a list?
- What is the time complexity of
nums[5]on a Python list of 1 million items?
Intermediate
- What is the lower bound for comparison-based sorting?
- Worst case of quicksort, and when does it happen?
- Which is true about merge sort?
- Two Sum: find indices of two numbers adding to
target. Optimal approach? - Detect a cycle in a linked list with O(1) extra space?
- Shortest path (fewest edges) in an unweighted graph?
- Best way to get the k largest elements from a stream of n numbers?
- Longest substring without repeating characters. Optimal technique and complexity?
- In a sorted array, find whether two numbers sum to target using O(1) space.
- Which two properties indicate a problem fits dynamic programming?
- Time complexity of memoized Fibonacci
fib(n)? - A deep recursive DFS in Python on a 100,000-node path graph will likely…
- Implementing a queue with two stacks gives what cost per operation?
- Autocomplete over a dictionary of words by prefix. Best structure?
- Which traversal of a binary search tree yields keys in sorted order?
- Worst-case search time in an unbalanced BST built from sorted input?
- For a sparse graph (E much smaller than V²), which representation is preferred?
- Answer many
sum(nums[i:j])range queries on a static array quickly? - How does a hash map work internally?
- Reverse a singly linked list iteratively. Explain the pointers.
Advanced
- Dijkstra's algorithm requires…
- You need an order to install packages given 'A depends on B' relations. Algorithm?
- Count connected components while edges arrive dynamically. Best structure?
- Space complexity of recursive DFS on a binary tree of height h?
- Maximum subarray sum in O(n)?
- Generating all permutations of n distinct elements takes at least…
- 'Next greater element' for each array item in O(n) uses…
- An LRU cache with O(1) get and put is typically built with…
- For a positive integer n, what does
n & (n - 1) == 0test? - A dynamic array doubles capacity when full. Amortized cost of append?