How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Solve Array Merge and Parentheses Cleanup

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are asked to solve two coding problems. ### Problem 1: Merge Three Sorted Arrays Given three integer arrays, each sorted in nondecreasing order, merge them into one sorted array and remove duplicate values. Return the final array in nondecreasing order, containing each distinct value exactly once. Example: ```text Input: a = [1, 2, 2, 5] b = [2, 3, 4] c = [1, 4, 6] Output: [1, 2, 3, 4, 5, 6] ``` Discuss the time and space complexity of your approach. ### Problem 2: Remove Invalid Parentheses Minimally Given a string containing lowercase English letters and parentheses `'('` and `')'`, remove the minimum possible number of parentheses so that the remaining string is valid. A valid string must satisfy: - Every opening parenthesis has a matching closing parenthesis. - Parentheses are matched in the correct order. - Letters do not affect validity. Return all distinct valid strings that can be produced by removing the minimum number of parentheses. The output order does not matter. Example: ```text Input: "()())()" Output: ["(())()", "()()()"] ``` Discuss the time and space complexity of your approach.

Quick Answer: This question evaluates array manipulation and deduplication skills for merging multiple sorted sequences with complexity analysis, alongside string parsing and combinatorial search for producing minimally edited valid parenthesis strings.

Part 1: Merge Three Sorted Arrays

You are given three integer arrays `a`, `b`, and `c`, each already sorted in nondecreasing order. Merge them into a single array that is also sorted in nondecreasing order, but include each distinct value only once. Your task is to return the sorted list of unique values appearing in any of the three arrays.

Constraints

0 <= len(a), len(b), len(c) <= 100000
-10^9 <= element value <= 10^9
Each input array is sorted in nondecreasing order

Examples

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

Expected Output: [1, 2, 3, 4, 5, 6]

Explanation: Merging all three sorted arrays and removing duplicates gives the sorted unique values 1 through 6.

Input: ([], [], [])

Expected Output: []

Explanation: All arrays are empty, so the result is also empty.

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

Expected Output: [0, 1]

Explanation: Only one array has values, and duplicates are removed.

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

Expected Output: [-5, -4, -3, 0, 1, 2]

Explanation: Negative numbers, repeated values, and values spread across arrays are all handled.

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

Expected Output: [7]

Explanation: All values are the same, so only one copy remains.

Hints

Because all three arrays are already sorted, think about advancing pointers instead of concatenating and sorting again.
When you choose the current smallest value, skip every occurrence of that value in all arrays to avoid duplicates.

Part 2: Remove Invalid Parentheses Minimally

You are given a string `s` containing lowercase English letters and the characters `'('` and `')'`. Remove the minimum possible number of parentheses so that the remaining string is valid. A string is valid if every opening parenthesis has a matching closing parenthesis, pairs are properly ordered, and letters are ignored when checking validity. Return all distinct valid strings that can be formed using the minimum number of removals. For deterministic output, return the result in lexicographically sorted order.

Constraints

0 <= len(s) <= 25
Each character in `s` is either a lowercase English letter, '(' or ')'

Examples

Input: "()())()"

Expected Output: ["(())()", "()()()"]

Explanation: Removing one parenthesis can produce two different valid strings, both requiring the minimum number of deletions.

Input: "(a)())()"

Expected Output: ["(a())()", "(a)()()"]

Explanation: Letters remain untouched, and there are two distinct valid results with one removal.

Input: ")("

Expected Output: [""]

Explanation: Both parentheses must be removed to make the string valid.

Input: "abc"

Expected Output: ["abc"]

Explanation: The string has no invalid parentheses, so it is already valid.

Input: ""

Expected Output: [""]

Explanation: The empty string is already valid.

Hints

If you explore all strings formed by removing one parenthesis at a time, the first level where you find valid strings gives the minimum removals.
Use a set to avoid processing the same string more than once.

Quick Overview

This question evaluates array manipulation and deduplication skills for merging multiple sorted sequences with complexity analysis, alongside string parsing and combinatorial search for producing minimally edited valid parenthesis strings.