75 Data Structures and Algorithms (DSA) Questions Asked in Google Coding Rounds

In this blog post, we will explore 75 commonly asked Data Structures and Algorithms (DSA) questions in Google coding rounds. These questions are categorized by topic, with Java solutions provided for some of them along with sample inputs and outputs. Let's dive in!

---

1. Arrays (10 Questions)

1. Two Sum

   • Problem: Find indices of two numbers in an array that add up to a target.

   • Input: nums = [2, 7, 11, 15], target = 9

   • Output: [0, 1]

   • Solution:

     import java.util.HashMap;
     
     public class TwoSum {
         public int[] twoSum(int[] nums, int target) {
             HashMap<Integer, Integer> map = new HashMap<>();
             for (int i = 0; i < nums.length; i++) {
                 int complement = target - nums[i];
                 if (map.containsKey(complement)) {
                     return new int[]{map.get(complement), i};
                 }
                 map.put(nums[i], i);
             }
             throw new IllegalArgumentException("No solution found");
         }
     }

2. Maximum Subarray (Kadane's Algorithm)

   • Problem: Find the contiguous subarray with the maximum sum.

   • Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

   • Output: 6 (subarray [4, -1, 2, 1])

3. Merge Intervals

4. Product of Array Except Self

5. Find Duplicate Number

6. Rotate Image

7. Next Permutation

8. Trapping Rain Water

9. Search in Rotated Sorted Array

10. Subarray Sum Equals K

---

2. Strings (10 Questions)

1. Longest Palindromic Substring

   • Problem: Find the longest palindromic substring in a given string.

   • Input: s = "babad"

   • Output: "bab" (or "aba")

   • Solution:

     public class LongestPalindromicSubstring {
         public String longestPalindrome(String s) {
             if (s == null || s.length() < 1) return "";
             int start = 0, end = 0;
             for (int i = 0; i < s.length(); i++) {
                 int len1 = expandAroundCenter(s, i, i);
                 int len2 = expandAroundCenter(s, i, i + 1);
                 int len = Math.max(len1, len2);
                 if (len > end - start) {
                     start = i - (len - 1) / 2;
                     end = i + len / 2;
                 }
             }
             return s.substring(start, end + 1);
         }
     
         private int expandAroundCenter(String s, int left, int right) {
             while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                 left--;
                 right++;
             }
             return right - left - 1;
         }
     }

2. Group Anagrams

3. Valid Parentheses

4. Longest Substring Without Repeating Characters

5. String to Integer (atoi)

6. Check if Strings are Isomorphic

7. Minimum Window Substring

8. Implement StrStr()

9. Longest Common Prefix

10. Word Ladder

---

3. Linked Lists (10 Questions)

1. Reverse a Linked List

2. Detect Cycle in a Linked List

3. Merge Two Sorted Lists

   • Problem: Merge two sorted linked lists into one sorted list.

   • Input: l1 = [1, 2, 4], l2 = [1, 3, 4]

   • Output: [1, 1, 2, 3, 4, 4]

   • Solution:

     class ListNode {
         int val;
         ListNode next;
         ListNode(int x) { val = x; }
     }
     
     public class MergeTwoSortedLists {
         public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
             if (l1 == null) return l2;
             if (l2 == null) return l1;
     
             if (l1.val < l2.val) {
                 l1.next = mergeTwoLists(l1.next, l2);
                 return l1;
             } else {
                 l2.next = mergeTwoLists(l1, l2.next);
                 return l2;
             }
         }
     }

4. Remove Nth Node from End of List

5. Intersection of Two Linked Lists

6. Flatten a Multilevel Doubly Linked List

7. Reorder List

8. Partition List

9. Sort List

10. Rotate List

---

4. Trees and Graphs (15 Questions)

1. Binary Tree Inorder Traversal

2. Maximum Depth of Binary Tree

3. Validate Binary Search Tree

4. Binary Tree Level Order Traversal

5. Lowest Common Ancestor of a Binary Tree

6. Construct Binary Tree from Preorder and Inorder Traversal

7. Word Ladder

8. Course Schedule

9. Clone Graph

10. Number of Islands

11. Graph Valid Tree

12. Kth Smallest Element in a BST

13. Flatten Binary Tree to Linked List

14. Find Closest Leaf in a Binary Tree

15. Check Bipartite Graph

---

More Topics

The remaining topics include Recursion and Backtracking, Dynamic Programming, Sorting and Searching, Stacks and Queues, and Math/Bit Manipulation. Each topic has challenging problems that often appear in Google coding interviews.

For detailed explanations and additional questions with solutions, feel free to comment below or reach out for a comprehensive guide!