📌 Blog Series: Expedia DSA Interview Patterns with Java Code

🔹 Blog 1: Strings & Arrays

• Longest Substring Without Repeating Characters (Sliding Window)
• Distinct Count in Every Window (HashMap + Sliding Window)
• Pair Sum Problems (Two Sum)

🔹 Blog 2: Dynamic Programming

• Coin Change (Min Coins)
• Minimum Path Sum in Triangle
• Partition Array for Max Sum

🔹 Blog 3: Linked Lists

• Merge Two Sorted Lists
• Add Two Numbers (Linked List representation)
• Reverse a Linked List

🔹 Blog 4: Trees & Graphs

• Vertical Traversal of Binary Tree
• Maximum Root-to-Leaf Path Sum
• Number of Islands (DFS/BFS)

🔹 Blog 5: Sliding Window & Monotonic Queue

• Sliding Window Maximum (Deque)
• Longest Subarray with Sum ≤ K
• Substrings with K distinct characters

🔹 Blog 6: Hashing & Sorting

• Remove Duplicates from Sorted Array
• Group Anagrams
• Word Frequency

🔹 Blog 7: Stacks & Queues

• Next Greater Element
• Valid Parentheses
• Trapping Rain Water

🔹 Blog 8: System Design Lite (OOP)

• LRU Cache Implementation
• Parking Lot Design (OOP)
• Autocomplete System (Trie + HashMap)

---

👉 I’ll start now with Blog 1: Strings & Arrays (Expedia’s most common category).

---

🚀 Blog 1: Strings & Arrays — Expedia DSA Patterns

🔹 Problem 1: Longest Substring Without Repeating Characters

Pattern: Sliding Window

import java.util.*;

public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0, maxLen = 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;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
    }
}

---

🔹 Problem 2: Distinct Elements in Every Sliding Window

Pattern: HashMap + Sliding Window

import java.util.*;

public class DistinctInWindow {
    public static List<Integer> countDistinct(int[] arr, int k) {
        List<Integer> result = new ArrayList<>();
        Map<Integer, Integer> freq = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {
            freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1);

            if (i >= k) {
                int remove = arr[i - k];
                freq.put(remove, freq.get(remove) - 1);
                if (freq.get(remove) == 0) freq.remove(remove);
            }

            if (i >= k - 1) result.add(freq.size());
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 1, 3, 4, 2, 3};
        System.out.println(countDistinct(arr, 4)); // [3, 4, 4, 3]
    }
}

---

🔹 Problem 3: Two Sum (Pair Sum Problem)

Pattern: Hashing

import java.util.*;

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];
            if (map.containsKey(diff)) {
                return new int[]{map.get(diff), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int[] res = twoSum(nums, 9);
        System.out.println(Arrays.toString(res)); // [0,1]
    }
}

---

✅ Summary

• Sliding Window solves substring & distinct count efficiently.
• HashMap is Expedia’s favorite for frequency & lookup problems.
• Array problems often reduce to sliding window, hashing, or two-pointer tricks.

---

👉 In Blog 2, we’ll dive into Dynamic Programming (Coin Change, Triangle Path Sum, Partitioning) — another Expedia hot topic.

---