Google

## Part 1: Algorithmic Problem — Greedy Algorithms & Intervals ### Base Problem: Merge Intervals Given an array of `intervals` where `intervals[i] = [start_i, end_i]`, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input. Why is sorting the intervals based on the `start` time the absolutely critical first step for this algorithm? What does it mathematically guarantee about any potential overlaps as you iterate from left to right? Explain the $O(N \log N)$ logic. Once sorted, as you iterate through the intervals, how do you compare the `end` time of the last interval currently in your output array with the `start` time of the current interval to determine if a merge is required? When merging two overlapping intervals, why must the new `end` time be the `max(current_end, new_end)` rather than just taking `new_end`? (Hint: Consider an interval that is completely enveloped by another, like `[1, 10]` and `[2, 5]`). - ### Follow-Up 1: Insert Interval You are given an array of non-overlapping intervals `intervals` where `intervals[i] = [start_i, end_i]` represent the start and the end of the $i$-th interval, and `intervals` is sorted in ascending order by `start_i`. You are also given an interval `newInterval = [start, end]`. Task:** Insert `newInterval` into `intervals` such that `intervals` is still sorted in ascending order by `start_i` and still does not have any overlapping intervals (merge overlapping intervals if necessary). Since the input array is *already* sorted, doing a standard insert and re-sorting the whole array takes $O(N \log N)$ time. How do you solve this in strictly $O(N)$ time in a single pass? Explain the three distinct phases of the $O(N)$ sweep: (1) Adding strictly non-overlapping intervals *before* the new interval, (2) Merging all overlapping intervals into a single "mega-interval", and (3) Adding all strictly non-overlapping intervals *after*. What is the exact mathematical condition that proves a current interval belongs to Phase 1, and what specific condition triggers the transition to Phase 3? - ### Follow-Up 2: Minimum Number of Arrows to Burst Balloons There are some spherical balloons taped onto a flat wall that represents the XY-plane. You are given a 2D integer array `points` where `points[i] = [x_start, x_end]` denotes the horizontal diameter of the $i$-th balloon. Arrows can be shot up vertically from the x-axis. A balloon is burst if an arrow is shot between `x_start` and `x_end` (inclusive). Task:** Return the minimum number of arrows that must be shot to burst all balloons. This is mathematically identical to finding the maximum number of *non-overlapping* intervals. Why does sorting the balloons by their `end` time (instead of their `start` time) provide a massive greedy advantage for this specific problem? Explain the Greedy Choice Property: If you sort by `end` time and shoot your first arrow at the exact `end` coordinate of the very first balloon, why are you mathematically guaranteed to pop the maximum possible number of overlapping balloons with that single arrow? Walk through the single-pass $O(N)$ traversal. How do you use a single integer variable `current_arrow_position` to track when you are forced to spend a new arrow? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Evaluation (BLEU/ROUGE vs. LLM-as-a-Judge) Historically, NLP models translating text or summarizing documents were evaluated using metrics like BLEU or ROUGE, which essentially just counted overlapping words between the AI's output and a human-written reference. Why are these traditional metrics completely useless for evaluating modern LLMs? Why do AI companies now heavily rely on "LLM-as-a-Judge" (using GPT-4 to grade another model) to score their new models? - ### Question 2: Base Models vs. Instruct/Chat Models When downloading an open-source model like Llama-3, developers must choose between the "Base" model and the "Instruct" (or Chat) model. If both models have the exact same 8 Billion parameters and read the exact same terabytes of internet data during pre-training, what is the fundamental difference in how they will respond to a prompt like *"Write a poem about a cat"*? - ### Question 3: Chinchilla Scaling Laws (Compute-Optimal Training) In 2022, DeepMind published the famous "Chinchilla Scaling Laws," which completely changed how companies train AI. Before this, companies assumed that simply building models with more parameters (e.g., jumping from 100 Billion to 500 Billion parameters) was the best way to increase intelligence. In plain English, what did the Chinchilla paper mathematically prove about the required ratio between model size (parameters) and training data (tokens)? - ### Question 4: Generation Parameters (Repetition Penalty) When configuring an AI API, developers can tweak generation parameters like `presence_penalty`, `frequency_penalty`, or `repetition_penalty`. Mechanically, how do these settings alter the output logits (probabilities) of the AI during text generation? If a developer sets the `repetition_penalty` extremely high to prevent the AI from looping, what strange or broken behavior will the AI inevitably start exhibiting when writing long paragraphs?