PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates algorithmic problem-solving and data-structure competencies, focusing on selection algorithms and time/space complexity reasoning for the k-th largest element and tree traversal, lowest common ancestor discovery with attention to BST properties, parent pointers, and external-memory constraints.

  • medium
  • Meta
  • Coding & Algorithms
  • Software Engineer

Find Kth Largest and Tree Ancestors

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: This question evaluates algorithmic problem-solving and data-structure competencies, focusing on selection algorithms and time/space complexity reasoning for the k-th largest element and tree traversal, lowest common ancestor discovery with attention to BST properties, parent pointers, and external-memory constraints.

Part 1: K-th Largest Element in an Unsorted Array

Given an unsorted integer array nums and an integer k, return the k-th largest element. Duplicate values count as separate elements, so in [5, 5, 4], the 2nd largest is 5. The interview goal is to avoid fully sorting the array; a strong approach is randomized Quickselect, which partitions around a pivot until the target rank is found. Edge cases include k = 1, k = len(nums), duplicates, negative numbers, and a single-element array.

Constraints

  • 1 <= len(nums) <= 100000
  • -1000000000 <= nums[i] <= 1000000000
  • 1 <= k <= len(nums)
  • Duplicate values are allowed and count independently.

Examples

Input: ([3, 2, 1, 5, 6, 4], 2)

Expected Output: 5

Explanation: Sorted descending is [6, 5, 4, 3, 2, 1], so the 2nd largest is 5.

Input: ([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)

Expected Output: 4

Explanation: Sorted descending is [6, 5, 5, 4, 3, 3, 2, 2, 1].

Input: ([-1, -1, -2, -3], 2)

Expected Output: -1

Explanation: Duplicates count separately; the two largest elements are -1 and -1.

Input: ([10], 1)

Expected Output: 10

Explanation: Single-element edge case.

Input: ([7, 7, 7], 3)

Expected Output: 7

Explanation: All elements are equal, including the smallest/largest boundary ranks.

Hints

  1. The k-th largest element is at index len(nums) - k if the array were sorted in ascending order.
  2. Instead of sorting both sides recursively, partition around a pivot and continue only into the side containing the target index.

Part 2: Lowest Common Ancestor in a Binary Tree

Given a binary tree and two distinct node values p and q that both exist in the tree, return the value of their lowest common ancestor. The lowest common ancestor is the deepest node that has both p and q as descendants, where a node is allowed to be a descendant of itself. For coding convenience, the tree is represented by parallel arrays of node values and child indices. The core idea is a postorder DFS: if p is found in one subtree and q in the other, the current node is the answer; if the current node is p or q, it can be the answer when the other target lies below it.

Constraints

  • 2 <= len(values) <= 10000
  • len(left) == len(right) == len(values)
  • All values are unique integers.
  • left[i] and right[i] are either -1 or valid node indices.
  • The arrays describe a valid binary tree rooted at index 0.
  • p and q are distinct values that both appear in values.

Examples

Input: ([3, 5, 1, 6, 2, 0, 8, 7, 4], [1, 3, 5, -1, 7, -1, -1, -1, -1], [2, 4, 6, -1, 8, -1, -1, -1, -1], 5, 1)

Expected Output: 3

Explanation: Nodes 5 and 1 are in different subtrees of root 3.

Input: ([3, 5, 1, 6, 2, 0, 8, 7, 4], [1, 3, 5, -1, 7, -1, -1, -1, -1], [2, 4, 6, -1, 8, -1, -1, -1, -1], 5, 4)

Expected Output: 5

Explanation: Node 5 is an ancestor of node 4, so 5 is the LCA.

Input: ([3, 5, 1, 6, 2, 0, 8, 7, 4], [1, 3, 5, -1, 7, -1, -1, -1, -1], [2, 4, 6, -1, 8, -1, -1, -1, -1], 7, 4)

Expected Output: 2

Explanation: Nodes 7 and 4 are the two children of node 2.

Input: ([1, 2], [1, -1], [-1, -1], 1, 2)

Expected Output: 1

Explanation: Smallest valid tree edge case: the root is one of the queried nodes.

Input: ([1, 2, 3, 4], [-1, -1, -1, -1], [1, 2, 3, -1], 3, 4)

Expected Output: 3

Explanation: Skewed-tree edge case where one queried node is an ancestor of the other.

Hints

  1. A DFS call can return the index of a target or LCA found in that subtree, or -1 if neither target is present.
  2. If both left and right recursive calls return non-empty results, the current node is where the two target paths meet.

Part 3: Lowest Common Ancestor Optimized for a Binary Search Tree

Given a binary search tree and two distinct values p and q in it, return the value of their lowest common ancestor. Unlike a general binary tree, a BST lets you avoid searching both subtrees. If both targets are smaller than the current node, move left; if both are larger, move right; otherwise the current node is the split point and therefore the LCA. Edge cases include one target being an ancestor of the other and trees with only two nodes.

Constraints

  • 2 <= len(values) <= 100000
  • len(left) == len(right) == len(values)
  • All values are unique integers.
  • The arrays describe a valid binary search tree rooted at index 0.
  • For every node, all values in its left subtree are smaller and all values in its right subtree are larger.
  • p and q are distinct values that both appear in values.

Examples

Input: ([6, 2, 8, 0, 4, 7, 9, 3, 5], [1, 3, 5, -1, 7, -1, -1, -1, -1], [2, 4, 6, -1, 8, -1, -1, -1, -1], 2, 8)

Expected Output: 6

Explanation: Values 2 and 8 split at the root 6.

Input: ([6, 2, 8, 0, 4, 7, 9, 3, 5], [1, 3, 5, -1, 7, -1, -1, -1, -1], [2, 4, 6, -1, 8, -1, -1, -1, -1], 2, 4)

Expected Output: 2

Explanation: Node 2 is an ancestor of node 4.

Input: ([6, 2, 8, 0, 4, 7, 9, 3, 5], [1, 3, 5, -1, 7, -1, -1, -1, -1], [2, 4, 6, -1, 8, -1, -1, -1, -1], 3, 5)

Expected Output: 4

Explanation: Values 3 and 5 are on opposite sides of node 4.

Input: ([2, 1], [1, -1], [-1, -1], 2, 1)

Expected Output: 2

Explanation: Two-node edge case where the root is one of the queried nodes.

Input: ([1, 2, 3], [-1, -1, -1], [1, 2, -1], 2, 3)

Expected Output: 2

Explanation: Right-skewed BST edge case.

Hints

  1. Compare both p and q to the current node's value at the same time.
  2. The first node whose value lies between p and q, inclusive, is the LCA.

Part 4: Lowest Common Ancestor with Parent Pointers

Each node in a rooted tree has a pointer to its parent. Given two node indices p and q, return their lowest common ancestor index. You are not given the root directly, but it can be reached by following parent pointers. An efficient interview solution first computes the depth of both nodes, moves the deeper node upward until both are at the same depth, and then moves both upward together until they meet.

Constraints

  • 2 <= len(parent) <= 100000
  • parent contains exactly one -1 entry, representing the root.
  • Every other parent[i] is a valid node index.
  • The parent array describes a valid rooted tree.
  • 0 <= p, q < len(parent), and p != q.

Examples

Input: ([-1, 0, 0, 1, 1, 2, 2], 3, 4)

Expected Output: 1

Explanation: Nodes 3 and 4 are siblings under node 1.

Input: ([-1, 0, 0, 1, 1, 2, 2], 3, 5)

Expected Output: 0

Explanation: The paths meet first at the root 0.

Input: ([-1, 0, 0, 1, 1, 2, 2], 1, 4)

Expected Output: 1

Explanation: Node 1 is an ancestor of node 4.

Input: ([-1, 0], 0, 1)

Expected Output: 0

Explanation: Smallest valid tree edge case.

Input: ([-1, 0, 1, 2, 3], 4, 2)

Expected Output: 2

Explanation: Skewed chain edge case where one node is an ancestor of the other.

Hints

  1. Following parent pointers from a node gives its path to the root.
  2. If the two nodes are at the same depth, moving them upward one step at a time preserves the LCA.

Part 5: Lowest Common Ancestor When the Tree Is Too Large to Fit in Memory

In a very large tree, you may not be able to load all nodes or build child adjacency lists. For this coding version, parent and depth arrays represent external metadata lookups: parent[i] gives the parent id and depth[i] gives the node's depth from the root. Given two node ids p and q, return their LCA while using only parent/depth lookups along the two ancestor chains. The most memory-efficient approach is to equalize depths, then climb both nodes together. This avoids scanning the whole tree and avoids storing an ancestor set.

Constraints

  • 2 <= len(parent) == len(depth) <= 100000
  • parent contains exactly one -1 entry, representing the root.
  • depth[root] == 0, and depth[i] == depth[parent[i]] + 1 for non-root nodes.
  • The parent array describes a valid rooted tree.
  • 0 <= p, q < len(parent), and p != q.
  • The algorithm should not build child lists, traverse unrelated subtrees, or store complete root-to-node paths.

Examples

Input: ([-1, 0, 0, 1, 1, 2, 2], [0, 1, 1, 2, 2, 2, 2], 3, 5)

Expected Output: 0

Explanation: Nodes 3 and 5 are in different root subtrees, so the LCA is 0.

Input: ([-1, 0, 0, 1, 1, 2, 2], [0, 1, 1, 2, 2, 2, 2], 3, 4)

Expected Output: 1

Explanation: Both nodes have the same parent 1.

Input: ([-1, 0, 0, 1, 1, 2, 2], [0, 1, 1, 2, 2, 2, 2], 1, 4)

Expected Output: 1

Explanation: Node 1 is an ancestor of node 4; the deeper node is lifted first.

Input: ([-1, 0], [0, 1], 0, 1)

Expected Output: 0

Explanation: Smallest valid tree edge case.

Input: ([-1, 0, 1, 2, 3, 4], [0, 1, 2, 3, 4, 5], 5, 3)

Expected Output: 3

Explanation: Deep-chain edge case; depth alignment immediately lifts node 5 to node 3.

Hints

  1. Depth metadata tells you which node is deeper without walking all the way to the root first.
  2. After both nodes are at equal depth, move them upward together; the first equal id is the LCA.
Last updated: Jun 23, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Find Shortest Unique Prefixes - Meta (medium)
  • Compute Exclusive Execution Times - Meta (medium)
  • Solve Tree Columns And Maze Variants - Meta (medium)
  • Solve Tree Diameter and Palindromic Counts - Meta (medium)
  • Simulate Monster Team Battles - Meta (hard)