Google

## Part 1: Algorithmic Problem — Priority Queues & Heaps ### Base Problem: Kth Largest Element in an Array You are given an integer array `nums` and an integer `k`. Task:** Return the `k`-th largest element in the array. Note that it is the `k`-th largest element in the sorted order, not the `k`-th distinct element. What is the time complexity of simply sorting the array and returning the element at index `N - k`? How do you implement a **Min-Heap** (Priority Queue) of size `k` to solve this problem efficiently? Why does limiting the heap size to `k` yield a time complexity of $O(N \log K)$ and space complexity of $O(K)$? (Bonus)* How does the **QuickSelect** algorithm (using a pivot, similar to QuickSort) solve this in $O(N)$ *average* time but $O(N^2)$ worst-case time? - ### Follow-Up 1: Merge K Sorted Lists You are given an array of `k` linked lists, where each linked list is sorted in ascending order. Task:** Merge all the linked lists into one sorted linked list and return it. Why does repeatedly merging lists two at a time sequentially take $O(N \cdot K)$ time (where $N$ is the total number of nodes)? How do you use a **Min-Heap** to keep track of the smallest current node across all `k` lists? Explain how initializing the heap with the `head` of each list, and pushing the `next` node into the heap every time you pop the minimum, solves this in strictly $O(N \log K)$ time and $O(K)$ space. - ### Follow-Up 2: Find Median from Data Stream You are designing a system that receives a continuous stream of integers. At any given time, you need to be able to output the median of all the numbers seen so far. Task:** Design a data structure that supports `addNum(int num)` and `findMedian()`. If you maintain a sorted array, inserting a new number takes $O(N)$ time. How do you use **Two Heaps** (a Max-Heap for the lower half of the numbers, and a Min-Heap for the upper half) to drastically optimize this? Explain the balancing logic required when calling `addNum()` to ensure the size difference between the two heaps never exceeds $1$. What are the resulting time complexities for `addNum()` and `findMedian()` using the two-heap approach? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Generative AI vs. Discriminative (Predictive) AI In plain English, what is the fundamental difference between a **Generative AI** model (like ChatGPT or Midjourney) and a traditional **Discriminative AI** model (like an email spam filter or a system that tags photos of cats)? - ### Question 2: The "Attention" Mechanism The "T" in ChatGPT stands for Transformer, an architecture famous for its "Self-Attention" mechanism. Without using heavy math, what does "Attention" actually mean when an AI is reading a sentence? How does it help the model understand that the word "bank" means something different in "river bank" versus "bank account"? - ### Question 3: Why do AI models need GPUs instead of CPUs? If you try to run a large language model on a standard desktop CPU, it generates words extremely slowly. However, running it on a GPU (Graphics Processing Unit) is blazingly fast. Why are GPUs, which were originally designed for rendering video games, so much better at running neural networks than CPUs? - ### Question 4: Overfitting vs. Generalization In machine learning, what does it mean if a model suffers from **Overfitting**? Why is it a major problem if an AI model perfectly "memorizes" all the answers to its training data, rather than learning the underlying patterns?