Flipkart

Part 1: Algorithmic Problem — Bitmask Dynamic Programming & State Space ### Base Problem: Shortest Path Visiting All Nodes You have an undirected, connected graph of `n` nodes labeled from `0` to `n - 1`. You are given an array `graph` where `graph[i]` is a list of all the nodes connected with node `i` by an edge. Task:** Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges. A standard Breadth-First Search (BFS) uses a 1D `visited` array (or Hash Set) to prevent infinite loops, but since this problem *allows* revisiting nodes to reach unvisited ones, a 1D array instantly fails. Why? How do you use an integer **Bitmask** to perfectly represent the exact combination of nodes you have visited so far (e.g., how does the integer `13` mathematically represent visiting nodes 0, 2, and 3)? Explain the modified BFS queue and state tracking: Your queue will now store tuples of `(current_node, visited_bitmask)`. Why does this expanded 2D state space (`visited[node][mask]`) correctly prevent infinite loops while still allowing you to revisit a node if it unlocks a new part of the graph? What is the exact bitwise $O(1)$ operation to check if all `n` nodes have been visited, immediately terminating the BFS? - ### Follow-Up 1: Find the Shortest Superstring Given an array of strings `words`. Task:** Return the smallest string that contains each string in `words` as a substring. If there are multiple valid strings of the smallest length, return any of them. Since $N \le 12$, you must explore permutations of how these words chain together, but calculating string overlaps repeatedly is incredibly slow. How do you precompute a 2D $O(N^2)$ adjacency matrix `overlap[i][j]` that stores the exact number of characters you save by appending `words[j]` directly after `words[i]`? This is the Travelling Salesperson Problem (TSP) in disguise. Define your 2D Dynamic Programming state `dp[mask][i]`. What does the `mask` represent, and why is it absolutely critical to track `i` (the index of the *last* string appended in that subset)? Walk through the state transition: If you are at `dp[mask][i]`, and you want to transition to a new unvisited string `j`, what bitwise operation adds `j` to the `mask`, and how do you update the maximum overlap using `overlap[i][j]`? To actually return the string (not just the minimum length), you cannot just return an integer from your DP matrix. How do you maintain a `parent[mask][i]` array to trace the optimal path backward once the DP is complete? - ### Follow-Up 2: Maximum Students Taking Exam (Grid Bitmask DP) Given an $M \times N$ matrix `seats` that represents a classroom, where `'#'` means a broken seat and `'.'` means an empty seat. Students cannot sit adjacent to each other (left, right, upper-left, or upper-right) to prevent cheating. Task:** Return the maximum number of students that can take the exam together. Because the grid width $N$ is very small (e.g., $N \le 8$), you can represent the seating arrangement of an entire row as a single bitmask. How does generating all possible $2^N$ bitmasks for a row allow you to compress the DP state down to just `dp[row][mask]`? Explain the row-level validity checks using bitwise operators: How does `(mask & broken_seats_mask) == 0` guarantee no student is sitting in a broken chair? How does `(mask & (mask >> 1)) == 0` mathematically guarantee that absolutely no two students are sitting horizontally adjacent in that specific row? Walk through the inter-row transition: When comparing the valid seating `mask` of row `i` against a valid `prev_mask` of row `i-1`, what exact bit shifts (e.g., `prev_mask >> 1`, `prev_mask << 1`) are required to ensure no diagonal cheating occurs before you add the number of set bits (students) to your DP sum? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Direct Preference Optimization (DPO) For years, the gold standard for aligning an AI to human preferences was RLHF (using PPO), which required building a massive, separate "Reward Model" just to score the AI's behavior. Recently, the industry largely shifted to **DPO (Direct Preference Optimization)**. Conceptually, how does DPO mathematically bypass the need for a separate Reward Model? How does it update the LLM's weights directly by contrasting a "chosen" response against a "rejected" response? - ### Question 2: State Space Models (e.g., Mamba) The Transformer architecture has dominated AI since 2017, but it suffers from a quadratic $O(N^2)$ memory bottleneck because every word must mathematically attend to every previous word. New architectures like **State Space Models (SSMs)** (such as Mamba) are gaining traction. Without heavy math, how do SSMs process text sequentially and compress the context into a fixed-size hidden state (similar to classic RNNs), achieving strictly linear $O(N)$ scaling for near-infinite context windows? - ### Question 3: Chunked Prefill (Inference Optimization) In a production AI server, inference happens in two phases: the "Prefill" phase (reading the user's massive prompt) and the "Decode" phase (generating new words one by one). If User A submits a massive 100,000-token prompt, the GPU historically locked up completely to process it, freezing User B's mid-sentence generation. Conceptually, how does **Chunked Prefill** solve this by slicing User A's prompt into pieces and intertwining them with User B's generation steps? - ### Question 4: Contrastive Decoding To reduce hallucinations and force deeper logical reasoning during inference, researchers sometimes employ **Contrastive Decoding**. This involves running a massive, highly capable model and a tiny, much weaker model simultaneously on the same prompt. Conceptually, how does subtracting the probability distribution of the weak model from the strong model dynamically boost factual, highly intelligent tokens while suppressing the generic, cliché phrasing that smaller models default to?