Validate parentheses and find k-th largest
Overview
This pair of problems evaluates mastery of fundamental data structures and algorithmic techniques: Problem A tests understanding of stack-based parsing and bracket-matching invariants for validating nested delimiters, while Problem B assesses proficiency with selection algorithms and heap-based priority queues for finding the k-th largest element.
Problem A — Validate parentheses
Given a string s containing only the characters '(', ')', '[', ']', '{', '}', determine whether the input string is valid.
A string is valid if:
- Open brackets are closed by the same type of brackets.
- Open brackets are closed in the correct order .
- Every closing bracket has a corresponding previously-opened bracket.
Input: s (string)
Output: true if s is valid, otherwise false.
Example
-
s = "()[]{}"→true -
s = "([)]"→false
Constraints (typical): 1 <= |s| <= 10^4
Problem B — k-th largest element using a heap
Given an integer array nums and an integer k, return the k-th largest element in the array.
Notes:
-
“k-th largest” refers to the element that would appear at index
k-1if the array were sorted in descending order. - Duplicates count as separate elements.
Input: nums (array of integers), k (integer)
Output: an integer, the k-th largest element.
Example
-
nums = [3,2,1,5,6,4], k = 2→5
Constraints (typical):
-
1 <= n <= 10^5 -
1 <= k <= n -
nums[i]fits in 32-bit signed int