Algorithms and Data Structures Middle interview questions and answers

75 questions for a Algorithms and Data Structures (Middle) interview - with correct answers, explanations and links to the docs.

Take this quiz
  1. 1.How does merge sort work?
  2. 2.What is the main drawback of merge sort on arrays?
  3. 3.What is the worst case of quicksort and when does it happen?
  4. 4.Why is quicksort often faster than merge sort in practice despite the same O(n log n) average?
  5. 5.What does partitioning do in quicksort?
  6. 6.Which sorting algorithm does V8 use for Array.prototype.sort?
  7. 7.Why can't any comparison sort beat O(n log n) in the worst case?
  8. 8.When can counting sort beat O(n log n)?
  9. 9.What is a binary heap (min-heap)?
  10. 10.What are the costs of the main operations of a binary heap?
  11. 11.How do you find the k largest elements of a large array efficiently?
  12. 12.Does JavaScript have a built-in priority queue?
  13. 13.What does this binary search return when target is not in the array?
  14. 14.Why is mid = lo + Math.floor((hi - lo) / 2) recommended in many languages instead of (lo + hi) / 2?
  15. 15.What does "binary search on the answer" mean?
  16. 16.How do you find a value in a sorted array that was rotated, like [4, 5, 6, 1, 2, 3], in O(log n)?
  17. 17.What is the sliding window technique?
  18. 18.Longest substring without repeating characters: what's the O(n) idea?
  19. 19.Two Sum on a sorted array: what's the O(n) approach without extra memory?
  20. 20.How do you merge overlapping intervals like [[1,3],[2,6],[8,10]]?
  21. 21.What is a monotonic stack used for?
  22. 22.How do you implement a queue with two stacks so that each operation is amortized O(1)?
  23. 23.Which structure gives O(1) insertion and removal at both ends?
  24. 24.How do you detect a cycle in a linked list with O(1) extra memory?
  25. 25.How do you find the middle of a linked list in one pass?
  26. 26.How do you reverse a singly linked list iteratively?
  27. 27.How is an LRU cache with O(1) get and put usually built?
  28. 28.Why does BFS find the shortest path in an unweighted graph?
  29. 29.Why do graph traversals keep a visited set?
  30. 30.How do you count islands (connected groups of 1s) in a grid of 0s and 1s?
  31. 31.What is a topological sort?
  32. 32.How does Kahn's algorithm compute a topological order?
  33. 33.How do you detect a cycle in a directed graph with DFS?
  34. 34.What does a union-find (disjoint set) structure support?
  35. 35.What is a trie good for?
  36. 36.Which tree traversal visits the values of a BST in sorted order?
  37. 37.How do you traverse a binary tree level by level?
  38. 38.How do you compute the maximum depth of a binary tree recursively?
  39. 39.What problem do self-balancing trees (AVL, red-black) solve?
  40. 40.Which two properties make a problem a good fit for dynamic programming?
  41. 41.What is the difference between memoization and tabulation?
  42. 42.Climbing stairs: you can step 1 or 2 stairs at a time. How many ways are there to climb n stairs?
  43. 43.Why can a greedy algorithm fail for making change with coins [1, 3, 4] and amount 6?
  44. 44.What is the complexity of the coin change DP for amount A and k coin types?
  45. 45.What is the longest common subsequence (LCS) of two strings?
  46. 46.What does the Levenshtein (edit) distance measure?
  47. 47.What is the idea of Kadane's algorithm for the maximum subarray sum?
  48. 48.How many subsets does a set of n elements have, and why does that matter?
  49. 49.What is backtracking?
  50. 50.How many permutations does an array of n distinct elements have?
  51. 51.How can you avoid a stack overflow in deep recursion in JavaScript?
  52. 52.What is the space complexity of a recursive DFS on a tree of height h?
  53. 53.What happens to a hash table when its load factor gets too high?
  54. 54.What makes a good hash function for a hash table?
  55. 55.What does the group anagrams problem usually use as a map key?
  56. 56.How do you answer "sum of elements from i to j" many times on a static array?
  57. 57.Subarray sum equals k: why do we store counts of prefix sums in a hash map?
  58. 58.What does Dijkstra's algorithm compute?
  59. 59.Which data structure makes Dijkstra's algorithm efficient?
  60. 60.What is the complexity of BFS or DFS on a graph stored as adjacency lists?
  61. 61.How do you check if a graph can be colored with two colors so that no edge connects equal colors?
  62. 62.What does x & (x - 1) do for a positive integer x?
  63. 63.Every number in an array appears twice except one. How do you find it in O(n) time and O(1) memory?
  64. 64.What is the complexity of this function?
  65. 65.Which algorithm finds a minimum spanning tree by adding the cheapest edges that don't create a cycle?
  66. 66.Why does the order of keys in a JavaScript object not always match insertion order?
  67. 67.What is the complexity of checking whether two strings of length n are equal?
  68. 68.Which problem is solved by keeping the k most recent values in a fixed-size ring buffer?
  69. 69.What is the "meet in the middle" idea in two-sided BFS?
  70. 70.Why are arrays usually faster to iterate than linked lists even though both are O(n)?
  71. 71.What is the time complexity of str.split("").sort().join("") for a string of length n?
  72. 72.What does this function do, and what is its complexity?
  73. 73.What does it cost to insert a value into a sorted array and keep it sorted?
  74. 74.How do you rotate an array right by k positions in place with O(1) extra memory?
  75. 75.Subset sum: can some of the numbers add up to target? What is the classic DP solution?