Google Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
void run(char[] a){
int n = a.length;
boolean[] valid = new boolean[n];
Stack<Integer> sp = new Stack<Integer>();
for(int i = 0; i < n; i++){
if(a[i] == '(') sp.push(i);
else if(a[i] == ')'){
if(!sp.isEmpty() && a[sp.peek()] == '('){
valid[i] = true;
valid[sp.pop()] = true;
}
}
else valid[i] = true;
}
for(int i = 0; i < n; i++)
if(valid[i]) System.out.print(a[i]);
System.out.println();
}
void run(char[] a){
int n = a.length;
boolean[] valid = new boolean[n];
Stack<Integer> sp = new Stack<Integer>();
for(int i = 0; i < n; i++){
if(a[i] == '(') sp.push(i);
else if(a[i] == ')'){
if(!sp.isEmpty() && a[sp.peek()] == '('){
valid[i] = true;
valid[sp.pop()] = true;
}
}
else valid[i] = true;
}
for(int i = 0; i < n; i++)
if(valid[i]) System.out.print(a[i]);
System.out.println();
}
/* Balance Parentheris */
def is_balanced(string){
!exists([0: size(string)/2 ] ) where {
// when s[index] != s[-1-index]
string[$.o] != string[-1-$.o]
}
}
def balance_paren(string){
if ( is_balanced(string) ) { return string }
// now, here... generates a multi set
m = mset(string.value)
left_count = m[_'(']
right_count = m[_')']
#(min,max) = minmax(left_count,right_count)
// extract the bracket less string
s = fold(m.keys,'') as {
continue( $.o == _'(' || $.o == _')' )
$.p += ( str($.o) ** m[$.o] )
}
// duplicate bracket-ness and... creare a balanced string
( '(' ** max ) + s + ( ')' ** max )
}
println( balance_paren(@ARGS[0]) )
void run(char[] a){
int n = a.length;
boolean[] valid = new boolean[n];
Stack<Integer> sp = new Stack<Integer>();
for(int i = 0; i < n; i++){
if(a[i] == '(') sp.push(i);
else if(a[i] == ')'){
if(!sp.isEmpty() && a[sp.peek()] == '('){
valid[i] = true;
valid[sp.pop()] = true;
}
}
else valid[i] = true;
}
for(int i = 0; i < n; i++)
if(valid[i]) System.out.print(a[i]);
System.out.println();
}
Solution in python using a stack (promoted to a counter as we only have one type of parens). Regarding the input examples. For the input: '(((((' the output should be: '((((()))))' isn't?
def balanceParens(s):
parens_stack = 0
res = ''
for c in s:
if c == '(':
parens_stack += 1
elif c == ')':
if parens_stack == 0: continue
parens_stack -= 1
res += c
res += ')' * parens_stack
return res
import java.util.Scanner;
import java.util.Stack;
public class BalancedParanthesis{
public static void main(String args[]){
Stack<Integer> stack= new Stack<Integer>();
Scanner in= new Scanner(System.in);
StringBuilder str = new StringBuilder(in.next());
in.close();
int i,n=str.length();
for(i=0;i<n;i++){
if(str.charAt(i)=='(')
stack.push(i);
else if(str.charAt(i)==')'){
if(stack.isEmpty()){
str.deleteCharAt(i--);
n--;
}
else
stack.pop();
}
}
while(!stack.isEmpty())
{
str.deleteCharAt(stack.peek());
stack.pop();
}
System.out.println(str);
}
}
Couple of assumptions before we begin:
1) Will the string always have equal number of ( and )? If not then should we add extra missing braces to balance them? Thats the approach code below takes and runs in O(N) memory and O(N) time
public class Solution {
public String balance(String str) {
if(str == null || str.isEmpty() || (str.indexOf('(') < 0 && str.indexOf(')') < 0)) {
return str;
}
StringBuilder sb = new StringBuilder();
int rightCount = leftCount = remRight = remLeft = 0;
for(Character c : str.toCharArray()) {
if(c != '(' && c != ')') {
sb.append(c);
continue;
}
if(c == '(') {
leftCount++;
}
else {
if(leftCount > rightCount) {
rightCount++;
}
else {
remRight++;
continue;
}
}
sb.append(c);
}
// In case our input had unequal number of ( and )
while(leftCount > rightCount) {
sb.append(')');
rightCount++;
remRight--;
}
if(remRight > 0) {
for(int i = 1; i <= remRight; i++) {
sb.append('()');
}
}
return sb.toString();
}
}
import java.util.Arrays;
import java.util.Stack;
public class BalanceStringParentheses {
public static void main(String[] args){
System.out.println(balanceStringParentheses("a(b)"));
System.out.println(balanceStringParentheses("(((("));
System.out.println(balanceStringParentheses("(()())"));
System.out.println(balanceStringParentheses(")ab(()"));
}
public static String balanceStringParentheses(String input){
char[] inputChar = input.toCharArray();
Stack<Integer> openingParentheses = new Stack<Integer>();
boolean[] charToBeRemoved = new boolean[inputChar.length];
Arrays.fill(charToBeRemoved, false);
for(int i = 0 ; i < inputChar.length; i++)
{
if(inputChar[i] == '('){
openingParentheses.push(i);
}
else if(inputChar[i] == ')'){
if(!openingParentheses.empty())
{
openingParentheses.pop();
}
else{
charToBeRemoved[i] = true;
}
}
}
// if there are un matched opening parentheses remove them
while(!openingParentheses.empty()){
charToBeRemoved[openingParentheses.pop()] = true;
}
// now collect only the balanced chars.
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < inputChar.length; i++){
if(!charToBeRemoved[i]){
sb.append(inputChar[i]);
}
}
return sb.toString();
}
}
string Balance(string const &s)
{
unordered_set<int> remove_idxes;
stack<int> st;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == ')') {
if (st.empty()) {
remove_idxes.insert(i);
} else {
st.pop();
}
} else if (s[i] == '(') {
st.push(i);
}
}
while (!st.empty()) {
remove_idxes.insert(st.top());
st.pop();
}
string out;
for (int i = 0; i < s.size(); ++i) {
if (remove_idxes.find(i) == remove_idxes.end()) {
out += s[i];
}
}
return out;
}
Store the position of '(' in another stack.The position should be the length of the output string at that point. If '(' needs to be printed in the output string, then we can get the entry position in the output string from the stackPos.
- Sibendu Dey June 26, 2017