DSA Questions for Experienced Java Candidates

Table of Contents

1. Arrays
2. Strings
3. Linked Lists
4. Stacks and Queues
5. Trees
6. Graphs
7. Dynamic Programming
8. Sorting and Searching
9. Bit Manipulation
10. Backtracking
11. Miscellaneous

---

1. Arrays

1. Find the maximum subarray sum (Kadane's Algorithm).
2. Rotate an array by k steps.
3. Merge two sorted arrays.
4. Find the duplicate number in an array containing n+1 integers.
5. Implement a function to find the intersection of two arrays.
6. Sort an array of 0s, 1s, and 2s (Dutch National Flag problem).
7. Find the smallest subarray with a sum greater than a given value.
8. Implement a binary search algorithm.
9. Find the median of two sorted arrays.
10. Maximum product subarray.

1.1 Prefix Sum

1. LeetCode 303: Range Sum Query – Immutable
2. LeetCode 560: Subarray Sum Equals K
3. LeetCode 238: Product of Array Except Self
4. LeetCode 325: Maximum Size Subarray Sum Equals k
5. GFG: Longest Subarray With Sum K
6. LeetCode 974: Subarray Sums Divisible by K

Additional Resources

• Leetcode Practice: Prefix Sum Problems on Leetcode
• GeeksforGeeks Practice: Prefix Sum Problems on GFG

---

2. Strings

1. Check if two strings are anagrams.
2. Reverse a string without affecting special characters.
3. Implement a function to check if a string is a palindrome.
4. Longest substring without repeating characters.
5. Longest palindromic substring.
6. Implement strstr() or indexOf().
7. Group anagrams from a list of strings.
8. Count and say problem.
9. Find the minimum window substring.
10. Roman to Integer conversion.

3. Linked Lists

1. Reverse a singly linked list.
2. Detect and remove a cycle in a linked list.
3. Merge two sorted linked lists.
4. Find the intersection of two linked lists.
5. Remove nth node from the end of the list.
6. Clone a linked list with random pointers.
7. Flatten a multilevel doubly linked list.
8. Add two numbers represented by linked lists.
9. Find the middle node of a linked list.
10. Check if a linked list is a palindrome.

4. Stacks and Queues

1. Implement a stack using arrays or linked lists.
2. Implement a queue using two stacks.
3. Next greater element in an array.
4. Valid parentheses problem.
5. Implement a circular queue.
6. Sort a stack using recursion.
7. LRU Cache implementation.
8. Evaluate a postfix expression.
9. Sliding window maximum.
10. Min stack implementation.

5. Trees

1. Implement in-order, pre-order, and post-order traversal.
2. Level-order traversal of a binary tree.
3. Find the height of a binary tree.
4. Check if a binary tree is balanced.
5. Lowest common ancestor of two nodes in a binary tree.
6. Serialize and deserialize a binary tree.
7. Binary search tree validation.
8. Kth smallest element in a BST.
9. Path sum problems.
10. Convert a binary tree to a doubly linked list.

6. Graphs

1. Implement depth-first search (DFS) and breadth-first search (BFS).
2. Detect a cycle in a directed and undirected graph.
3. Find the shortest path in an unweighted graph.
4. Implement Dijkstra's algorithm.
5. Implement Kruskal's and Prim's algorithms for MST.
6. Topological sort of a directed acyclic graph (DAG).
7. Number of islands problem.
8. Word ladder problem.
9. Floyd-Warshall algorithm.
10. Check if a graph is bipartite.

7. Dynamic Programming

1. Longest increasing subsequence.
2. 0/1 Knapsack problem.
3. Coin change problem.
4. Longest common subsequence.
5. Edit distance problem.
6. Maximum profit in a rod cutting problem.
7. Matrix chain multiplication.
8. Subset sum problem.
9. Maximum sum increasing subsequence.
10. Decode ways.
11. Palindrome Partitioning II.
12. Count Number of Texts.

8. Sorting and Searching

1. Quick sort implementation.
2. Merge sort implementation.
3. Heap sort implementation.
4. Binary search variations (lower bound, upper bound).
5. Search in a rotated sorted array.
6. Find the kth largest element in an array.
7. Count inversions in an array.
8. Find the peak element.
9. Median in a stream of integers.
10. Aggressive cows (binary search problem).

9. Bit Manipulation

1. Check if a number is a power of two.
2. Count the number of set bits in an integer.
3. Find the single number in an array where every other number appears twice.
4. XOR of all numbers from 1 to n.
5. Swap two numbers without using a temporary variable.
6. Find the two non-repeating elements in an array of repeating elements.
7. Reverse bits of a given 32-bit unsigned integer.
8. Find the missing number in an array.
9. Implement bitwise AND of numbers range.
10. Power of two, three, or four determination using bitwise operations.

10. Backtracking

1. Solve the N-Queens problem.
2. Sudoku solver.
3. Word search in a 2D grid.
4. Generate all subsets of a set (power set).
5. Generate all permutations of a string.
6. Rat in a maze problem.
7. M-coloring problem.
8. Knight's tour problem.
9. Hamiltonian path and cycle problem.
10. Find all palindrome partitioning of a string.
11. Letter Combinations of a Phone Number

11. Miscellaneous

1. Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
2. Implement an LFU Cache.
3. Find the maximum meetings in one room.
4. Implement a trie (prefix tree) and its operations.
5. Find the maximum profit in stock buy and sell.
6. Median of a data stream.
7. Count distinct elements in every window of size k.

---

Notes

• Coding Practice Platforms: Use platforms like LeetCode, HackerRank, Codeforces, or GeeksforGeeks for coding practice.
• Time Complexity: Always analyze the time and space complexity of your solution.
• Mock Interviews: Conduct mock interviews to assess your problem-solving and coding skills.