Find Kth Largest and Tree Ancestors

In a technical phone interview, the candidate was asked two coding problems in the same round: 1. **K-th largest element in an array** Given an unsorted integer array `nums` and an integer `k`, return the `k`-th largest element in the array. You should discuss the expected time and space complexity of your approach, and whether it can be solved without fully sorting the array. 2. **Lowest common ancestor in a tree** Given the root of a binary tree and two distinct nodes `p` and `q` in the tree, return their lowest common ancestor. The interviewer then asked several follow-up variants: - How would you optimize the solution if the tree is a **binary search tree**? - How would you solve it if each node has a **parent pointer**? - How would you approach the problem if the tree is **too large to fit into memory**? For each problem, explain the core idea, edge cases, and the most efficient implementation you would choose in an interview.