100 Must-Know DSA and Dynamic Programming Questions to Secure Your Spot at FAANG and Beyond

1. Given an array of integers, find the maximum sum subarray using Kadane’s algorithm. (Amazon)

2. Given a string, find the length of the longest palindromic subsequence. (Amazon)

3. Implement a trie data structure. (Google)

4. Given a 2D grid of 0s and 1s, find the maximum size rectangle containing only 1s. (Amazon)

5. Given two strings, find the longest common subsequence. (Microsoft)

6. Implement a binary search algorithm. (Amazon)

7. Given a binary tree, find the maximum path sum. (Amazon)

8. Given a sorted array of integers, find the number of occurrences of a target integer. (Amazon)

9. Implement a hash table with collision resolution using separate chaining. (Amazon)

10. Given a string, find the longest palindromic substring. (Microsoft)

11. Given a linked list, find the middle element. (Amazon)

12. Implement a stack using two queues. (Amazon)

13. Given a matrix of integers, find the minimum path sum from the top left to the bottom right. (Google)

14. Given a string and a dictionary of words, find all the words in the string that can be formed by concatenating the words from the dictionary. (Google)

15. Given a binary tree, check if it is a binary search tree. (Amazon)

16. Given a set of intervals, merge overlapping intervals. (Amazon)

17. Given a set of n jobs with start and end times, find the maximum number of jobs that can be scheduled without overlapping. (Google)

18. Given a string and a pattern, find all the occurrences of the pattern in the string. (Amazon)

19. Implement a heap data structure. (Amazon)

20. Given a set of n points in a 2D plane, find the closest pair of points. (Amazon)

21. Given a set of n items with weights and values, find the maximum value that can be obtained with a knapsack of capacity W. (Google)

22. Given a binary tree, serialize it into a string and deserialize it back to the original tree. (Amazon)

23. Implement Dijkstra’s algorithm for finding the shortest path in a graph. (Google)

24. Given a binary tree, find the lowest common ancestor of two nodes. (Amazon)

25. Given a set of n intervals, find the minimum number of points that can be placed to cover all the intervals. (Amazon)

26. Implement a binary search tree data structure. (Amazon)

27. Given a set of n points in a 2D plane, find the maximum number of points that lie on the same straight line. (Amazon)

28. Given a string, find the length of the longest substring without repeating characters. (Amazon)

29. Implement a graph data structure using adjacency matrix and adjacency list representations. (Google)

30. Given a set of n strings, find the longest common prefix. (Amazon)

31. Implement an AVL tree data structure. (Google)

32. Given a set of n intervals, find the maximum number of intervals that can be covered without overlapping. (Amazon)

33. Given a string, find the length of the longest substring that contains at most k distinct characters. (Amazon)

34. Implement a priority queue data structure. (Amazon)

35. Given a set of n points in a 2D plane, find the convex hull. (Google)

36. Given a binary tree, find the diameter (the longest path between any two nodes). (Amazon)

37. Implement a doubly linked list data structure. (Amazon)

38. Given a set of n intervals, find the minimum number of intervals that need to be removed to make the remaining intervals non-overlapping. (Google)

39. Implement a queue data structure. (Amazon)

40. Given a set of n points in a 2D plane, find the k closest points to a given point. (Amazon)

41. Given a binary tree, flatten it into a linked list in-place. (Amazon)

42. Implement a binary heap data structure. (Google)

43. Given a set of n intervals, find the maximum number of non-overlapping intervals that can be selected. (Amazon)

44. Given a set of n points in a 2D plane, find the shortest path between two points using A* algorithm. (Google)

45. Implement a red-black tree data structure. (Google)

46. Given a set of n intervals, find the minimum number of points that need to be removed to make the remaining intervals non-overlapping. (Amazon)

47. Given a string, find the length of the longest substring that is a palindrome. (Amazon)

48. Implement a merge sort algorithm. (Amazon)

49. Given a set of n points in a 2D plane, find the k closest points to the origin. (Amazon)

50. Given a binary tree, find the kth smallest element. (Google)

51. Implement a quick sort algorithm. (Amazon)

52. Given a set of n intervals, find the maximum number of points that can be placed to cover the intervals, where each point can cover a range of length k. (Google)

53. Implement a radix sort algorithm. (Amazon)

54. Given a set of n points in a 2D plane, find the minimum spanning tree using Kruskal’s algorithm. (Google)

55. Implement a bubble sort algorithm. (Amazon)

56. Given a binary tree, find the sum of all left leaves. (Amazon)

57. Implement a counting sort algorithm. (Amazon)

58. Given a set of n points in a 2D plane, find the minimum spanning tree using Prim’s algorithm. (Google)

59. Implement a selection sort algorithm. (Amazon)

60. Given a binary tree, find the maximum width. (Amazon)

61. Implement an insertion sort algorithm. (Amazon)

62. Given a set of n points in a 2D plane, find the closest pair of points using divide and conquer. (Amazon)

63. Implement a shell sort algorithm. (Amazon)

64. Given a binary tree, find the vertical sum of nodes. (Amazon)

65. Implement a bucket sort algorithm. (Google)

66. Given a set of n points in a 2D plane, find the maximum sum rectangle in a matrix. (Amazon)

67. Implement a heap sort algorithm. (Amazon)

68. Given a binary tree, find the maximum depth. (Amazon)

69. Implement a topological sort algorithm. (Google)

70. Given a set of n points in a 2D plane, find the number of pairs of points with distance less than k. (Google)

71. Implement a shell sort algorithm. (Amazon)

72. Given a binary tree, find the lowest common ancestor of two nodes using parent pointers. (Amazon)

73. Implement a bucket sort algorithm. (Google)

74. Given a set of n points in a 2D plane, find the convex hull using Graham’s algorithm. (Amazon)

75. Implement a heap sort algorithm. (Amazon)

76. Given a binary tree, find the inorder successor of a node. (Amazon)

77. Implement a shell sort algorithm. (Amazon)

78. Given a set of n points in a 2D plane, find the maximum sum subarray in a matrix. (Amazon)

79. Implement a counting sort algorithm

1. Given a binary tree, find the lowest common ancestor of two nodes. (Amazon)

2. Implement a bucket sort algorithm. (Google)

3. Given a set of n points in a 2D plane, find the intersection of two line segments. (Google)

4. Implement a heap sort algorithm. (Amazon)

5. Given a binary tree, serialize and deserialize it. (Amazon)

6. Implement a shell sort algorithm. (Amazon)

7. Given a set of n points in a 2D plane, find the maximum product of two points whose distance is less than k. (Google)

8. Implement a counting sort algorithm. (Amazon)

9. Given a binary tree, find the level order traversal. (Amazon)

10. Implement a quick sort algorithm. (Amazon)

11. Given a set of n points in a 2D plane, find the line that passes through the most number of points. (Google)

12. Implement a radix sort algorithm. (Amazon)

13. Given a binary tree, find the zigzag level order traversal. (Amazon)

14. Implement a selection sort algorithm. (Amazon)

15. Given a set of n points in a 2D plane, find the maximum sum path in a matrix. (Amazon)

16. Implement a bucket sort algorithm. (Google)

17. Given a binary tree, find the level order traversal using constant space. (Amazon)

18. Implement a shell sort algorithm. (Amazon)

19. Given a set of n points in a 2D plane, find the maximum number of points that can be enclosed in a rectangle with sides parallel to the coordinate axes. (Google)

20. Implement a counting sort algorithm. (Amazon)

21. Given a binary tree, find the diameter. (Amazon)

These are just a few examples of the types of questions you might encounter in a technical interview. It's important to note that companies may ask a wide variety of questions and may also ask questions specific to their industry or the role you are applying for. Additionally, some companies may also ask behavioral or situational questions to assess how you would handle certain situations. It's important to prepare thoroughly and practice as much as possible to increase your chances of success.

Thanks For Reading My Blog! 😍

TATA!