How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview 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.

Determine feasibility and clean parentheses string

Q: Determine feasibility and clean parentheses string

This pair of problems evaluates proficiency with graph algorithms (dependency modeling and cycle detection/topological ordering) and string processing (parentheses balancing and minimal-edit transformations), focusing on algorithmic thinking, data-structure usage, and efficient linear-time solutions.

You are given two independent coding tasks.

1) Check if all courses/tasks can be completed

You have n courses labeled 0..n-1 and a list of prerequisite pairs prereq.

Each pair [a, b] means: to take course a , you must finish course b first.
Return true if it is possible to finish all n courses (i.e., there is no prerequisite cycle). Otherwise return false .

Input

Integer n
List of pairs prereq where each element is [a, b]

Output

Boolean

Constraints (typical interview scale)

1 ≤ n ≤ 10^5
0 ≤ |prereq| ≤ 2*10^5

2) Remove the minimum invalid parentheses

Given a string s consisting of lowercase letters and parentheses '(' and ')', remove the minimum number of parentheses so that the resulting string is valid.

A string is valid if:

Every ')' has a matching '(' before it.
Parentheses are properly nested.

Return one valid string after performing the minimum removals.

Input

String s

Output

A valid string formed by deleting the minimum number of parentheses characters

Constraints (typical interview scale)

1 ≤ |s| ≤ 10^5

Notes

Deleting letters is not allowed/needed; only delete parentheses.
If multiple answers exist, returning any one is acceptable.

You are given two independent coding tasks.

1) Check if all courses/tasks can be completed

You have n courses labeled 0..n-1 and a list of prerequisite pairs prereq.

Each pair [a, b] means: to take course a , you must finish course b first.
Return true if it is possible to finish all n courses (i.e., there is no prerequisite cycle). Otherwise return false .

Input

Integer n
List of pairs prereq where each element is [a, b]

Output

Boolean

Constraints (typical interview scale)

1 ≤ n ≤ 10^5
0 ≤ |prereq| ≤ 2*10^5

2) Remove the minimum invalid parentheses

Given a string s consisting of lowercase letters and parentheses '(' and ')', remove the minimum number of parentheses so that the resulting string is valid.

A string is valid if:

Every ')' has a matching '(' before it.
Parentheses are properly nested.

Return one valid string after performing the minimum removals.

Input

String s

Output

A valid string formed by deleting the minimum number of parentheses characters

Constraints (typical interview scale)

1 ≤ |s| ≤ 10^5

Notes

Deleting letters is not allowed/needed; only delete parentheses.
If multiple answers exist, returning any one is acceptable.

Determine feasibility and clean parentheses string

Quick Overview

1) Check if all courses/tasks can be completed

2) Remove the minimum invalid parentheses

Submit Your Answer to Earn 20XP

Determine feasibility and clean parentheses string

Quick Overview

1) Check if all courses/tasks can be completed

2) Remove the minimum invalid parentheses

Submit Your Answer to Earn 20XP