## Facebook Interview Question for Software Developers

• 2
of 2 votes

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

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

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

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
}

}``````

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

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

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

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

}``````

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

You mind adding some example to the question?

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

}``````

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

}``````

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;
},'')
}``````

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

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