Solve classic LeetCode problems
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Question
LeetCode 215. Kth Largest Element in an Array LeetCode 249. Group Shifted Strings Variant of LeetCode 56. Merge Intervals extended to 2-D rectangles LeetCode 938. Range Sum of BST
https://leetcode.com/problems/kth-largest-element-in-an-array/description/ https://leetcode.com/problems/group-shifted-strings/description/ https://leetcode.com/problems/merge-intervals/description/ https://leetcode.com/problems/range-sum-of-bst/description/
Overview: This question evaluates proficiency with core data structures and algorithmic techniques including array selection and ordering, string pattern grouping, interval/rectangle merging, and binary search tree range queries.
Given an integer array nums and an integer k (1-indexed), return the k-th largest element in the array. The k-th largest element is the element that would appear at index len(nums) - k if nums were sorted in nondecreasing order. Duplicates count as separate elements.
Constraints
- 1 <= len(nums) <= 200000
- -10^9 <= nums[i] <= 10^9
- 1 <= k <= len(nums)
Hints
- Maintain a min-heap of size k to track the k largest elements.
- Alternatively, use Quickselect (Hoare's selection) to achieve average O(n) time.
- Transform k-th largest to (n - k)-th index in ascending order.