Most Used Coding exercises

Many coding problems in interviews are variations of common problem patterns. Recognizing these patterns and their solutions can help you solve many problems efficiently. Below is a breakdown of common problem categories similar to Two Sum and their solutions.

---

1️⃣ Two Sum Variations & Related Patterns

The Two Sum problem belongs to the "Pair Sum" category, but many variations exist. Some common types include:

(A) Two Sum (Classic)

• Problem: Find two numbers in an array that sum to a target.

• Solution: Use a HashSet for O(N)O(N) time complexity.

(B) Two Sum (Sorted Array) → Two Pointers

• Problem: Given a sorted array, find a pair that sums to a target.

• Solution: Use the Two Pointers technique:

  • Place one pointer at the start and another at the end.

  • If the sum is too low, move the left pointer.

  • If the sum is too high, move the right pointer.

  • Time Complexity: O(N)O(N).

(C) Two Sum (Unique Pairs)

• Problem: Find all unique pairs that sum to a target.

• Solution: Use a HashSet but ensure uniqueness (e.g., store pairs in a Set<Pair<Integer, Integer>>).

(D) Three Sum

• Problem: Find three numbers that sum to a target.

• Solution:

  • Sort the array.

  • Fix one number and apply the Two Pointers technique on the remaining part.

  • Time Complexity: O(N2)O(N^2).

(E) Four Sum / K Sum

• Problem: Find four (or k) numbers that sum to a target.

• Solution: Use recursion + two pointers for efficient solving.

---

2️⃣ Sliding Window Variations

Used when dealing with subarrays, continuous sequences, or optimal windows.

(A) Find the Longest Subarray with a Given Sum

• Problem: Given an array, find the longest contiguous subarray that sums to a target.

• Solution: Use a HashMap to store prefix sums for efficient lookup.

(B) Maximum Sum Subarray of Fixed Length (Kadane’s Algorithm)

• Problem: Find the subarray of size k with the maximum sum.

• Solution: Use the Sliding Window approach.

(C) Longest Substring Without Repeating Characters

• Problem: Find the longest substring where all characters are unique.

• Solution: Use a Sliding Window + HashSet.

---

3️⃣ HashMap-Based Problems

Used when you need fast lookups.

(A) Subarray Sum Equals K

• Problem: Find the number of subarrays that sum to kk.

• Solution: Use a HashMap to store prefix sums.

(B) Group Anagrams

• Problem: Given an array of words, group anagrams together.

• Solution: Use a HashMap where the key is a sorted word.

---

4️⃣ Sorting & Two-Pointer Variations

When dealing with arrays & intervals, sorting can help.

(A) Merge Intervals

• Problem: Given intervals [start,end][start, end], merge overlapping ones.

• Solution: Sort by start time, then merge overlapping intervals.

(B) Meeting Rooms (Interval Scheduling)

• Problem: Find the minimum number of meeting rooms required.

• Solution: Use a priority queue.

---

5️⃣ Graph-Based Problems

Used for connectivity, paths, shortest distances, etc..

(A) Shortest Path in a Graph

• Solution: Use Dijkstra’s Algorithm (Priority Queue).

(B) Detect Cycle in a Graph

• Solution: Use DFS with visited nodes.

---

6️⃣ Backtracking Problems

Used when solving combinations, permutations, and constraints.

(A) Subsets & Combinations

• Problem: Find all subsets of an array.

• Solution: Use Backtracking (recursive DFS).

(B) Word Search

• Problem: Find a word in a grid.

• Solution: Use Backtracking + DFS.

---

7️⃣ Dynamic Programming (DP) Problems

Used when solving problems with optimal substructures.

(A) Fibonacci Sequence (Classic DP)

• Solution: Use memoization (top-down) or tabulation (bottom-up).

(B) Longest Increasing Subsequence

• Problem: Find the longest increasing subsequence in an array.

• Solution: Use Binary Search + DP.

---

8️⃣ Binary Search Variations

Used for searching efficiently in sorted structures.

(A) Find First and Last Position of Element in Sorted Array

• Solution: Binary Search (Modified).

(B) Find Peak Element

• Solution: Use Binary Search on hills and valleys.

---

Conclusion: How to Approach Any Coding Problem

1. Identify the problem type (Two Sum, Sliding Window, DP, etc.).

2. Choose the right data structure (HashMap, Set, Priority Queue).

3. Optimize for time complexity (Brute Force → Optimized approach).

4. Write & test code efficiently.

Here are four exercises, each focusing on a commonly used data structure: Set, HashMap, Stack, and Priority Queue. These exercises are structured to resemble real interview problems.

---

1️⃣ HashSet Exercise: Find First Repeating Element

🔹 Problem:
Given an array of integers, find the first repeating element (the first element that appears more than once). If no element repeats, return -1.

🔹 Example:

Input: [4, 3, 2, 7, 8, 3, 2, 1]  
Output: 3

🔹 Hint:

• Use a HashSet to track seen elements.

• As you iterate, return the first number already in the set.

---

2️⃣ HashMap Exercise: Subarray Sum Equals K

🔹 Problem:
Given an array of integers and an integer k, find the number of contiguous subarrays that sum to k.

🔹 Example:

Input: nums = [1, 1, 1], k = 2  
Output: 2

🔹 Hint:

• Use a HashMap to store the prefix sum at each step.

• If prefixSum - k exists in the map, count the occurrences.

---

3️⃣ Stack Exercise: Valid Parentheses

🔹 Problem:
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
A string is valid if:

• Open brackets are closed by the same type of brackets.

• Open brackets are closed in the correct order.

🔹 Example:

Input: "{[()]}"  
Output: true  

Input: "{[(])}"  
Output: false

🔹 Hint:

• Use a Stack to push opening brackets.

• Pop the stack when encountering a closing bracket and check for a match.

---

4️⃣ Priority Queue (Heap) Exercise: Kth Largest Element in an Array

🔹 Problem:
Given an integer array nums and an integer k, return the kth largest element in the array.

🔹 Example:

Input: nums = [3,2,1,5,6,4], k = 2  
Output: 5

🔹 Hint:

• Use a Min Heap (PriorityQueue in Java).

• Maintain a heap of size k, and return the top element.

---

Here are the solutions for each exercise, along with explanations. 🚀

---

1️⃣ HashSet Solution: Find First Repeating Element

Approach:

• Use a HashSet to store elements as we traverse the array.

• If an element is already in the set, return it (it's the first repeating element).

• If no repeating element is found, return -1.

Code:

import java.util.HashSet;

public class FirstRepeatingElement {
    public static int findFirstRepeating(int[] arr) {
        HashSet<Integer> seen = new HashSet<>();

        for (int num : arr) {
            if (seen.contains(num)) {
                return num; // First repeated element
            }
            seen.add(num);
        }

        return -1; // No repeats found
    }

    public static void main(String[] args) {
        int[] nums = {4, 3, 2, 7, 8, 3, 2, 1};
        System.out.println(findFirstRepeating(nums)); // Output: 3
    }
}

Complexity:

• Time Complexity: O(N)O(N) (since we traverse the array once).

• Space Complexity: O(N)O(N) (worst case, all unique elements are stored).

---

2️⃣ HashMap Solution: Subarray Sum Equals K

Approach:

• Use a HashMap to store prefix sums.

• At each step, check if prefixSum - k exists in the map.

• If it does, it means a subarray ending at the current index sums to k.

Code:

import java.util.HashMap;

public class SubarraySumK {
    public static int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1); // Initialize with sum 0 appearing once

        int prefixSum = 0;
        int count = 0;

        for (int num : nums) {
            prefixSum += num;

            if (prefixSumCount.containsKey(prefixSum - k)) {
                count += prefixSumCount.get(prefixSum - k);
            }

            prefixSumCount.put(prefixSum, prefixSumCount.getOrDefault(prefixSum, 0) + 1);
        }

        return count;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1};
        int k = 2;
        System.out.println(subarraySum(nums, k)); // Output: 2
    }
}

Complexity:

• Time Complexity: O(N)O(N) (single traversal).

• Space Complexity: O(N)O(N) (stores prefix sums).

---

3️⃣ Stack Solution: Valid Parentheses

Approach:

• Use a Stack to track opening brackets.

• If we encounter a closing bracket, check if it matches the last opened bracket.

• If the stack is empty at the end, the string is valid.

Code:

import java.util.Stack;

public class ValidParentheses {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) return false; // No matching opening bracket

                char open = stack.pop();
                if ((ch == ')' && open != '(') ||
                    (ch == '}' && open != '{') ||
                    (ch == ']' && open != '[')) {
                    return false; // Mismatched pair
                }
            }
        }

        return stack.isEmpty(); // Stack should be empty if all brackets matched
    }

    public static void main(String[] args) {
        System.out.println(isValid("{[()]}")); // Output: true
        System.out.println(isValid("{[(])}")); // Output: false
    }
}

Complexity:

• Time Complexity: O(N)O(N) (single pass).

• Space Complexity: O(N)O(N) (stack usage in worst case).

---

4️⃣ Priority Queue (Heap) Solution: Kth Largest Element

Approach:

• Use a Min Heap (PriorityQueue in Java) of size k.

• Maintain only the k largest elements in the heap.

• The top of the heap (peek()) gives the kth largest element.

Code:

import java.util.PriorityQueue;

public class KthLargestElement {
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // Remove the smallest element
            }
        }

        return minHeap.peek(); // Kth largest element
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println(findKthLargest(nums, k)); // Output: 5
    }
}

Complexity:

• Time Complexity: O(Nlog⁡k)O(N \log k) (since we perform heap operations O(log⁡k)O(\log k) for each element).

• Space Complexity: O(k)O(k) (heap stores k elements).

---