Flipkart

Part 1: Algorithmic Problem — Sliding Windows & Monotonic Deques ### Base Problem: Sliding Window Maximum You are given an array of integers `nums`. There is a sliding window of size `k` which is moving from the very left of the array to the very right. You can only see the `k` numbers in the window. Each time the sliding window moves right by one position. Task:** Return an array containing the maximum element of each sliding window. Why does a naive approach (scanning the `k` elements for every window shift) result in an $O(N \cdot K)$ time complexity? How do you implement a **Monotonic Decreasing Deque** (Double-Ended Queue) to solve this in strictly $O(N)$ time? Explain the deque logic: When a new element enters the window, why is it safe to pop all smaller elements from the back of the deque? How do you use the indices stored in the deque to know when an element has "expired" and must be popped from the front? - ### Follow-Up 1: Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit Given an array of integers `nums` and an integer `limit`. Task:** Return the size of the longest non-empty subarray such that the absolute difference between any two elements in this subarray is less than or equal to `limit`. In a standard sliding window (Two Pointers), you need to know the absolute maximum and minimum values currently inside the window to check the condition `max_val - min_val <= limit`. Since the window expands and shrinks dynamically, how can you use **Two Monotonic Deques** (one strictly decreasing to track the maximums, and one strictly increasing to track the minimums) simultaneously? Walk through the logic: When the limit condition is violated, how do you shrink the window from the `left` pointer and update both deques accordingly in $O(1)$ amortized time? - ### Follow-Up 2: Shortest Subarray with Sum at Least K Given an integer array `nums` and an integer `k`. Task:** Return the length of the shortest non-empty subarray of `nums` with a sum of at least `k`. If there is no such subarray, return `-1`. (Crucial Detail: The array `nums` can contain negative numbers).* Why does the standard two-pointer sliding window approach (like in "Minimum Size Subarray Sum") completely fail when negative numbers are introduced? (Hint: The running sum is no longer monotonically increasing). How do you construct a **Prefix Sum Array** and then use a **Monotonic Increasing Deque** to evaluate it? Explain the two core rules of the deque: Why do you pop from the *front* to find a valid subarray length? Why do you pop from the *back* to maintain the increasing order of prefix sums, effectively throwing away "useless" starting points? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Tokenizing Numbers and Math If you ask an LLM to multiply `4829 * 9183`, it might get the math completely wrong, even though it can write a complex Python script perfectly. From a mechanical perspective, why do LLMs struggle so much with basic arithmetic? (Hint: Think about how a tokenizer might unpredictably chop up the number `4829` into weird chunks like `48` and `29` rather than treating it as individual digits). - ### Question 2: The KV Cache (Memory Growth) When you ask an AI to write a very long story, the generation starts fast but might slow down slightly toward the end. More importantly, the AI consumes more and more RAM on the cloud servers for every single new word it types. In plain English, what is the **KV Cache**? Why does the model need to physically store a mathematical memory of *every previous word* just to guess the next one? - ### Question 3: Rate Limits (TPM vs. RPM) When building software with commercial AI APIs, you are restricted by two main limits: **RPM** (Requests Per Minute) and **TPM** (Tokens Per Minute). In traditional web servers, usually only Requests Per Minute matter. Why is TPM so critically important for AI servers? Why would a single user asking for a 10-page essay strain the server more than 50 users asking for a 1-sentence joke? - ### Question 4: Greedy Decoding vs. Beam Search When an AI model predicts the next word, it assigns a probability to every word in its vocabulary. *Greedy Decoding:** Always picking the #1 most probable next word immediately. *Beam Search:** Looking a few words ahead to see which *sequence* of words has the highest overall probability. In plain English, why might Greedy Decoding paint the AI into a corner and produce a weird sentence? Why is looking ahead (Beam Search) fundamentally better for generating high-quality text?