Flipkart

Part 1: Algorithmic Problem — Graph Theory (Topological Sorting) ### Base Problem: Course Schedule There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [a_i, b_i]` indicates that you must take course `b_i` first if you want to take course `a_i`. Task:** Return `true` if you can finish all courses. Otherwise, return `false`. Conceptually, why does this problem perfectly map to detecting a **Cycle in a Directed Graph**? How do you implement Kahn’s Algorithm (BFS) using an `in_degree` array? What does an `in_degree` of exactly `0` conceptually mean for a course? Walk through the BFS queue logic: When you pop a course with an `in_degree` of `0` and "take" it, how do you update the `in_degree` of its neighboring courses? How does checking the total number of processed courses at the end immediately tell you if a cycle exists? - ### Follow-Up 1: Course Schedule II (Return the Order) You are given the exact same `numCourses` and `prerequisites` array. Task:** Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array. Using Kahn's Algorithm, modifying the previous solution is trivial (you just append the popped nodes to an array). However, how do you solve this using **Depth-First Search (DFS)** instead? Explain why a simple `visited` boolean array is insufficient for DFS cycle detection in a directed graph. How do you use a 3-state visited array (`UNVISITED`, `VISITING`, `VISITED`) to detect back-edges (cycles)? When a node transitions from `VISITING` to `VISITED`, why is that the exact moment it must be appended to your topological output array? - ### Follow-Up 2: Alien Dictionary There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you. You are given a list of strings `words` from the alien language's dictionary, where the strings in `words` are sorted lexicographically by the rules of this new language. Task:** Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no valid ordering, return `""`. You are not explicitly given the graph edges here; you must deduce them. How do you extract the directed edges by comparing exactly two adjacent words in the array at a time? Explain why looking only at the *first* differing character between `words[i]` and `words[i+1]` gives you exactly one valid directed edge, and why subsequent characters in those two words must be ignored. What is the edge case involving prefix lengths? (e.g., if `words[i] = "abcd"` and `words[i+1] = "abc"`, why does this instantly invalidate the entire dictionary?) Once the adjacency list and `in_degree` map of unique characters are built, how do you apply standard Topological Sort to return the final alphabet string? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: The "Alignment Tax" When AI companies take a base model and apply heavy safety training (RLHF) to ensure it refuses to write malware or use hate speech, researchers often measure an **"Alignment Tax."** In plain English, what does this term mean? Why does forcing a model to become overly "safe" and polite frequently degrade its ability to write complex Python code or solve intricate logic puzzles? - ### Question 2: Chain of Thought (CoT) Mechanics If you ask an LLM a complex math question, it might answer incorrectly. If you append the phrase *"Let's think step by step,"* the model often gets the right answer. We know this is called Chain of Thought (CoT). But mechanically, *why* does this work? (Hint: An LLM generates text one token at a time and cannot "backtrack." How does generating intermediate text physically serve as temporary scratchpad memory for the AI's math?) - ### Question 3: Train/Test Contamination (Data Leakage) Every time a new AI model drops, the creators boast that it scored 95% on coding and law exams. However, independent researchers are increasingly skeptical due to **Train/Test Contamination**. Conceptually, what is this contamination? If a company trains its model by indiscriminately scraping the entire internet, why does a 95% score on the LSAT benchmark not actually prove the AI is capable of complex legal reasoning? - ### Question 4: Apple Silicon & Unified Memory (Hardware) Running a massive open-source model (like a 70B parameter LLM) locally usually requires incredibly expensive enterprise Nvidia graphics cards because the model needs 140+ GB of VRAM. Yet, developers routinely run these massive models on standard Apple Mac Studios or high-end MacBook Pros. What is **Unified Memory Architecture (UMA)**? How does Apple's unique hardware design bypass the traditional VRAM bottleneck that plagues Windows/Linux PCs?