Google

Part 1: Algorithmic Problem — Bit Manipulation & Bitwise Tries ### Base Problem: Single Number You are given a non-empty array of integers `nums`. Every element appears exactly twice, except for one element which appears exactly once. Task:** Find that single one. What is the time and space complexity of using a Hash Map or a Hash Set to track the occurrences of each number? How do you solve this in strictly $O(N)$ time and $O(1)$ auxiliary space using the Bitwise XOR (`^`) operator? Explain the fundamental mathematical properties of XOR (e.g., $A \oplus A = 0$ and $A \oplus 0 = A$) that make this approach work, regardless of the order of the numbers in the array. - ### Follow-Up 1: Single Number II (Appears Three Times) You are given an integer array `nums` where every element appears exactly **three times** except for one, which appears exactly once. Task:** Find the single element and return it. Why does the simple cumulative XOR approach completely fail when numbers appear an odd number of times (like three)? How can you solve this in $O(N)$ time and $O(1)$ space by looking at the numbers at the bit level? Explain how counting the total number of `1`s at each specific bit position (from 0 to 31) across the entire array, and taking that sum modulo 3, reconstructs the exact binary representation of the single number. - ### Follow-Up 2: Maximum XOR of Two Numbers in an Array Given an integer array `nums` of length $N$, you must find two integers in the array, `nums[i]` and `nums[j]` (where $i \le j$), such that their XOR result (`nums[i] ^ nums[j]`) is maximized. Task:** Return the maximum result of `nums[i] ^ nums[j]`. A brute-force double loop to check every pair takes $O(N^2)$ time, which is too slow. How can you utilize a **Bitwise Trie** (a prefix tree where each node only has two children: `0` and `1`) to optimize this? Explain the greedy traversal strategy: After inserting all numbers into the Trie, how do you search for the best match for a given number by always attempting to branch down the path of the *opposite* bit (to force a `1` in the XOR result) starting from the Most Significant Bit (MSB)? What is the final time complexity? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: The "Lost in the Middle" Phenomenon When developers upload a massive 100-page PDF into an AI's context window and ask a question, the AI usually remembers facts from page 1 and page 100 perfectly, but completely misses a critical fact located on page 50. What is this "Lost in the Middle" phenomenon, and why does it mean that simply having a huge context window isn't a magic solution for analyzing large datasets? - ### Question 2: Native Audio vs. Cascaded Systems Older voice assistants (like Siri or Alexa) worked in a "Cascaded" pipeline: (1) Speech-to-Text translates your voice to words, (2) an AI processes the text, (3) Text-to-Speech reads the answer. Modern models (like GPT-4o) are "Native Audio." What is the practical advantage of an AI processing the raw audio directly? (Hint: Think about human communication cues like sarcasm, breathing, background noise, or speaking speed). - ### Question 3: "Open Weights" vs. "Open Source" In traditional software, "Open Source" means you get the human-readable source code (like C++ or Python files) so you can see exactly how the program makes decisions. In the AI industry, companies often release "Open Weights" instead. Why is a massive file of billions of numbers (weights) fundamentally different from traditional open-source code? Why does having the weights still not tell you exactly *how* the AI learned a specific fact? - ### Question 4: Model Checkpoints If you read about the process of training a large AI model, you will frequently see the term **Checkpoint**. Training an LLM can take thousands of GPUs running 24/7 for three months. In plain English, what is a checkpoint in this context? Why is regularly saving checkpoints an absolute necessity when dealing with massive hardware clusters?