Facebook Interview Question
Software DevelopersCountry: United States
Interview Type: Written Test
C#
public string LongestValidParenthese(string s)
{
int cnt = 0;
IList<int> open = new List<int>();
IList<int> close = new List<int>();
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '(')
{
cnt++;
open.Add(i);
}else if (s[i] == ')')
{
cnt--;
if (cnt < 0)
{
close.Add(i);
cnt = 0;
}
else
{
open.RemoveAt(open.Count - 1);
}
}
}
StringBuilder sb = new StringBuilder();
int lo = 0, lc = 0;
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '(')
{
if (lo < open.Count && i == open[lo])
{
lo++;
}
else
{
sb.Append(s[i]);
}
}else if (s[i] == ')')
{
if (lc < close.Count && i == close[lc])
{
lc++;
}
else
{
sb.Append(s[i]);
}
}
else
{
sb.Append(s[i]);
}
}
return sb.ToString();
}
g
import java.util.ArrayList;
import java.util.List;
public class RemoveUnbalancedParenthesis {
public static void main(String[] args) {
String input = "i7difdk(ds()))98ijdskjf(89lk)8w(((()))))";
System.out.println(removeUnbalancedParenthesis(input));
}
private static class PosAndLfRt{
int pos;
int ltRt;
private PosAndLfRt(int pos, int ltRt){
this.pos = pos;
this.ltRt = ltRt;
}
}
public static String removeUnbalancedParenthesis(String input){
StringBuilder str = new StringBuilder(input);
List<PosAndLfRt> parenthesis = new ArrayList<>();
for(int i=0;i<str.length();i++){
char charecter = str.charAt(i);
if(charecter == '('){
parenthesis.add(new PosAndLfRt(i,1));
}else if(charecter == ')'){
parenthesis.add(new PosAndLfRt(i,-1));
}
}
int track = 0;
List<Integer> posToRemove = new ArrayList<>();
for (PosAndLfRt posAndLfRt : parenthesis) {
track += posAndLfRt.ltRt;
if(track<0){
posToRemove.add(posAndLfRt.pos);
track++;
}
}
int posToRmvLen = posToRemove.size();
for (int i = posToRmvLen-1;i>=0;i--) {
str.deleteCharAt(posToRemove.get(i));
}
return str.toString();
}
}
import scala.collection.immutable.Stack
object BalanceParenthesis extends App {
println(balance("((a((aa(((()d(())("))
def balance(input: String): String = {
var stack = Stack.empty[Int]
var remove = Set.empty[Int]
val withIndices = input.toCharArray.zipWithIndex
withIndices.foreach { case (c, i) =>
c match {
case '(' => stack = stack.push(i)
case ')' => if (stack.isEmpty) remove = remove + i else stack = stack.pop
case _ =>
}
}
remove = remove ++ stack.toSet
withIndices.filterNot(v => remove.contains(v._2)).map(_._1).mkString
}
}
Using the stack has been my first thought as well, but it is not the correct solution as it is asking for removing the fewest characters as possible.
That's why the solution proposed by aonecoding using counters is the best:
E.g. (ignoring other charachters but parenthesis)
"((())(())"
"((()))" -> 3 removals // using stack
"((())())" -> 1 removal // using counter
I did something similar to the scala one..
1. loop through the entire string
1.a. if ( is found push it in stack
1.b.i if ) is found pop it from stack
1.b.ii if ) is found and there is no matching ( <empty stack> then remove )
2 at the end stack has all the ( with no matching ) and so remove all ( in the stack
import java.io.IOException;
import java.util.EmptyStackException;
import java.util.Scanner;
import java.util.Stack;
public class Solution1a
{
private static final Scanner in = new Scanner(System.in);
private static String input;
public static void main(String[] args) throws IOException
{
input = in.nextLine();
balPara();
System.out.println(input);
}
private static void balPara()
{
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < input.length(); i++)
if (input.charAt(i) == '(')
stack.push(i);
else if (input.charAt(i) == ')')
try {
stack.pop();
}
catch (EmptyStackException e) {
input = input.substring(0, i) + input.substring(i + 1);
i--;
}
while (stack.size() > 0) {
input = input.substring(0, stack.peek()) + input.substring(stack.peek() + 1);
stack.pop();
}
}
}
static void trim(char[] chars){
if(chars == null)
throw new IllegalArgumentException();
Stack<Character> s = new Stack<>();
int i=0;
for(;i<chars.length; i++){
if(chars[i] == '(')
s.push('(');
else{
if(!s.isEmpty() && s.peek().equals('(')){
if(chars[i] == ')')
s.pop();
}
else{
chars[i] = '#';
}
}
}
int j = i-1;
while(!s.isEmpty()){
char c = chars[j];
chars[j] = '#';
if(c == '(')
s.pop();
}
}
public static String balanceParentesis(String string){
StringBuffer sb = new StringBuffer(string);
int noOfParenthesis = 0;
for(int x = 0; x < string.length(); x ++){
if(string.charAt(x) == '(' || string.charAt(x) == ')')
noOfParenthesis++;
}
int noOfOtherCharts = string.length() - noOfParenthesis;
int elementsToDelete = noOfOtherCharts - noOfParenthesis;
boolean flag = (elementsToDelete == 0) ? false : true;
int x = 0;
int deletedItems = 0;
while(flag){
boolean resultFinding = (elementsToDelete < 0)?
(string.charAt(x) != ')' && string.charAt(x) != '(')
: string.charAt(x) == ')' || string.charAt(x) == '(';
if(resultFinding){
sb.deleteCharAt(x);
string = sb.toString();
deletedItems++;
if(deletedItems == elementsToDelete)
flag = false;
}else{
x++;
}
}
return sb.toString();
}
import java.util.Arrays;
import java.util.Stack;
public class MinDeletionsToBalanceParantheses {
public static void main(String[] args){
String[] testcase = { "()())()" , "((a((aa((()d(())(",
"())))()(((()))))))()(((()(()))("
};
for (String test : testcase){
String res = balance(test);
System.out.println(test + " result: " + res);
}
}
public static String balance(String inp) {
Stack<Integer> stack = new Stack<Integer>();
int n = inp.length();
char[] inpc = inp.toCharArray();
boolean[] markedForDeletion = new boolean[n];
Arrays.fill(markedForDeletion, false);
for (int i = 0; i < n; i++) {
char c = inpc[i];
if (c == ')') {
if (stack.isEmpty()) {
markedForDeletion[i] = true;
} else {
stack.pop();
}
} else if(c == '('){
stack.push(i);
}
}
while(!stack.isEmpty()){
markedForDeletion[stack.pop()] = true;
}
int numDeletions = 0;
String res = "";
for (int i = 0; i < n; i++){
if (!markedForDeletion[i]){
res = res + inpc[i];
} else {
numDeletions++;
}
}
System.out.println("numDeletions " + numDeletions);
return res;
}
}
Looking for coaching on interview preparation?
Visit AONECODE.COM for ONE-TO-ONE private lessons by FB, Google and Uber engineers!
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. advanced algorithms and clean coding)
Interview questions sorted by companies
Mock Interviews
Ace G, U, FB, Amazon, LinkedIn, MS and other top-tier interviews in weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution: O(n)
first for-loop removes all invalid ')'. Second for-loop removes all invalid '('
- aonecoding April 07, 2018