Advanced Interview Patterns

# CHAPTER 17

Advanced Interview Patterns #

1. Chapter Introduction #

2. Pattern 1: The Trie (Prefix Tree) #

*The Node Structure:*

class TrieNode:
    def __init__(self):
        self.children = {} # Maps char -> TrieNode
        self.is_end_of_word = False

*Implementation (Insert):*

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        curr = self.root
        for char in word:
            if char not in curr.children:
                curr.children[char] = TrieNode()
            curr = curr.children[char]
        curr.is_end_of_word = True # Mark the end of the word

*Time Complexity:* Inserting or searching for a word takes O(L) Time, where L is the length of the word. This is incredibly fast (independent of how many millions of words are in the dictionary).

3. Pattern 2: Union Find (Disjoint Set) #

*Implementation (With Path Compression):*

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]

    def find(self, i):
        # Path Compression: Point node directly to absolute root
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            self.parent[root_i] = root_j # Connect them

*Time Complexity:* With path compression, operations are essentially O(1) (Inverse Ackermann function).

4. Pattern 3: Bit Manipulation #

*Key Operators:*

• & (AND): 1 & 1 = 1, else 0. Used to mask bits.

• | (OR): 0 | 0 = 0, else 1.

• ^ (XOR): 1 ^ 0 = 1, 1 ^ 1 = 0. (Returns 1 if bits are DIFFERENT).

• << (Left Shift): 0010 << 1 becomes 0100. (Effectively multiplies by 2).

*The XOR Trick (Single Number Problem):* *Prompt:* Given an array where every element appears twice except for one. Find that single one. (LeetCode 136). *Rule:* A ^ A = 0 (XORing a number by itself cancels it out). *Rule:* A ^ 0 = A. *Solution:* XOR every number in the array together. All duplicates will cancel each other out to 0. The only remaining binary value will be the single number!

def singleNumber(nums):
    res = 0
    for num in nums:
        res ^= num
    return res
# Time: O(N), Space: O(1)

5. Real-World Scenario: Network Routing #

6. Mini Project: Implement Trie Search #

    def search(self, word):
        curr = self.root
        for char in word:
            if char not in curr.children:
                return False
            curr = curr.children[char]
        return curr.is_end_of_word # Must be a complete word

    def startsWith(self, prefix):
        curr = self.root
        for char in prefix:
            if char not in curr.children:
                return False
            curr = curr.children[char]
        return True # Doesn't need to be complete word

7. Common Mistakes #

• Trie Memory Overhead: Tries are extremely fast, but they consume massive amounts of Space (RAM) because every single character is wrapped in a dedicated Node object with its own Hash Map. Mention this tradeoff in interviews.

• Forgetting isendofword: If you insert "APPLE" into a Trie, and then search for "APP", the path exists, but it is NOT a valid word in the dictionary. Checking the boolean flag is mandatory.

14. Interview Questions #

• Q: "Design a data structure that supports adding new words and finding if a string matches any previously added string. The search string can contain dots . where dots can be matched with any letter." (LeetCode 211. Hint: Use a Trie with recursive DFS).

15. FAQs #

• Q: Do I really need to know Union Find?

16. Summary #

17. Next Chapter Recommendation #