Facebook Interview Question Software Engineers
Country: United States
import java.util.Stack;
public class BalanceParanthese {
public static void main(String[] args) {
String s="((a(+b)(((())";
Stack<String> stack=new Stack<>();
for(int i=0;i<s.length();i++) {
char ch=s.charAt(i);
switch(ch) {
case '(':
stack.push("F");
break;
case ')':
stack.pop();
break;
default:
break;
}
}
StringBuilder out=new StringBuilder(s);
for(int i=0;i<stack.size();i++) {
out.append(")");
}
System.out.println("Input = "+s);
System.out.println("Output = "+out.toString());
}
}
Thing to keep in mind .. for a string to be balanced the number of ) should never exceed number of ( going left to right. Here is an O(n) solution with O(1) memory as it changes the string in place:
public class Solution {
public String balance(String str) {
if(str == null || str.isEmpty() || !isValid(str)) {
return "";
}
// Now we know the string can be balanced
int rightBraceOverCount;
Char array = str.charArray();
for(int i = 0; i < array.length; i++) {
Char c = array[i];
// AT NOT POINT in time should # of ) exceed number of ( if the string needs to be balanced
if(c == ')') {
rightBraceOverCount++;
// If after increment the right brace count became grater than 0 that means we need to change it to (
if(rightBraceOverCount > 0) {
array[i] = '(';
}
}
else {
// If the rightBraceOverCount was > 0 and we encountered a left brace then change it to ) as we must have replaced
// a prev ) with (
if(rightBraceOverCount > 0) {
array[i] = ')';
}
rightBraceOverCount--;
}
}
return str;
}
private boolean isValid(String str) {
Char[] array = str.charArray();
int leftBrace = 0, rightBrace = 0;
for(Char c : array) {
if(!(c == '(' || c == ')')) {
return false;
}
if(c == '(') {
leftBrace++;
}
else rightBrace++;
}
return leftBrace == rightBrace;
}
}
The string may be consisting of imbalanced(unbalanced) parenthesis but is complete, I mean, for every open parenthesis, there is a corresponding closing parenthesis, If it is not, we will try out best to make it complete till possible.
Here is how we would do it
public string MakeBalanced(sting parenthesis)
{
Stack s = new Stack();
Queue s = new Queue();
if(String.IsNullOrWhiteSpace(parenthesis))
{
return parenthesis;
}
StringBuilder newString = new StringBuilder();
for(int i = 0 ; i < parenthesis.Length;i++)
{
if(parenthesis[i] == '{' || parenthesis[i] == '(' || parenthesis[i] == '[')
{
newString.Append(parenthesis[i]);
if(OpositeParenthesis(q.Peek()) == parenthesis[i])
{
newString.Append(OpositeParenthesis(q.Dequeue()));
}
else
{
s.Push(parenthesis[i]);
}
}
else if(parenthesis[i] == '}' || parenthesis[i] == ')' || parenthesis[i] == ']')
{
if(OpositeParenthesis(s.Peek()) == parenthesis[i])
{
newString.Append(OpositeParenthesis(s.Pop()));
}
else
{
q.Enqueue(parenthesis[i]);
}
}
}
if(s.Count > 0)
{
while(s.Count > 0 && q.Count > 0)
{
if(q.Contains(OpositeParenthesis(s.Peek())))
{
While(q.Peek() != OpositeParenthesis(s.Peek()))
{
q.Enqueue(q.Dequeue());
}
s.Pop();
newString.Append(q.Dequeue());
}
}
}
else
{
newString.Append(q.ToString());
}
return newString.ToString();
}
public char OpositeParenthesis(char parenthesis)
{
if(parenthesis == '{')
{
return '}';
}
else if(parenthesis == '(')
{
return ')';
}
else if(parenthesis == '[')
{
return ']';
}
else if(parenthesis == '}')
{
return '{';
}
else if(parenthesis == ')')
{
return '(';
}
else if(parenthesis == ']')
{
return '[';
}
else
{
return parenthesis;
}
}
Complexity : O(N) space complexity and O(N) if Parenthesis are not randomly placed, if they are, it will require O(N*N) time complexity
public static String balance (String s) {
if (s == null || s.length() < 1) {
return s;
}
int ctr = 0;
for (Character c : s.toCharArray()) {
switch (c) {
case '(':
ctr--;
break;
case ')':
ctr++;
break;
}
}
while (ctr < 0) {
s += ')';
ctr++;
}
while (ctr > 0) {
s = '(' + s;
ctr--;
}
return s;
}
String str = ")(()";
// base case
if (str.length() == 0) {
System.out.println("Empty string");
return;
}
Stack<Character> stack = new Stack<>();
StringBuilder builder = new StringBuilder(str);
for (int i = 0 ; i < str.length(); i++) {
char c = str.charAt(i);
System.out.println(c);
if (c == '(') {
stack.push(c);
} else if (!stack.isEmpty() && stack.peek() == '(') stack.pop();
else builder.insert(0, '(');
}
while (!stack.isEmpty()) {
stack.pop();
builder.append(')');
}
System.out.println(builder.toString());
public class ParanthesisAppend {
private static final Map<Character, Character> brackets = new HashMap<Character, Character>();
private static final Map<Character, Character> oppositebrackets = new HashMap<Character, Character>();
static {
brackets.put('[', ']');
brackets.put('{', '}');
brackets.put('(', ')');
oppositebrackets.put(']', '[');
oppositebrackets.put('}', '{');
oppositebrackets.put(')', '(');
}
public static String isBalanced(String str) {
if (str.length() == 0) {
throw new IllegalArgumentException("String length should be greater than 0");
}
final Stack<Character> stack = new Stack<Character>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
if (brackets.containsKey(str.charAt(i))) {
stack.push(str.charAt(i));
sb.append(str.charAt(i));
} else if (stack.empty() || (str.charAt(i) != brackets.get(stack.pop()))) {
if (i == 0) {
if (sb.toString().indexOf(oppositebrackets.get(str.charAt(i))) == -1)
sb.insert(0, oppositebrackets.get(str.charAt(i)));
sb.append(str.charAt(i));
} else {
if (sb.toString().indexOf(oppositebrackets.get(str.charAt(i))) == -1)
sb.append(oppositebrackets.get(str.charAt(i)));
sb.append(str.charAt(i));
}
} else {
sb.append(str.charAt(i));
}
}
for (char c : stack) {
sb.append(brackets.get(c));
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(isBalanced("{}([])"));
System.out.println(isBalanced("([}])"));
System.out.println(isBalanced("([])"));
System.out.println(isBalanced("()[]{}[][]"));
System.out.println(isBalanced("[}])"));
}
}
public class ParanthesisAppend {
private static final Map<Character, Character> brackets = new HashMap<Character, Character>();
private static final Map<Character, Character> oppositebrackets = new HashMap<Character, Character>();
static {
brackets.put('[', ']');
brackets.put('{', '}');
brackets.put('(', ')');
oppositebrackets.put(']', '[');
oppositebrackets.put('}', '{');
oppositebrackets.put(')', '(');
}
public static String isBalanced(String str) {
if (str.length() == 0) {
throw new IllegalArgumentException("String length should be greater than 0");
}
final Stack<Character> stack = new Stack<Character>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
if (brackets.containsKey(str.charAt(i))) {
stack.push(str.charAt(i));
sb.append(str.charAt(i));
} else if (stack.empty() || (str.charAt(i) != brackets.get(stack.pop()))) {
if (i == 0) {
if (sb.toString().indexOf(oppositebrackets.get(str.charAt(i))) == -1)
sb.insert(0, oppositebrackets.get(str.charAt(i)));
sb.append(str.charAt(i));
} else {
if (sb.toString().indexOf(oppositebrackets.get(str.charAt(i))) == -1)
sb.append(oppositebrackets.get(str.charAt(i)));
sb.append(str.charAt(i));
}
} else {
sb.append(str.charAt(i));
}
}
for (char c : stack) {
sb.append(brackets.get(c));
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(isBalanced("{}([])"));
System.out.println(isBalanced("([}])"));
System.out.println(isBalanced("([])"));
System.out.println(isBalanced("()[]{}[][]"));
System.out.println(isBalanced("[}])"));
}
}
public class ParanthesisAppend {
private static final Map<Character, Character> brackets = new HashMap<Character, Character>();
private static final Map<Character, Character> oppositebrackets = new HashMap<Character, Character>();
static {
brackets.put('[', ']');
brackets.put('{', '}');
brackets.put('(', ')');
oppositebrackets.put(']', '[');
oppositebrackets.put('}', '{');
oppositebrackets.put(')', '(');
}
public static String isBalanced(String str) {
if (str.length() == 0) {
throw new IllegalArgumentException("String length should be greater than 0");
}
final Stack<Character> stack = new Stack<Character>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
if (brackets.containsKey(str.charAt(i))) {
stack.push(str.charAt(i));
sb.append(str.charAt(i));
} else if (stack.empty() || (str.charAt(i) != brackets.get(stack.pop()))) {
if (i == 0) {
if (sb.toString().indexOf(oppositebrackets.get(str.charAt(i))) == -1)
sb.insert(0, oppositebrackets.get(str.charAt(i)));
sb.append(str.charAt(i));
} else {
if (sb.toString().indexOf(oppositebrackets.get(str.charAt(i))) == -1)
sb.append(oppositebrackets.get(str.charAt(i)));
sb.append(str.charAt(i));
}
} else {
sb.append(str.charAt(i));
}
}
for (char c : stack) {
sb.append(brackets.get(c));
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(isBalanced("{}([])"));
System.out.println(isBalanced("([}])"));
System.out.println(isBalanced("([])"));
System.out.println(isBalanced("()[]{}[][]"));
System.out.println(isBalanced("[}])"));
}
}
Python simple BFS solution :
def isValid(mods):
"""Helper function to see if the string is valid."""
stack = []
for i in xrange(len(mods)):
if stack and stack[-1] == '(' and mods[i] == ')':
stack.pop(-1)
else:
stack.append(mods[i])
return not stack
def makeValidString(str):
if not str or isValid(str):
return str
visited, queue = set(), [str]
while queue:
element = queue.pop(0)
for i in xrange(len(element)):
newElement = element[:i] + element[i+1:]
if newElement not in visited:
if isValid(newElement): return newElement
queue.append(newElement)
visited.add(newElement)
This is an ambiguous question. Normally u use stack to evaluate an expression as well as to validate parenthesis if needed. This problem talks about imbalance of parenthesis which can still get to an valid value unless imbalance occurs at sign levels or if expression has to follow BODMAS principle.
String balanceParenthesis(String s, char open, char close) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == open)
count++;
if (s.charAt(i) == close)
count--;
}
for (; count < 0; count++)
s = open + s;
for (; count > 0; count--)
s = s + close;
return s;
}
. . .
balanceParenthesis("((a(+b)(((())", '(', ')'); --> ((a(+b)(((())))))
Here is my Solution in Java:
public static String BalencedParenthesis(String string) {
int open = 0;
int closed = 0;
if (string.length() == 0) {
return "Empty String";
}
for (int i = 0; i < string.length(); i++) {
String value = String.valueOf(string.charAt(i));
if (value.equals("(")) {
open++;
} else if (value.equals(")")) {
closed--;
}
}
int sum = open + closed;
if (sum == 0) {
return string;
} else if (sum > 0) {
while (sum != 0) {
string += ")";
sum--;
}
} else if (sum < 0) {
while (sum != 0) {
string += "(";
sum++;
}
}
return string;
}
}
Here is my solution in Java:
public static String BalencedParenthesis(String string) {
int open = 0;
int closed = 0;
if (string.length() == 0) {
return "Empty String";
}
for (int i = 0; i < string.length(); i++) {
String value = String.valueOf(string.charAt(i));
if (value.equals("(")) {
open++;
} else if (value.equals(")")) {
closed--;
}
}
int sum = open + closed;
if (sum == 0) {
return string;
} else if (sum > 0) {
while (sum != 0) {
string += ")";
sum--;
}
} else if (sum < 0) {
while (sum != 0) {
string += "(";
sum++;
}
}
return string;
}
}
import java.util.Stack;
public class BalanceParanthese {
public static void main(String[] args) {
String s="((a(+b)(((())";
Stack<String> stack=new Stack<>();
for(int i=0;i<s.length();i++) {
char ch=s.charAt(i);
switch(ch) {
case '(':
stack.push("F");
break;
case ')':
stack.pop();
break;
default:
break;
}
}
StringBuilder out=new StringBuilder(s);
for(int i=0;i<stack.size();i++) {
out.append(")");
}
System.out.println("Input = "+s);
System.out.println("Output = "+out.toString());
}
}
- tjcbs2 March 27, 2017#include <string> std::string balancedParens(const std::string& input) { std::string output; int state = 0; for (auto it = input.begin(); it != input.end(); it++) { state += *it == '(' ? 1 : -1; if (state == -1) { for (auto it2 = it; it2 != input.end() && *it2 == ')'; it2++, state++) output += '('; } output += *it; } for (int i = 0; i < state; i++) output += ')'; return output; }