Flipkart

Part 1: Algorithmic Problem — Eulerian Paths & Circuits (Hierholzer's Algorithm) ### Base Problem: Reconstruct Itinerary You are given a list of airline `tickets` where `tickets[i] = [from_i, to_i]` represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from `"JFK"`, thus, the itinerary must begin with `"JFK"`. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. A naive Backtracking DFS explores a path and backtracks if it hits a dead end, resulting in an exponential $O(V^E)$ time complexity. Why is this problem actually asking you to find an **Eulerian Path** in a directed graph, which guarantees an $O(E \log E)$ solution? To handle the lexicographical requirement, how do you structure your adjacency list using a Hash Map of Priority Queues (or sorted arrays) instead of standard lists? Explain the magic of **Hierholzer's Algorithm**. Starting from `"JFK"`, you recursively visit neighbors. Why is it absolutely critical that you only append the current airport to your final itinerary array *after* the recursive loop for all its outgoing flights has completely finished (Post-Order Traversal)? Once the DFS completes, your itinerary array is built in reverse. Why does simply reversing the final array perfectly reconstruct the valid path without ever needing to manually backtrack? -- ### Follow-Up 1: Valid Arrangement of Pairs You are given a 2D integer array `pairs` where `pairs[i] = [start_i, end_i]`. An arrangement of `pairs` is valid if for every index `i` from `0` to `n - 2`, the `end_i` of the current pair equals the `start_{i+1}` of the next pair. *Task:** Return any valid arrangement of pairs. You are guaranteed that at least one valid arrangement exists. Unlike the Base Problem where you are explicitly told to start at `"JFK"`, here you must mathematically deduce the starting node. How do you use the `in_degree` and `out_degree` of every node to find the exact starting point of the Eulerian Path? What is the strict mathematical condition for the starting node of an Eulerian Path in a directed graph? (Hint: compare `out_degree` and `in_degree`). If all nodes have perfectly equal in and out degrees, what does that imply about the graph, and where can you start? Once the starting node is identified, how do you apply the exact same Post-Order DFS (Hierholzer's) from the Base Problem? Since you are returning pairs rather than a list of nodes, how do you format the output as you backtrack up the recursion stack? -- ### Follow-Up 2: Cracking the Safe (De Bruijn Sequence) There is a safe protected by a password. The password is a sequence of `n` digits where each digit can be one of the first `k` digits `0, 1, ..., k-1`. While entering a password, the last `n` digits entered will automatically be matched against the correct password. (For example, if the password is `"345"`, you can open it by typing `"012345"`). *Task:** Return any password of minimum length that is guaranteed to open the safe at some point of entering it. To guarantee opening the safe, your string must contain every possible permutation of length `n`. A naive concatenation yields a string of length $k^n \cdot n$. How does modeling this as a **De Bruijn Sequence** compress the length to exactly $k^n + n - 1$? Structurally, how do you map this to a graph where the nodes represent all possible prefixes of length `n - 1`, and the directed edges represent the `k` possible exact digits you can append? Because every node has exactly `k` incoming edges and `k` outgoing edges, this graph is mathematically guaranteed to contain an **Eulerian Circuit**. Walk through the DFS implementation: Starting from a node like `"00...0"`, you append a digit, transition to the new `n - 1` length suffix, and recurse. Why does appending the edge transition digit to your result string only *after* the recursive call guarantee the most optimally compressed overlapping string? -- ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Speculative Decoding (Inference Speedup) Generating text token-by-token using a massive 70-Billion parameter model is inherently slow because of the memory bandwidth required to load the model for every single step. Conceptually, how does **Speculative Decoding** use a tiny, lightning-fast "Draft" model (e.g., 1-Billion parameters) to rapidly guess the next 5 tokens, and then use the massive 70B model to verify all 5 guesses simultaneously in a single, highly parallel mathematical step? -- ### Question 2: ReAct Prompting (Reasoning + Acting) When building AI agents to perform complex workflows (like booking flights or executing SQL queries), developers heavily rely on the **ReAct** (Reasoning and Acting) framework. Conceptually, why is forcing the LLM to physically print a "Thought" (e.g., *"I need to check the database schema first"*) before printing an "Action" (e.g., ``) absolutely critical for preventing the AI from hallucinating APIs or getting stuck in an infinite failure loop? -- ### Question 3: GGUF Format & CPU Inference Historically, running deep learning models required saving weights as PyTorch `.bin` or `.safetensors` files, which had to be loaded entirely into expensive GPU VRAM. Today, open-source developers running local models on MacBooks almost exclusively use the **GGUF** format. In plain English, how does GGUF leverage OS-level `mmap` (memory mapping) to seamlessly stream weights directly from the SSD and CPU RAM, allowing consumer hardware to run models that technically exceed their unified memory limits? -- ### Question 4: ORPO (Odds Ratio Preference Optimization) In the progression of AI alignment algorithms, RLHF required a Reward Model, and DPO eliminated the Reward Model but still required a "Reference Model" (doubling the GPU memory required during training). Recently, **ORPO** has gained massive popularity. Conceptually, how does ORPO completely eliminate the need for a Reference Model by calculating an "Odds Ratio" penalty that dynamically suppresses the probability of rejected answers during the standard Supervised Fine-Tuning (SFT) phase?