Facebook Interview Question for Software Developers


Country: United States
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
4
of 4 vote

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 '('

public static String balanceParenthesis(String s) {
        StringBuilder str = new StringBuilder(s);
        int left = 0;
        for(int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == '(') {
                left++;
            } else if(str.charAt(i) == ')') {
                if(left > 0) {
                    left--;
                } else {
                    str.deleteCharAt(i--);
                }
            }
        }
        int right = 0;
        for(int i = str.length() - 1; i >= 0; i--) {
            if(str.charAt(i) == ')') {
                right++;
            } else if(str.charAt(i) == '('){
                if(right > 0) right--;
                else {
                    str.deleteCharAt(i);
                }
            }
        }
        return str.toString();
    }

- aonecoding April 07, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}

- billyliu597 April 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
	}
}

- dadakhalandhar April 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
  }

}

- jvmakine April 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous May 21, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1-5-(8+9)+6)

- Anonymous April 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
        }
    }

}

- PeyarTheriyaa April 08, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You mind adding some example to the question?

- Asif Garhi April 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
    }
  
  }

- vibhorrastogi.in April 25, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
		
	}

- Sergio Flores May 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function balanceParenthesis(str) {
	let arr = []
	return str.split('').reduce((a,e) => {
		if(e === '(') {
			arr.push('(');
		} else if(e === ')') {
			if(arr.length > 0) {
				arr.pop();
			} else {
				return a;
			}
		}
		return a+e;
	},'')
}

- kk October 01, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
   }
}

- just_do_it November 11, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More