Katkat
Back

Validate parentheses and find k-th largest

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to handle nested structures using a stack and your efficiency in order-based selection using heap operations.

Part 1: String Validation

Given a string s containing only characters '(', ')', '[', ']', '{', '}', determine if the string is valid. A string is valid if brackets are closed in the correct order and every closing bracket has a corresponding opening bracket of the same type.

Function Signature

def isValid(s: str) -> bool:

Part 2: K-th Largest Element

Given an unsorted list of integers nums and an integer k, return the k-th largest element in the array. Note that it is the k-th largest element in sorted order, not the k-th distinct element.

Function Signature

def findKthLargest(nums: List[int], k: int) -> int:

Examples

Part 1:

  • Input: s = "()[]{}" -> Output: True
  • Input: s = "([)]" -> Output: False

Part 2:

  • Input: nums = [3,2,1,5,6,4], k = 2 -> Output: 5
  • Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 -> Output: 4

Constraints

  • Part 1: 1 <= s.length <= 10^4
  • Part 2: 1 <= k <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4
  • Part 2 should aim for better than O(n log n) time complexity.

Hints

Hint 1

For Part 1, use a stack to push opening brackets and pop/check when encountering a closing bracket.

Hint 2

For Part 2, a min-heap of size k is an efficient way to keep track of the largest elements seen so far.

Hint 3

Consider the QuickSelect algorithm as an alternative to heaps to achieve an average time complexity of O(n).

Follow-up questions

  • How would you modify the validation function to support multi-character tokens like 'begin' and 'end'?
  • What is the worst-case time complexity of QuickSelect, and how can you mitigate it using random pivots?
  • How would you solve the k-th largest problem if the input size is too large to fit in memory?