Balanced Brackets and List Merge | Dataford Interview Questions

Your question is Balanced Brackets and List Merge. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

PagerDuty configuration and incident-routing expressions can contain nested brackets. Given a bracket string and two sorted integer lists, first verify that the brackets are properly matched and nested. If they are valid, return one sorted list containing all values from both input lists. If the bracket string is invalid, return None and do not merge the lists.

The bracket string contains only (, ), [, ], {, and }. An empty string is valid. The input lists are sorted in nondecreasing order and may contain duplicates.

Formal Specification

Implement validate_and_merge(brackets, first, second):

Input: brackets, a string; first and second, sorted lists of integers.
Output: The merged sorted list if brackets is valid, otherwise None.
The returned list must preserve duplicates and contain every value from both input lists exactly once.

Constraints

0 <= len(brackets) <= 10^4
0 <= len(first), len(second) <= 10^4
-10^9 <= first[i], second[i] <= 10^9
first and second are sorted in nondecreasing order
brackets contains only parentheses, square brackets, and curly brackets

Function Signature

def validate_and_merge(brackets, first, second):