Algorithms and Data Structures Senior interview questions and answers

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

Take this quiz
  1. 1.Why does Dijkstra's algorithm give wrong results with negative edge weights?
  2. 2.What extra capability does Bellman-Ford have compared with Dijkstra?
  3. 3.How does A* differ from Dijkstra's algorithm?
  4. 4.What is the complexity of Floyd-Warshall, and when is it a reasonable choice?
  5. 5.How do Prim's and Kruskal's algorithms differ?
  6. 6.What makes union-find operations nearly O(1)?
  7. 7.What problem does a Fenwick tree (binary indexed tree) solve?
  8. 8.When would you choose a segment tree over a Fenwick tree?
  9. 9.What can a Bloom filter tell you about a key?
  10. 10.Why can't you delete an element from a standard Bloom filter?
  11. 11.What does HyperLogLog estimate, and why is it popular?
  12. 12.What advantage does consistent hashing give a distributed cache?
  13. 13.What is a skip list?
  14. 14.Why do databases use B-trees rather than binary search trees for indexes?
  15. 15.What trade-off do LSM trees make compared with B-trees?
  16. 16.What is the average complexity of quickselect for finding the k-th smallest element?
  17. 17.How do you pick a uniformly random sample of k items from a stream of unknown length?
  18. 18.What is wrong with shuffling an array via arr.sort(() => Math.random() - 0.5)?
  19. 19.How do you sort a 200 GB file on a machine with 8 GB of RAM?
  20. 20.How do you merge k sorted lists with n elements in total efficiently?
  21. 21.What is the key idea of the Rabin-Karp string search?
  22. 22.How does KMP achieve O(n + m) string search?
  23. 23.By the master theorem, what is the complexity of T(n) = 2T(n/2) + O(n)?
  24. 24.What does it mean that the 0/1 knapsack DP is pseudo-polynomial?
  25. 25.An interviewer describes a problem that reduces to the traveling salesman problem. What's a sensible response?
  26. 26.What does bitmask DP use as its state?
  27. 27.How do you reduce the memory of an LCS or edit distance DP from O(n × m) to O(m)?
  28. 28.What is amortized analysis with the "accounting" or "potential" method?
  29. 29.What is hash flooding?
  30. 30.Why can an O(n log n) algorithm lose to an O(n²) one on real inputs?
  31. 31.Why does Timsort perform so well on real-world data?
  32. 32.What is introsort and why is it used in C++ std::sort?
  33. 33.Which structure lets you find all intervals overlapping a point in O(log n + k)?
  34. 34.What does Tarjan's or Kosaraju's algorithm compute?
  35. 35.Why does React's reconciliation run in O(n) when a general tree diff is about O(n³)?
  36. 36.Which algorithm do git diff and many diff tools use by default?
  37. 37.A virtualized list renders only visible rows of 100,000 items with different heights. How does it find the first visible row quickly?
  38. 38.What does structural sharing in persistent data structures give you?
  39. 39.When does LFU beat LRU as a cache eviction policy?
  40. 40.How does a token bucket rate limiter work?
  41. 41.What is the complexity of building a binary heap from n unsorted elements with sift-down (heapify)?
  42. 42.Why can't you run binary search efficiently on a linked list?
  43. 43.Which approach answers "is this word in the dictionary?" for millions of words with the least memory, if rare false positives are fine?
  44. 44.What is the time complexity of building a suffix array naively by sorting all suffixes?
  45. 45.Why are tries often replaced by hash maps or radix trees in production?
  46. 46.Which algorithm should you use to detect a cycle in module imports at build time?
  47. 47.Why can't union-find detect cycles in a directed graph?
  48. 48.What is the complexity of checking whether a number is a power of two with n > 0 && (n & (n - 1)) === 0?
  49. 49.Why does 0.1 + 0.2 !== 0.3 matter for algorithms?
  50. 50.Which statement about average and worst case of hash table operations is correct?
  51. 51.What is cache-friendly about iterating a 2D array row by row in C-like layouts?
  52. 52.Which algorithm finds the maximum flow in a network?
  53. 53.A recursive solution is correct but times out because of repeated subproblems with three parameters. What's the usual first fix?
  54. 54.What is the expected number of comparisons for a successful lookup in a hash table with chaining and load factor α?
  55. 55.What does a monotonic deque give you in the "sliding window maximum" problem?
  56. 56.How do you maintain the running median of a stream efficiently?
  57. 57.What does it mean that a problem is NP-complete?
  58. 58.Why is the recursion depth of quicksort a concern, and how is it bounded?
  59. 59.Which structure would you use for an autocomplete that ranks suggestions by popularity?
  60. 60.What problem does a ring buffer with head and tail indices solve for a high-throughput queue?
  61. 61.What is the lower bound for finding an element in an unsorted array, and why?
  62. 62.Why is DFS preferred over BFS for some puzzles despite BFS finding shortest solutions?
  63. 63.What is the complexity of Array.prototype.sort in V8 on an array that's already sorted?
  64. 64.How do you find all pairs that sum to a target in an array with duplicates, without double counting?
  65. 65.Which statement about recursion and the call stack in JavaScript is correct?
  66. 66.What is the main advantage of Dijkstra with a Fibonacci heap over a binary heap?
  67. 67.How do you check whether two words are one edit apart in O(n)?
  68. 68.What does randomization give quicksort?
  69. 69.Which approach counts inversions (pairs i < j with a[i] > a[j]) in O(n log n)?
  70. 70.Why does a good hash function for strings process every character?
  71. 71.What does the "sparse table" structure answer in O(1)?
  72. 72.What is the main reason to prefer an adjacency matrix over adjacency lists?
  73. 73.An algorithm runs in O(n) but allocates a new array on every iteration of a hot loop. What's the likely real-world issue?
  74. 74.What does the "two heaps" trick fail to support efficiently, compared with a balanced BST?
  75. 75.Why is Array.prototype.indexOf inside filter a common hidden O(n²) in code reviews?