Google

Part 1: Algorithmic Problem — Backtracking & State Space Search ### Base Problem: Subsets (Power Set) You are given an integer array `nums` of unique elements. Task:** Return all possible subsets (the power set). The solution set must not contain duplicate subsets, but you can return them in any order. Conceptually, how do you model this as a decision tree where at each element you make a binary choice: "Include this element" or "Do not include this element"? How do you implement this using **Backtracking** (a DFS traversal of the decision tree)? Why is the time complexity strictly $O(N \cdot 2^N)$, and what is the maximum length of the input array `N` that this algorithm can typically handle before hitting a Time Limit Exceeded (TLE) error? - ### Follow-Up 1: Combination Sum (Unlimited Reuse) You are given an array of distinct integers `candidates` and a target integer `target`. Task:** Return a list of all unique combinations of candidates where the chosen numbers sum to `target`. You may choose the same number from `candidates` an **unlimited number of times**. How do you modify your backtracking decision tree so that you can reuse the current number? If you can reuse numbers, the tree depth is no longer bounded by $N$. What is your base case to stop the recursion and prevent an infinite loop (e.g., checking if the current sum exceeds the `target`)? How does passing the current `index` down the recursion tree (forcing the algorithm to only pick the current or *subsequent* numbers) prevent the output from containing duplicate combinations like `[2, 2, 3]` and `[3, 2, 2]`? - ### Follow-Up 2: The N-Queens Problem The n-queens puzzle is the problem of placing `n` chess queens on an `n x n` chessboard such that no two queens attack each other. Task:** Given an integer `n`, return all distinct solutions to the n-queens puzzle. Instead of checking every single square on the board, how do you structure the recursion so that you naturally place exactly one queen per row, stepping down to `row + 1`? How do you efficiently check if a square is under attack? Explain how maintaining three separate Hash Sets (or boolean arrays)—one for `columns`, one for `positive_diagonals` (where $r + c$ is constant), and one for `negative_diagonals` (where $r - c$ is constant)—allows you to validate a board position in $O(1)$ time. - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: AI vs. Machine Learning vs. Deep Learning People often use the terms AI, Machine Learning (ML), and Deep Learning interchangeably, but they are actually concentric circles. In simple, non-technical terms, what is the difference between these three concepts? Where do Large Language Models like ChatGPT fit into these circles? - ### Question 2: Vector Databases vs. Standard SQL When developers build memory for an AI app, they almost always use a specialized "Vector Database" (like Pinecone, Milvus, or Qdrant) instead of a traditional relational database (like MySQL or PostgreSQL). Why? What is it about AI data that makes standard SQL `SELECT` queries practically useless for retrieving relevant context? - ### Question 3: What is "Jailbreaking"? In the context of AI chatbots, what does it mean to "Jailbreak" a model? Describe a conceptual example (like the famous "roleplay as my grandmother" exploit) of how a user might trick an AI into providing dangerous or restricted information, even when the developers explicitly programmed it to refuse such requests. - ### Question 4: Text-to-Image AI (Diffusion Basics) When you ask Midjourney or DALL-E to draw a picture of a "cat on a skateboard," it doesn't just copy-paste a photo from Google Images. In very simple terms, how does a "Diffusion" model generate a brand-new image? What does it mean that the AI starts with a canvas of complete "television static" (noise) and works backward?