Google

## Part 1: Algorithmic Problem — Linked Lists & Fast/Slow Pointers ### Base Problem: Linked List Cycle Detection You are given the head of a singly linked list. Task:** Determine if the linked list has a cycle in it (i.e., if some node points back to a previous node). What is the naive approach using a Hash Set, and what is its space complexity? How do you implement Floyd’s Cycle-Finding Algorithm (the "Tortoise and Hare" fast/slow pointer method) to solve this in strictly $O(N)$ time and $O(1)$ auxiliary space? - ### Follow-Up 1: Find the Start of the Cycle You are given the same linked list, and you have confirmed it contains a cycle. Task:** Return the exact node where the cycle begins. After the fast pointer and slow pointer meet inside the cycle, explain the mathematical intuition behind moving one pointer back to the `head` of the list. Why does moving both pointers forward at a speed of 1 step at a time guarantee they will collide exactly at the start of the cycle? - ### Follow-Up 2: Find the Duplicate Number (Array Modeled as Linked List) You are given an array of integers `nums` containing $N + 1$ integers where each integer is in the range $[1, N]$ inclusive. There is exactly one repeated number in `nums`, but it may appear more than twice. Task:** Find this duplicate number without modifying the array and using only $O(1)$ extra space. Explain why standard approaches like sorting (modifies the array) or Hash Sets (uses $O(N)$ space) are invalid here. How can you conceptually treat the array values as "pointers" to the next index (i.e., `next_node = nums[current_node]`), allowing you to use the exact same Tortoise and Hare cycle detection algorithm to find the duplicate number? - ## Part 2: AI & LLM Core Concepts (Light / Foundational) ### Question 1: Zero-Shot vs. Few-Shot Prompting What is the difference between "zero-shot" and "few-shot" prompting? How does providing a few examples of inputs and desired outputs inside the prompt improve the LLM's reliability for formatting or classification tasks? - ### Question 2: RLHF (Reinforcement Learning from Human Feedback) In simple terms, what is RLHF? Why is this specific training step necessary to turn a raw, base AI model (which just tries to complete the next word on the internet) into a polite, helpful, and safe conversational chatbot? - ### Question 3: Stop Sequences When configuring an LLM API request, developers can define "stop sequences" (e.g., passing `"\n\n"` or `"User:"`). What exactly does a stop sequence do, and how does it prevent the model from rambling endlessly or speaking for the user? - ### Question 4: Top-P (Nucleus Sampling) Most LLM APIs feature a parameter called `top_p` alongside Temperature. In plain English, what does `top_p` do? How does it restrict the model to only choose from a dynamic "nucleus" of the most probable next words, effectively cutting off the long tail of weird, low-probability words?