Katkat
Back

Determine feasibility and clean parentheses string

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate string structures using stack-based logic and perform graph-based dependency resolution using topological sort.

Part 1: Balanced Parentheses

Given a string s consisting of '(' and ')', write a function minRemoveToMakeValid(s) that removes the minimum number of parentheses so that the remaining string is valid. A string is valid if it is empty, contains only valid parentheses, or can be written as AB where A and B are valid. Return any valid resulting string.

Examples

  • Input: "lee(t(c)o)de)" -> Output: "lee(t(c)o)de"
  • Input: "a)b(c)d" -> Output: "ab(c)d"

Part 2: Task Scheduler with Dependencies

Imagine these parentheses represent task dependencies where an open parenthesis ( represents the start of a task and a close parenthesis ) represents the end. Now, consider a set of n tasks labeled 0 to n-1 and a list of directed edges prerequisites where [a, b] means task a depends on task b (you must finish b before a). Determine if it is possible to finish all tasks.

Function Signature

def canFinish(numTasks: int, prerequisites: List[List[int]]) -> bool:

Constraints

  • 1 Output: True`
  • Input: numTasks = 2, prerequisites = [[1,0], [0,1]] -> Output: False

Hints

Hint 1

For Part 1, use a stack to track indices of unmatched parentheses, then remove characters at those specific indices.

Hint 2

For Part 2, recognize this as a directed graph cycle detection problem, which can be solved using Kahn's Algorithm (in-degree counting) or DFS with coloring.

Hint 3

Ensure your topological sort implementation handles disconnected components by iterating through all nodes in the graph.

Follow-up questions

  • In Part 1, how would you modify your solution if there were multiple types of brackets (e.g., [], {}, ())?
  • In Part 2, if a valid ordering exists, how would you return the specific sequence of tasks rather than just a boolean?
  • What are the space and time complexity trade-offs if you used an adjacency matrix instead of an adjacency list for the dependency graph?