Flipkart Grid

# 1. Difference Between Maximum and Minimum Price Sum ## Problem Statement There exists an undirected and unrooted tree with `n` nodes indexed from `0` to `n - 1`. You are given the integer `n` and a 2D integer array `edges` of length `n - 1`, where `edges[i] = [u_i, v_i]` indicates that there is an edge between nodes `u_i` and `v_i` in the tree. Each node has an associated price. You are given an integer array `price`, where `price[i]` is the price of the `i`-th node. The **price sum** of a given path is the sum of the prices of all nodes lying on that path. The tree can be rooted at any node `root` of your choice. The incurred cost after choosing `root` is the difference between the **maximum** price sum of any path starting at `root` and the **minimum** price sum of any path starting at `root`. Return the maximum possible cost you can achieve. (Hint: Since all prices are strictly positive, the minimum price sum starting at `root` will always just be `price[root]`. The problem reduces to finding the maximum path sum in the tree minus one of its endpoints. This can be solved optimally in O(N) time using Tree Rerooting DP.)* ## Constraints `1 <= n <= 10^5` `edges.length == n - 1` `0 <= u_i, v_i <= n - 1` `edges` represents a valid tree. `price.length == n` `1 <= price[i] <= 10^5` ## Test Cases Test Case 1:** *Input:** `n = 6`, `edges = [[0,1],[1,2],[1,3],[3,4],[3,5]]`, `price = [9,8,7,6,10,5]` *Output:** `24` *Explanation:** Choose `root = 2`. The max path starting at `2` goes to `4` (2 -> 1 -> 3 -> 4) with a price sum of `7 + 8 + 6 + 10 = 31`. The min path starting at `2` is just the node `2` itself with a price sum of `7`. The difference is `31 - 7 = 24`. It can be proven that 24 is the maximum possible cost. Test Case 2:** *Input:** `n = 3`, `edges = [[0,1],[1,2]]`, `price = [1,1,1]` *Output:** `2` *Explanation:** Choose `root = 0`. The max path goes to `2` with a sum of `1 + 1 + 1 = 3`. The min path is just `0` with a sum of `1`. Difference is `3 - 1 = 2`. - # 2. Count Valid Paths in a Tree ## Problem Statement There is an undirected tree with `n` nodes labeled from `1` to `n`. You are given the integer `n` and a 2D integer array `edges` of length `n - 1`, where `edges[i] = [u_i, v_i]` indicates that there is an edge between nodes `u_i` and `v_i` in the tree. Return the number of **valid paths** in the tree. A path `(u, v)` is considered **valid** if there is **exactly one** prime number among the node labels in the simple path from `u` to `v`. (Note: The path `(u, v)` is considered the same as the path `(v, u)` and should only be counted once.)* (Hint: Use the Sieve of Eratosthenes to identify prime nodes. If you virtually "remove" all prime nodes, the tree splits into several connected components containing only non-prime nodes. You can use a Disjoint Set Union (DSU) or DFS to find the size of each non-prime component, and then use combinatorial math around each prime node to count the valid paths in O(N) time.)* ## Constraints `1 <= n <= 10^5` `edges.length == n - 1` `edges[i].length == 2` `1 <= u_i, v_i <= n` `edges` represents a valid tree. ## Test Cases Test Case 1:** *Input:** `n = 5`, `edges = [[1,2],[1,3],[2,4],[2,5]]` *Output:** `4` *Explanation:** The prime numbers up to 5 are 2, 3, and 5. The valid paths (containing exactly one prime) are: (1, 2) since the path from 1 to 2 contains prime 2. (1, 3) since the path from 1 to 3 contains prime 3. (1, 4) since the path from 1 to 4 contains prime 2. (2, 4) since the path from 2 to 4 contains prime 2. Paths like (1, 5) are invalid because they contain two primes (2 and 5). Test Case 2:** *Input:** `n = 6`, `edges = [[1,2],[1,3],[2,4],[3,5],[3,6]]` *Output:** `6` *Explanation:** The primes are 2, 3, and 5. The valid paths are: (1, 2) contains prime 2. (1, 3) contains prime 3. (1, 4) contains prime 2. (2, 4) contains prime 2. (3, 6) contains prime 3. (1, 6) contains prime 3. # LLM & Generative AI Questions ## 1. Transformer Architecture Explain the Transformer architecture from scratch. Why were Transformers able to outperform RNNs and LSTMs for many NLP tasks? Explain the roles of self-attention, multi-head attention, positional encoding, residual connections, and layer normalization. - ## 2. Self-Attention Given the Query (Q), Key (K), and Value (V) matrices, derive the self-attention formula: Attention(Q, K, V) = softmax(QKᵀ / √dₖ)V Explain why we divide by √dₖ and what would happen if this scaling factor were removed. - ## 3. Multi-Head Attention Why do Transformers use multiple attention heads instead of a single attention mechanism with the same total dimensionality? Give an intuitive example of what different attention heads could potentially learn. - ## 4. Tokenization Compare BPE, WordPiece, and SentencePiece tokenization. Why do modern LLMs generally use subword-based tokenization instead of word-level tokenization? - ## 5. Positional Encoding Why does a Transformer need positional information? Compare sinusoidal positional encoding with learned positional embeddings. - ## 6. Causal Language Modeling What is causal language modeling? Given the sentence: "The cat is sitting on the" explain how an autoregressive LLM predicts the next token and why it cannot directly attend to future tokens during training. - ## 7. Pretraining Objective Explain the objective function used to train an autoregressive LLM. Given a sequence of tokens x₁, x₂, ..., xₙ, derive the probability that the model assigns to the complete sequence. - ## 8. Cross-Entropy Loss Why is cross-entropy loss commonly used to train language models? Explain the relationship between cross-entropy loss and maximum likelihood estimation. - ## 9. Temperature Suppose an LLM produces the following logits: ```text [2.5, 1.5, 0.5, -1.0]