Flipkart

PART 1: ALGORITHMIC PROBLEM - SLIDING WINDOW MEDIAN BASE PROBLEM You are processing a stream of sensor data. You are given an array of integers nums and an integer k. 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: Design an algorithm to return the median array for each window in the original array. Discuss the data structures required to achieve an efficient time complexity (better than O(N * K log K)). How would you use a combination of a Max-Heap and a Min-Heap (or a Balanced Binary Search Tree) to keep track of the moving median in O(N log K) time? FOLLOW-UP 1 The data is no longer a static array, but a continuous, real-time data stream. You need to implement a class with addNum(num) and getMedian(). Furthermore, sensor data can occasionally be flagged as faulty retroactively. You must implement a removeNum(num) function that can instantly delete a specific value that is currently somewhere in your window, even if it wasn't the oldest number. Task: Modifying a standard Priority Queue (Heap) to remove arbitrary elements takes O(K) time. How do you implement "lazy deletion" or use alternative structures like a TreeMap/SkipList to ensure removeNum remains highly efficient (O(log K))? FOLLOW-UP 2 This algorithm is being deployed in a high-frequency trading system. You are receiving millions of price ticks per second. A single machine's CPU cannot process the heap insertions and deletions fast enough. Task: If you are forced to distribute this stream across multiple servers, or if you must process the median much faster than O(log K) per element, how would you approach it? Discuss techniques for approximating the median at massive scale, such as using Buckets/Histograms (if the price ranges are fixed) or streaming algorithms like T-Digest. PART 2: AI DISCUSSION & TERMINOLOGY Practical Application & Code Review: If you use an LLM to automatically review pull requests in your CI/CD pipeline, how do you handle the risk of the AI generating confident but incorrect suggestions ("nitpicking" hallucinations), and how should developers interact with these automated reviews? General Knowledge: What are "Emergent Abilities" in Large Language Models? Why do researchers find it surprising when a model suddenly learns how to do arithmetic or translate languages when it was only explicitly trained to predict the next word? Basic Terminologies (Briefly explain the following concepts): PEFT (Parameter-Efficient Fine-Tuning): A broad category of techniques (like LoRA) used to adapt a massive, pre-trained AI model to a specific task without retraining all of its billions of parameters, drastically saving compute resources and memory. Reward Model: A crucial component in RLHF (Reinforcement Learning from Human Feedback). It is a secondary AI model trained specifically to score how "good" or "helpful" the primary AI's responses are, acting as an automated judge during the training process. BLEU / ROUGE Scores: Traditional mathematical metrics used to evaluate AI output (especially in translation and summarization) by comparing the AI's generated text against a human-written reference text and counting the overlapping words or phrases. Semantic Chunking: When preparing documents for a vector database (RAG), standard chunking just cuts the text every 500 words. Semantic chunking uses AI to intelligently break the document apart at natural boundaries (like paragraphs or topic changes) so that each chunk contains a complete, isolated thought.