Top Data Structures and Algorithms for Tech Interviews: Java Solutions

This blog provides Java solutions for commonly asked data structures and algorithms (DSA) problems in technical interviews at companies like Amazon, Google, Microsoft, Uber, Flipkart, Atlassian, and Walmart. Each section includes a problem, a brief explanation, and a complete Java solution. The content is SEO-optimized to help you prepare effectively for coding interviews.

---

1. Graphs & Traversals

Number of Islands (Flipkart, Uber, Atlassian)

Problem: Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Solution: Use DFS to mark all connected '1's as visited for each island.

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int islands = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    islands++;
                    dfs(grid, i, j);
                }
            }
        }
        return islands;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') return;
        grid[i][j] = '0'; // Mark as visited
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }
}

---

Word Ladder (Amazon, Google)

Problem: Transform one word into another by changing one letter at a time, with each intermediate word being valid. Find the shortest transformation sequence length.

Solution: Use BFS to find the shortest path in a word graph.

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) return 0;

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int level = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                if (word.equals(endWord)) return level;

                char[] chars = word.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char original = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[j] = c;
                        String newWord = new String(chars);
                        if (dict.contains(newWord)) {
                            queue.offer(newWord);
                            dict.remove(newWord);
                        }
                    }
                    chars[j] = original;
                }
            }
            level++;
        }
        return 0;
    }
}

---

Course Schedule (Google, Uber, Microsoft)

Problem: Given a list of courses and prerequisites, determine if you can finish all courses (detect a cycle in a directed graph).

Solution: Use DFS to detect cycles.

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        for (int[] pre : prerequisites) graph.get(pre[1]).add(pre[0]);

        boolean[] visited = new boolean[numCourses];
        boolean[] recStack = new boolean[numCourses];

        for (int i = 0; i < numCourses; i++) {
            if (!visited[i] && hasCycle(graph, i, visited, recStack)) return false;
        }
        return true;
    }

    private boolean hasCycle(List<List<Integer>> graph, int course, boolean[] visited, boolean[] recStack) {
        visited[course] = true;
        recStack[course] = true;

        for (int next : graph.get(course)) {
            if (!visited[next] && hasCycle(graph, next, visited, recStack)) return true;
            if (recStack[next]) return true;
        }

        recStack[course] = false;
        return false;
    }
}

---

Clone Graph (Amazon, Google)

Problem: Create a deep copy of a connected undirected graph.

Solution: Use DFS with a hash map to track cloned nodes.

class Node {
    public int val;
    public List<Node> neighbors;
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<>();
    }
}

class Solution {
    private Map<Node, Node> map = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (map.containsKey(node)) return map.get(node);

        Node copy = new Node(node.val);
        map.put(node, copy);

        for (Node neighbor : node.neighbors) {
            copy.neighbors.add(cloneGraph(neighbor));
        }
        return copy;
    }
}

---

Evaluate Division (Google, Uber, Microsoft)

Problem: Given equations like a/b = 2.0, evaluate queries like a/c.

Solution: Build a graph and use DFS to find paths.

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = new HashMap<>();

        // Build graph
        for (int i = 0; i < equations.size(); i++) {
            String u = equations.get(i).get(0), v = equations.get(i).get(1);
            graph.computeIfAbsent(u, k -> new HashMap<>()).put(v, values[i]);
            graph.computeIfAbsent(v, k -> new HashMap<>()).put(u, 1.0 / values[i]);
        }

        double[] result = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String start = queries.get(i).get(0), end = queries.get(i).get(1);
            result[i] = dfs(start, end, new HashSet<>(), graph);
        }
        return result;
    }

    private double dfs(String start, String end, Set<String> visited, Map<String, Map<String, Double>> graph) {
        if (!graph.containsKey(start) || !graph.containsKey(end)) return -1.0;
        if (start.equals(end)) return 1.0;

        visited.add(start);
        Map<String, Double> neighbors = graph.get(start);

        for (String next : neighbors.keySet()) {
            if (!visited.contains(next)) {
                double result = dfs(next, end, visited, graph);
                if (result != -1.0) return neighbors.get(next) * result;
            }
        }
        return -1.0;
    }
}

---

2. Intervals, Events & Scheduling

Merge Intervals (Google, Amazon, Microsoft)

Problem: Merge overlapping intervals into non-overlapping ones.

Solution: Sort intervals by start time and merge overlapping ones.

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> result = new ArrayList<>();

        int[] current = intervals[0];
        result.add(current);

        for (int[] interval : intervals) {
            if (interval[0] <= current[1]) {
                current[1] = Math.max(current[1], interval[1]);
            } else {
                current = interval;
                result.add(current);
            }
        }

        return result.toArray(new int[result.size()][]);
    }
}

---

Meeting Rooms II (Amazon, Uber)

Problem: Find the minimum number of meeting rooms required for a set of meetings.

Solution: Use a priority queue to track end times.

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int[] interval : intervals) {
            if (!pq.isEmpty() && pq.peek() <= interval[0]) {
                pq.poll();
            }
            pq.offer(interval[1]);
        }

        return pq.size();
    }
}

---

Insert Interval (Google, Flipkart)

Problem: Insert a new interval into a list of non-overlapping intervals and merge if necessary.

Solution: Linear scan with merging.

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0, n = intervals.length;

        // Add intervals before newInterval
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i++]);
        }

        // Merge overlapping intervals
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);

        // Add remaining intervals
        while (i < n) result.add(intervals[i++]);

        return result.toArray(new int[result.size()][]);
    }
}

---

Employee Free Time (Amazon, Atlassian)

Problem: Find common free time slots among employee schedules.

Solution: Use a sweep line approach.

class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> all = new ArrayList<>();
        for (List<Interval> employee : schedule) all.addAll(employee);

        all.sort((a, b) -> a.start - b.start);
        List<Interval> result = new ArrayList<>();

        int prevEnd = all.get(0).end;
        for (Interval interval : all) {
            if (interval.start > prevEnd) {
                result.add(new Interval(prevEnd, interval.start));
            }
            prevEnd = Math.max(prevEnd, interval.end);
        }

        return result;
    }
}
class Interval {
    int start, end;
    Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

---

Minimum Number of Arrows to Burst Balloons (Google, Walmart)

Problem: Find the minimum arrows needed to burst all balloons.

Solution: Greedy approach by sorting intervals.

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

        int arrows = 1, end = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > end) {
                arrows++;
                end = points[i][1];
            }
        }
        return arrows;
    }
}

---

3. Matrix Manipulation & Backtracking

Word Search (Google, Uber)

Problem: Find if a word exists in a grid of characters.

Solution: Use DFS with backtracking.

class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int i, int j, int k) {
        if (k == word.length()) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k)) return false;

        char temp = board[i][j];
        board[i][j] = '#';

        boolean found = dfs(board, word, i+1, j, k+1) ||
                        dfs(board, word, i-1, j, k+1) ||
                        dfs(board, word, i, j+1, k+1) ||
                        dfs(board, word, i, j-1, k+1);

        board[i][j] = temp;
        return found;
    }
}

---

Sudoku Solver (Google, Microsoft, Oracle)

Problem: Solve a partially filled 9x9 Sudoku board.

Solution: Use backtracking to try valid numbers.

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }

    private boolean solve(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (solve(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == c || board[i][col] == c || 
                board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
        }
        return true;
    }
}

---

Spiral Matrix (Flipkart, Uber, Microsoft)

Problem: Return all elements of a matrix in spiral order.

Solution: Track boundaries and traverse layer by layer.

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix.length == 0) return result;

        int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            for (int i = left; i <= right; i++) result.add(matrix[top][i]);
            top++;

            for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
            right--;

            if (top <= bottom) {
                for (int i = right; i >= left; i--) result.add(matrix[bottom][i]);
                bottom--;
            }

            if (left <= right) {
                for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
                left++;
            }
        }
        return result;
    }
}

---

N-Queens (Amazon, Google)

Problem: Place N queens on an NxN board so no two queens threaten each other.

Solution: Use backtracking to place queens.

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(result, board, 0);
        return result;
    }

    private void backtrack(List<List<String>> result, char[][] board, int row) {
        if (row == board.length) {
            result.add(construct(board));
            return;
        }

        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(result, board, row + 1);
                board[row][col] = '.';
            }
        }
    }

    private boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] == 'Q' && (j == col || i + j == row + col || i - j == row - col)) {
                    return false;
                }
            }
        }
        return true;
    }

    private List<String> construct(char[][] board) {
        List<String> list = new ArrayList<>();
        for (char[] row : board) list.add(new String(row));
        return list;
    }
}

---

Unique Paths II (Amazon, Walmart)

Problem: Find the number of unique paths in a grid with obstacles.

Solution: Use dynamic programming.

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) continue;
                if (i > 0) dp[i][j] += dp[i-1][j];
                if (j > 0) dp[i][j] += dp[i][j-1];
            }
        }

        return dp[m-1][n-1];
    }
}

---

4. Binary Trees & Binary Search Trees

Lowest Common Ancestor in Binary Tree (Amazon, Flipkart, Uber)

Problem: Find the lowest common ancestor of two nodes in a binary tree.

Solution: Use recursive DFS.

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) return root;
        return left != null ? left : right;
    }
}

---

Kth Smallest Element in BST (Google, Amazon)

Problem: Find the kth smallest element in a BST.

Solution: Use inorder traversal.

class Solution {
    private int count = 0, result = 0;

    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }

    private void inorder(TreeNode root, int k) {
        if (root == null) return;

        inorder(root.left, k);
        count++;
        if (count == k) result = root.val;
        inorder(root.right, k);
    }
}

---

Serialize & Deserialize Binary Tree (Google, Amazon, Atlassian)

Problem: Serialize and deserialize a binary tree.

Solution: Use preorder traversal with string manipulation.

public class Codec {
    // Serialize
    public String serialize(TreeNode root) {
        if (root == null) return "null";
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    // Deserialize
    public TreeNode deserialize(String data) {
        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
        return deserializeHelper(queue);
    }

    private TreeNode deserializeHelper(Queue<String> queue) {
        String val = queue.poll();
        if (val.equals("null")) return null;

        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = deserializeHelper(queue);
        node.right = deserializeHelper(queue);
        return node;
    }
}

---

Validate Binary Search Tree (Uber, Walmart)

Problem: Check if a binary tree is a valid BST.

Solution: Use inorder traversal with range checking.

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validate(TreeNode root, long min, long max) {
        if (root == null) return true;
        if (root.val <= min || root.val >= max) return false;
        return validate(root.left, min, root.val) && validate(root.right, root.val, max);
    }
}

---

Binary Tree Zigzag Level Order Traversal (Amazon, Google, Flipkart)

Problem: Traverse a binary tree in zigzag order.

Solution: Use BFS with a flag to reverse levels.

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToRight = true;

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            if (!leftToRight) Collections.reverse(level);
            result.add(level);
            leftToRight = !leftToRight;
        }
        return result;
    }
}

---

5. Sliding Window & Two Pointer Patterns

Longest Substring Without Repeating Characters (Amazon, Flipkart, Atlassian)

Problem: Find the length of the longest substring without repeating characters.

Solution: Use a sliding window with a hash set.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int maxLen = 0, left = 0;

        for (int right = 0; right < s.length(); right++) {
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left++));
            }
            set.add(s.charAt(right));
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

---

Longest Subarray with Sum ≤ K (Uber, Walmart, Oracle)

Problem: Find the longest subarray with sum ≤ k.

Solution: Use a sliding window with prefix sum.

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        int sum = 0, maxLen = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                maxLen = Math.max(maxLen, i - map.get(sum - k));
            }
            map.putIfAbsent(sum, i);
        }
        return maxLen;
    }
}

---

Minimum Window Substring (Google, Amazon)

Problem: Find the smallest substring containing all characters of a pattern.

Solution: Use a sliding window with a frequency map.

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);

        int count = map.size(), left = 0, minLen = Integer.MAX_VALUE, minStart = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                if (map.get(c) == 0) count--;
            }

            while (count == 0) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }

                char leftChar = s.charAt(left);
                if (map.containsKey(leftChar)) {
                    map.put(leftChar, map.get(leftChar) + 1);
                    if (map.get(leftChar) > 0) count++;
                }
                left++;
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }
}

---

Longest Continuous Subarray with Absolute Diff ≤ Limit (Uber, Google)

Problem: Find the longest subarray where the absolute difference between any two elements is ≤ limit.

Solution: Use sliding window with two deques.

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxDeque = new LinkedList<>();
        Deque<Integer> minDeque = new LinkedList<>();
        int left = 0, maxLen = 0;

        for (int right = 0; right < nums.length; right++) {
            while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] <= nums[right]) {
                maxDeque.pollLast();
            }
            while (!minDeque.isEmpty() && nums[minDeque.peekLast()] >= nums[right]) {
                minDeque.pollLast();
            }

            maxDeque.offerLast(right);
            minDeque.offerLast(right);

            while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit) {
                if (maxDeque.peekFirst() < minDeque.peekFirst()) {
                    left = maxDeque.pollFirst() + 1;
                } else {
                    left = minDeque.pollFirst() + 1;
                }
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

---

Maximum Number of Vowels in a Substring of Given Length (Microsoft, Amazon)

Problem: Find the maximum number of vowels in a substring of length k.

Solution: Use a sliding window.

class Solution {
    public int maxVowels(String s, int k) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
        int count = 0, maxCount = 0;

        for (int i = 0; i < s.length(); i++) {
            if (vowels.contains(s.charAt(i))) count++;
            if (i >= k && vowels.contains(s.charAt(i - k))) count--;
            if (i >= k - 1) maxCount = Math.max(maxCount, count);
        }
        return maxCount;
    }
}

---

6. Hashing, Sets & Random Access

Insert Delete GetRandom O(1) (Uber, Flipkart)

Problem: Implement a data structure with O(1) insert, delete, and random access.

Solution: Use a hash map and array list.

class RandomizedSet {
    private Map<Integer, Integer> map;
    private List<Integer> list;
    private Random rand;

    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        map.put(val, list.size());
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int index = map.get(val);
        if (index < list.size() - 1) {
            int lastVal = list.get(list.size() - 1);
            list.set(index, lastVal);
            map.put(lastVal, index);
        }
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

---

Top K Frequent Elements (Amazon, Uber, Google)

Problem: Find the k most frequent elements in an array.

Solution: Use a hash map and bucket sort.

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);

        List<Integer>[] bucket = new List[nums.length + 1];
        for (int num : map.keySet()) {
            int freq = map.get(num);
            if (bucket[freq] == null) bucket[freq] = new ArrayList<>();
            bucket[freq].add(num);
        }

        int[] result = new int[k];
        int index = 0;
        for (int i = bucket.length - 1; i >= 0 && index < k; i--) {
            if (bucket[i] != null) {
                for (int num : bucket[i]) {
                    result[index++] = num;
                    if (index == k) break;
                }
            }
        }
        return result;
    }
}

---

Group Anagrams (Google, Microsoft, Amazon)

Problem: Group anagrams together from a list of strings.

Solution: Use a hash map with sorted strings as keys.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }

        return new ArrayList<>(map.values());
    }
}

---

Subarray Sum Equals K (Amazon, Flipkart)

Problem: Find the number of subarrays with sum equal to k.

Solution: Use a hash map to store prefix sums.

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0, count = 0;

        for (int num : nums) {
            sum += num;
            count += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

---

Two Sum (Amazon, Google, Walmart)

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

Solution: Use a hash map for O(1) lookup.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<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);
        }
        return new int[]{};
    }
}

---

7. Dynamic Programming & State Optimization

Coin Change (Google, Uber, Flipkart)

Problem: Find the minimum number of coins to make up an amount.

Solution: Use bottom-up dynamic programming.

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}

---

Longest Increasing Subsequence (Amazon, Microsoft, Walmart)

Problem: Find the length of the longest increasing subsequence.

Solution: Use dynamic programming with binary search.

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;

        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) i = -(i + 1);
            dp[i] = num;
            if (i == len) len++;
        }
        return len;
    }
}

---

House Robber (Uber, Google)

Problem: Maximize the amount robbed without robbing adjacent houses.

Solution: Use dynamic programming.

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}

---

Edit Distance (Amazon, Google, Oracle)

Problem: Find the minimum operations to transform one word into another.

Solution: Use dynamic programming.

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

---

Unique Paths (Microsoft, Flipkart, Uber)

Problem: Find the number of unique paths from top-left to bottom-right in a grid.

Solution: Use dynamic programming.

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

---

8. Stack & Monotonic Patterns

Daily Temperatures (Google, Walmart)

Problem: Find the number of days until a warmer day for each day.

Solution: Use a monotonic stack.

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prev = stack.pop();
                result[prev] = i - prev;
            }
            stack.push(i);
        }
        return result;
    }
}

---

Next Greater Element I (Amazon, Atlassian, Uber)

Problem: Find the next greater element for each element in nums1 from nums2.

Solution: Use a monotonic stack.

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();

        for (int num : nums2) {
            while (!stack.isEmpty() && stack.peek() < num) {
                map.put(stack.pop(), num);
            }
            stack.push(num);
        }

        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = map.getOrDefault(nums1[i], -1);
        }
        return result;
    }
}

---

Valid Parentheses (Amazon, Flipkart)

Problem: Check if a string of parentheses is valid.

Solution: Use a stack to match parentheses.

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

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

---

Largest Rectangle in Histogram (Google, Microsoft, Oracle)

Problem: Find the largest rectangle area in a histogram.

Solution: Use a monotonic stack.

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxArea = 0;

        for (int i = 0; i <= heights.length; i++) {
            int h = i == heights.length ? 0 : heights[i];
            while (stack.peek() != -1 && heights[stack.peek()] >= h) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

---

Min Stack (Amazon, Uber, Google)

Problem: Implement a stack that supports getMin() in O(1).

Solution: Use two stacks to track minimums.

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

---

This blog provides complete Java solutions for key DSA problems, optimized for clarity and interview preparation. Practice these to excel in technical interviews at top tech companies :)