Microsoft

## Part 1: Algorithmic Problem — Binary Trees & Tree Traversal ### Base Problem: Lowest Common Ancestor (LCA) of a Binary Search Tree (BST) You are given a Binary Search Tree (BST) and two nodes, `p` and `q`, that exist in the tree. Task:** Find the Lowest Common Ancestor (LCA) of `p` and `q`. The LCA is defined as the lowest node in the tree that has both `p` and `q` as descendants (where a node can be a descendant of itself). How do you utilize the fundamental property of a BST (where all left descendants are smaller than the root, and right descendants are larger) to find the LCA? How do you implement this iteratively to achieve strictly $O(H)$ time (where $H$ is the height of the tree) and $O(1)$ auxiliary space, completely avoiding the call stack overhead of recursion? - ### Follow-Up 1: Lowest Common Ancestor of a Standard Binary Tree The tree is no longer a Binary Search Tree; it is now a standard Binary Tree with completely unsorted values. You are again given two nodes `p` and `q` that exist in the tree. Task:** Find their Lowest Common Ancestor. Why does the previous $O(1)$ space iterative approach fail here? How do you implement a recursive **Post-Order Traversal** (checking left and right subtrees before processing the root) to propagate a boolean or node reference upward, solving this in $O(N)$ time and $O(H)$ space? - ### Follow-Up 2: LCA with Parent Pointers (No Root Provided) You are given a standard Binary Tree, but you are **not** given a reference to the `root` node. Instead, every node in the tree has an extra `parent` pointer linking it to its direct parent. You are given references to nodes `p` and `q`. Task:** Find their Lowest Common Ancestor without using any extra memory. Explain why this problem can be conceptually mapped to finding the intersection point of two Singly Linked Lists. How do you use two pointers starting at `p` and `q`, traversing upward using the `parent` pointers, and swapping to the other node's starting position upon reaching the top, to guarantee they collide exactly at the LCA in strictly $O(H)$ time and $O(1)$ auxiliary space? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Multimodality Modern models like GPT-4o or Gemini are described as "Multimodal." In plain English, what does it mean for an AI model to be multimodal natively, as opposed to a text-only LLM? How does this change the way users can interact with the system? - ### Question 2: Prompt Injection Attacks From a cybersecurity perspective, what is a "Prompt Injection" attack? Imagine a company deploys a helpful AI customer service chatbot on their website. How might a malicious user attempt to exploit the chatbot using prompt injection, and what is the underlying mechanism that makes this possible? - ### Question 3: Training vs. Inference In the AI industry, compute costs are heavily divided into two distinct phases: **Training** (or Pre-training) and **Inference**. What is the practical difference between these two phases? When a user types a message into a chatbot and receives a response, which phase is currently happening? - ### Question 4: Chain-of-Thought (Let's Think Step-by-Step) If you ask an LLM a complex math or logic question, it might get it wrong. However, if you simply append the phrase *"Let's think step by step"* to your prompt, its accuracy often skyrockets. Why does forcing the LLM to generate intermediate text (showing its work) actually improve its mathematical or logical reasoning capabilities?