Flipkart

Part 1: Algorithmic Problem — Tries (Prefix Trees) & Word Matching ### Base Problem: Implement Trie (Prefix Tree) A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Task:** Implement the `Trie` class with the methods `insert(word)`, `search(word)`, and `startsWith(prefix)`. All methods should run in $O(L)$ time, where $L$ is the length of the string. If you just need to `search` for exact words, a standard Hash Set achieves $O(1)$ average lookups. Why is a Hash Set completely incapable of handling the `startsWith(prefix)` operation efficiently? How do you conceptually design a `TrieNode` object in memory? Explain why each node contains an array (or Hash Map) of children pointers and a `boolean is_end_of_word` flag. Walk through the iterative logic of `insert` and `search`: When inserting the word "APPLE", how do you traverse the tree, create new nodes for missing letters, and correctly mark the final 'E' node? - ### Follow-Up 1: Design Add and Search Words Data Structure Design a data structure that supports adding new words and finding if a string matches any previously added string. Task:** Implement the `WordDictionary` class with `addWord(word)` and `search(word)`. The `search` word may contain the dot character `'.'` to represent any one letter. (e.g., `search("b.d")` matches `"bad"`, `"bed"`, etc.). Standard Trie insertion remains unchanged. However, the `.` wildcard breaks the standard iterative search because you no longer know exactly which child pointer to follow. How do you transition your `search` function from a simple iterative loop into a **Recursive Depth-First Search (DFS)**? Explain the recursive branching logic: If the current character is a standard letter, you traverse down that single path. If the current character is `'.'`, how do you iterate through *all* currently active children of that node and recursively pass the remainder of the word to them? - ### Follow-Up 2: Word Search II Given an $M \times N$ `board` of characters and a list of strings `words`. Task:** Return all words on the board. Each word must be constructed from letters of sequentially adjacent cells (horizontally or vertically). The same letter cell may not be used more than once in a word. If you loop through the `words` list and run a separate full-board DFS for every single word, the time complexity is catastrophic ($O(W \cdot M \cdot N \cdot 4^L)$). How do you invert the problem by inserting all target `words` into a **single Trie**, and then running the DFS starting from each board cell exactly once? Explain the synergy between the Grid DFS and the Trie: At each cell in the grid, you simultaneously step down the Trie. If the Trie node doesn't have a child matching the current board letter, how does this instantly prune the DFS search path? *Advanced Optimization:** Once a word is found, why is it highly recommended to dynamically delete that word's leaf node (and potentially its parent nodes) from the Trie? How does this prevent the DFS from redundantly exploring paths for words you've already found? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Catastrophic Forgetting If a hospital takes an open-source AI and fine-tunes it extensively on thousands of complex medical textbooks, they might discover the AI has suddenly forgotten how to write computer code, or has lost its ability to converse politely. In neural network training, what is **Catastrophic Forgetting**? Why does aggressively updating the model's weights to learn new data inherently risk overwriting its previous knowledge? - ### Question 2: Model Merging (Franken-models) In the open-source AI community, developers frequently create new models by "Merging" two existing ones (e.g., combining a model highly trained in mathematics with a model highly trained in creative writing). Mind-blowingly, they do this *without* spending millions of dollars on retraining. Conceptually, how is it possible to take the mathematical average (or spherical interpolation) of two different models' weights and end up with a single, functional AI that possesses the skills of both? - ### Question 3: Sliding Window Attention The standard Transformer architecture has an $O(N^2)$ memory bottleneck: if a book is 10,000 words long, the 10,000th word must mathematically "look back" at all 9,999 previous words. To fix this, models like Mistral use **Sliding Window Attention**. Conceptually, how does restricting the AI to only look back at a fixed "window" (e.g., the last 4,000 tokens) solve the memory explosion while still allowing information from the beginning of the book to effectively ripple forward to the end? - ### Question 4: GQA (Grouped Query Attention) To generate text, an LLM must store the context of the conversation in the KV Cache (Key-Value Cache) in the GPU's memory. Older models used Multi-Head Attention, which required massive amounts of VRAM. Modern models use **Grouped Query Attention (GQA)**. Without heavy math, how does GQA save massive amounts of memory by forcing multiple "Readers" (Query heads) to share a single "Memory Bank" (Key/Value head) rather than giving every reader its own dedicated copy of the memory?