Google

## Part 1: Algorithmic Problem — Binary Search ### Base Problem: Standard Binary Search You are given an array of integers `nums` which is sorted in ascending order, and an integer `target`. Task:** Write a function to search `target` in `nums`. If `target` exists, then return its index. Otherwise, return `-1`. What is the linear time ($O(N)$) brute-force approach? How do you implement a **Binary Search** using two pointers (`left` and `right`) to find the target in strictly $O(\log N)$ time and $O(1)$ space? How do you calculate the `mid` pointer safely to avoid integer overflow in strongly typed languages like C++ or Java? - ### Follow-Up 1: First and Last Position (Lower/Upper Bound) The sorted array `nums` can now contain duplicate elements (e.g., `[5, 7, 7, 8, 8, 10]`). Task:** Find the starting and ending position of a given `target` value. If it is not found, return `[-1, -1]`. A standard binary search will find *a* target, but not necessarily the boundaries. How do you modify the binary search algorithm to find the **lower bound** (first occurrence)? How do you perform a second modified binary search to find the **upper bound** (last occurrence) while keeping the total time complexity strictly $O(\log N)$? - ### Follow-Up 2: Binary Search on Answer (Koko Eating Bananas) Koko loves to eat bananas. There are $N$ piles of bananas, where the $i$-th pile has `piles[i]` bananas. The guards have gone and will come back in `H` hours. Koko can decide her bananas-per-hour eating speed of `K`. Each hour, she chooses some pile and eats `K` bananas from that pile. If the pile has less than `K` bananas, she eats all of them and will not eat any more bananas during this hour. Task:** Find the minimum integer `K` such that she can eat all the bananas within `H` hours. Explain why this problem cannot be solved with a standard greedy array traversal. How do you conceptually treat the *eating speed* `K` as a sorted array of possible answers (from $1$ to the maximum pile size)? How do you apply **Binary Search on the Answer** to find the minimum valid `K` in strictly $O(N \log M)$ time (where $M$ is the maximum number of bananas in a single pile)? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Chatbot "Memory" When you talk to ChatGPT or Gemini, it remembers what you said three messages ago. However, the underlying Large Language Model is entirely "stateless" (it has no internal database of who you are or what you just said). How do developers trick the AI into "remembering" the context of a continuous conversation? - ### Question 2: What are "Parameters"? You often hear that an open-source model has "8 Billion parameters" (like Llama-3-8B). In plain English, what exactly is a parameter? Think about how the neural network learns to connect words and concepts—what do these billions of numbers actually represent in the software? - ### Question 3: Pre-training vs. Fine-Tuning Training an AI like ChatGPT happens in two major phases. First is **Pre-training** (reading the entire public internet). Second is **Fine-Tuning** (or Instruction Tuning). Why is the second step absolutely necessary? What would happen if you tried to chat with an AI that had *only* finished the Pre-training phase? - ### Question 4: Open Weights vs. Closed APIs From a software developer's perspective, what is the practical difference between building an app using an **API Model** (like OpenAI's GPT-4 or Google's Gemini) versus using an **Open Weights Model** (like Meta's Llama 3 or Mistral)? Consider aspects like data privacy, internet connectivity, and hardware costs.