Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

First of all, my Test Set. Use it to check your solution (hint: many of the solutions here fail it)

class MainTest {

    @Test
    void isBalanced() {
        assertTrue(Main.isBalanced(""));
        assertTrue(Main.isBalanced("()"));
        assertTrue(Main.isBalanced("(*)"));
        assertTrue(Main.isBalanced("(*)(*)"));

        assertTrue(Main.isBalanced("*"));
        assertTrue(Main.isBalanced("**"));
        assertTrue(Main.isBalanced("*)"));

        assertTrue(Main.isBalanced("*(((()())()))())"));

        assertFalse(Main.isBalanced("*()("));
        assertFalse(Main.isBalanced("**()("));
        assertFalse(Main.isBalanced("**(**)*("));
        assertFalse(Main.isBalanced(")**"));
        assertTrue(Main.isBalanced("****()))))"));
        assertTrue(Main.isBalanced("****())))"));
        assertFalse(Main.isBalanced("****())))))"));
        assertFalse(Main.isBalanced("***********************(((((()"));


        assertFalse(Main.isBalanced("(((()())()))())"));
        assertTrue(Main.isBalanced("*(((()())())*())"));
    }

    @Test
    void isBalanced5() {
        assertTrue(Main.isBalanced("(*)(*)(**"));
    }


    @Test
     void isBalanced10() {
        assertTrue(Main.isBalanced("*(((()())())())"));
    }

}

My approach solves it in O(n^2). And handles all of the cases regardless of the number and position of characters in a string. It's pretty brute-force but it does the job. This is a solution for the simple case. For the case with "[]" and "{}" you just have to call it 3 times passing bracket chars as parameters

public class Main {

    public static boolean isBalanced(String exp){
        // Empty string is balanced by definition
        if (exp.length() == 0) {
            return true;
        }

        // edge cases - no point in looking further
        if (exp.charAt(0) == ')' || exp.charAt(exp.length()-1) == '(') {
            return false;
        }

        // find all (), (*), (**), ... cases and clear the brackets
        for (int i = 0; i < exp.length(); i++) {
            if (exp.charAt(i) == ')') {
                for (int j = i - 1; j >= 0; j--) {
                    if (exp.charAt(j) == ')') {
                        break;
                    } else if (exp.charAt(j) == '(') {
                        exp = replaceString(exp, i, j);
                        break;
                    }
                }
            }
        }

        // find all *), *_), *___), ... cases and use the stars as left brackets
        for (int i = 0; i < exp.length(); i++) {
            if (exp.charAt(i) == ')') {
                for (int j = i - 1; j >= 0; j--) {
                    if (exp.charAt(j) == '*') {
                        exp = replaceString(exp, i, j);
                        break;
                    }
                    if (j == 0) {
                        return false;
                    }
                }
            }
        }

        // same for (*, (_*, (___*
        for (int j = exp.length() - 1; j >= 0; j--) {
            if (exp.charAt(j) == '(') {
                for (int i = j + 1; i < exp.length(); i++) {
                    if (exp.charAt(i) == '*') {
                        exp = replaceString(exp, i, j);
                        break;
                    }
                    if (j == exp.length() - 1) {
                        return false;
                    }
                }
            }
        }

        // if there any brackets left, then we ran out of stars
        return !exp.contains("(") && !exp.contains(")");
    }

    public static String replaceString(String exp, int i, int j) {
        return exp.substring(0, j) + "_" + exp.substring(j + 1, i) + "_" +
                (i == exp.length() - 1 ? "" : exp.substring(i + 1));
    }
}

- ruslanbes2 October 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I thought of a O(n) solution:

If I encounter a closing parentesis, the only thing I must ensure is there
was an opening parentesis before. If not, the expression isn't valid. An opening
parentesis can be a star as well. Stars I don't use, don't matter, they are null.

This doesn't account for too many open parentesis. But If I reverse the problem, I can
do the same again and find out, if all opening parentesis actually match a closing or
a "*".

It passes all the test cases and a few more. But the prove isn't that easy. It would, if
I used a stack and change the '*' into the according parentesis, but I think it's not
necessary. Any thoughts?

#include <iostream>
#include <string>

using namespace std;

bool validExpression(const string& expression) 
{
	string expr(expression); // make a modifiable copy of expr uses withing auxilary func.
	auto aux = [&expr]() -> bool {
		int openCtr = 0;
		int wildCtr = 0;
		for (char& c : expr) {
			if (c == '(') {
				c = ')';
				openCtr++;
			} else if (c == ')') {
				c = '(';
				if (openCtr > 0) openCtr--; // match ')' to a '('
				else if (wildCtr > 0) wildCtr--; // match ')' to a '*'
				else return false; // can't match ')' to anyting, error
			} else if (c == '*') {
				wildCtr++;
			}
		}
		reverse(expr.begin(), expr.end()); // reverse string
		return true;
	};

	return aux() && aux();
}


int main()
{
	cout << "TC1: " << (validExpression("(*)") == true) << endl;
	cout << "TC2: " << (validExpression("((*)") == true) << endl;
	cout << "TC3: " << (validExpression("((*))") == true) << endl;
	cout << "TC4: " << (validExpression("((*)))") == true) << endl;
	cout << "TC5: " << (validExpression("((*))))") == false) << endl;
	cout << "TC6: " << (validExpression("*((*))))") == true) << endl;
	cout << "TC7: " << (validExpression("(*((*))))") == true) << endl;
	cout << "TC8: " << (validExpression("(*)(*)(**") == true) << endl;
	cout << "TC9: " << (validExpression("(*)(*)(***") == true) << endl;
	cout << "TC10: " << (validExpression("((*)(*)(***") == true) << endl;
	cout << "TC11: " << (validExpression("(()(*)(") == false) << endl;
	cout << "TC12: " << (validExpression("(()(*)(") == false) << endl;
	cout << "TC13: " << (validExpression("****()))))") == true) << endl;
	cout << "TC12: " << (validExpression("") == true) << endl;
	cout << "TC13: " << (validExpression("()") == true) << endl;
	cout << "TC14: " << (validExpression("(*)") == true) << endl;
	cout << "TC15: " << (validExpression("(*)(*)") == true) << endl;
	cout << "TC16: " << (validExpression("*") == true) << endl;
	cout << "TC17: " << (validExpression("**") == true) << endl;
	cout << "TC18: " << (validExpression("*)") == true) << endl;
	cout << "TC19: " << (validExpression("*(((()())()))())") == true) << endl;
	cout << "TC20: " << (validExpression("*()(") == false) << endl;
	cout << "TC21: " << (validExpression("**()(") == false) << endl;
	cout << "TC22: " << (validExpression("**(**)*(") == false) << endl;
	cout << "TC23: " << (validExpression(")**") == false) << endl;
	cout << "TC24: " << (validExpression("****()))))") == true) << endl;
	cout << "TC25: " << (validExpression("****())))") == true) << endl;
	cout << "TC26: " << (validExpression("****())))))") == false) << endl;
	cout << "TC27: " << (validExpression("***********************(((((()") == false) << endl;
	cout << "TC28: " << (validExpression("*(((()())())())") == true) << endl;
	cout << "TC29: " << (validExpression("(((()())()))())") == false) << endl;
	cout << "TC30: " << (validExpression("*(((()())())*())") == true) << endl;
}

- Chris October 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't fail *()(, but failed *((*

- failed test case "*((*" February 19, 2019 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

My approach solves it in O(n).

Please mention if any issue with the approach or time complexity.

Thanks ruslanbes2 for the test cases. I have used the same for testing.

Steps:

1. Scan the string and count he number of occurrences of '(', ')' and '*'
If there is a ')' before '(' or '*' then it is not valid.

2. Check if the condition (Math.abs(rightParen - leftParen) <= starParen) satisfies.
The condition is to check if we have enough wild card *s to validate. Example *()))

3. Check if there is no *s in the String and both '(' and ')' should be equal.

4. Again scan the same string and decrement the number of occurrences calculated in the step 1.
Before decrementing check if '*' is 0 and '(' is greater than ')' then the string is not valid.
After decrementing check if ')' and '*' are 0 and '(' is greater than 0 then the string is not valid.

public class CheckParanthesis {

	private static boolean checkParenthesis(String str) {
		int leftParen = 0;
		int rightParen = 0;
		int starParen = 0;
		boolean isValid = true;

		// Group and Count character in the string
		for (char c : str.toCharArray()) {
			if (c == '(')
				leftParen++;
			else if (c == ')')
				rightParen++;
			else if (c == '*')
				starParen++;

			/**
			 * Return false when String starts with ) when there is no ( or *
			 **/
			if (leftParen == 0 && starParen == 0 && rightParen > 0) {
				return false;
			}
		}

		/**
		 * When there is shortage in * and either ( or ) more then return false
		 **/
		if (!(Math.abs(rightParen - leftParen) <= starParen))
			return false;

		/** if * is null and ( & ) is not equal then return false **/
		if ((starParen == 0 && rightParen != leftParen)) {
			return false;
		}

		// Scan the String and decrement the values
		for (char c : str.toCharArray()) {
			/** When * is empty but ( is greater than ) return false **/
			if (starParen == 0 && (leftParen > rightParen)) {
				return false;
			}

			if (c == '(')
				leftParen--;
			else if (c == ')')
				rightParen--;
			else if (c == '*')
				starParen--;

			/** When the string has no ) but still have ( then return false **/
			if ((rightParen == 0 && starParen == 0 && leftParen > 0)) {
				return false;
			}
		}
		return isValid;
	}

	/**
	 * Test Cases
	 */
	@Test
	public void checkParenthesis() {
		assertTrue(CheckParanthesis.checkParenthesis(""));
		assertTrue(CheckParanthesis.checkParenthesis("()"));
		assertTrue(CheckParanthesis.checkParenthesis("(*)"));
		assertTrue(CheckParanthesis.checkParenthesis("(*)(*)"));

		assertTrue(CheckParanthesis.checkParenthesis("*"));
		assertTrue(CheckParanthesis.checkParenthesis("**"));
		assertTrue(CheckParanthesis.checkParenthesis("*)"));

		assertTrue(CheckParanthesis.checkParenthesis("*(((()())()))())"));

		assertFalse(CheckParanthesis.checkParenthesis("*()("));
		assertFalse(CheckParanthesis.checkParenthesis("**()("));
		assertFalse(CheckParanthesis.checkParenthesis("**(**)*("));
		assertFalse(CheckParanthesis.checkParenthesis(")**"));
		assertTrue(CheckParanthesis.checkParenthesis("****()))))"));
		assertTrue(CheckParanthesis.checkParenthesis("****())))"));
		assertFalse(CheckParanthesis.checkParenthesis("****())))))"));
		assertFalse(CheckParanthesis.checkParenthesis("***********************(((((()"));

		assertFalse(CheckParanthesis.checkParenthesis("(((()())()))())"));
		assertTrue(CheckParanthesis.checkParenthesis("*(((()())())*())"));
	}

	@Test
	public void checkParenthesis5() {
		assertTrue(CheckParanthesis.checkParenthesis("(*)(*)(**"));
	}

	@Test
	public void checkParenthesis10() {
		assertTrue(CheckParanthesis.checkParenthesis("*(((()())())())"));
	}

}

- iLoveCoding85 October 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

After posting the soln above, seems that we can have O(n2) approach, using additional space which is much cleaner -

public static void main(String[] args){
  	String str = "*)(*";
    System.out.println(isValid(str));
  }
  
  public static boolean isValid(String str){
  	char[] carr = str.toCharArray();
    int n = carr.length;
    Stack<Character> stack = new Stack<Character>();
    Queue<Character> queue = new LinkedList<Character>();
    int i = 0;
    while(i < n){
      if(carr[i] == '(' || carr[i] == '*')
      	stack.push(carr[i]);
      else{
          while(!stack.isEmpty()){
          	char c = stack.pop();
            if(c == '(')
              continue;
            else
              queue.add(c);
          }
        }
      	
        if(!queue.isEmpty() && stack.isEmpty()){
          while(!queue.isEmpty()){
          	stack.add(queue.poll());
          }
        }
      	i++;
      }
    
      boolean valid = true;
      int countWild = 0;
      if(!stack.isEmpty()){
		char c = stack.pop();
        if(c == '*'){
          valid = true;
          countWild++;
        }else if(c == ')'){
        	valid = false;
        }else if(c == '(' && countWild > 0){
        	countWild--;
        }else if(c == '(' && countWild <= 0){
        	return false;
        }
      }
      return valid;
  }

- sudip.innovates October 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My idea is first to remove all paired brackets. After that, we get something like ")))((". Then, to count how many stars and how many closing brackets are there to the left of each closing bracket. And the same logic backward pass for opening brackets.

bool Valid(string s)
{
	stack<int> st;
	for (int i = 0; i < s.size(); ++i) {
		if (s[i] == '(') {
			st.push(i);
		} else if (s[i] == ')') {
			if (!st.empty()) {
				s[i] = ' ';
				s[st.top()] = ' ';
				st.pop();
			}
		}
	}
	int stars = 0;
	int closings = 0;
	for (int i = 0; i < s.size(); ++i) {
		if (s[i] == '*') {
			++stars;
		} else if (s[i] == ')') {
			++closings;
		}
		if (closings > stars) {
			return false;
		}
	}

	stars = 0;
	int openings = 0;
	for (int i = s.size() - 1; i >= 0; --i) {
		if (s[i] == '*') {
			++stars;
		} else if (s[i] == '(') {
			++openings;
		}
		if (openings > stars) {
			return false;
		}
	}

	return true;
}

- Alex October 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static boolean isValid(String input) {
    	if (input == null || input.length() == 0) return false;
    	int count = 0;
    	int starCount = 0;
    	char arr[] = input.toCharArray();
    	for(char c : arr) {
    		switch(c) {
    			case ')':
    				count--;
    			break;
    
    			case '(':
    				count++;
    			break;
    
    			case '*':
    				starCount++;
    			break;
    
    		}
    	}
    	if (starCount == 0 && count == 0) return true;
    	if (count > 0) return (count - starCount) == 0;
    	if (count == 0) return Math.abs(count - starCount) % 2 == 0;
    	return false;
    }

- kaustubh deshmukh October 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
	 * Givens: 1- * can work as either opening or closing parenthis, or none.
	 * Required: Check for string validation,, this is usually a stack problem. In
	 * this case, it is a stack problem, and at every wild card we need to have
	 * three different options. For each option (,) or *, we need to make a branch.
	 * Backtracking problem.
	 * 
	 * Base case: location == string.length,, return test Stack General case:
	 * 
	 * @param args
	 */
	
	public static Stack<Character> stack = new Stack<>();
	public static void main(String[] args) {
		System.out.println(isValid("(((**)",0));
	}
	public static boolean isValid(String s, int location) {
		if (location >= s.length() - 1) {	
			if (s.charAt(location) == '*')
				return pushToStackAndTestThenPop(null) || pushToStackAndTestThenPop(')')
						|| pushToStackAndTestThenPop('(');
			else
				return pushToStackAndTestThenPop(s.charAt(location));
		} else {
			if (s.charAt(location) == '*') {
				// null condition, nothing to push
				if (isValid(s, location+1)) return true;
				else {
					stack.push('(');
					if (isValid(s, location+1))
						return true;
					else {
						stack.pop();//backtracking
						stack.push(')');
						return isValid(s,location+1);
					}
				}
			} else {
				stack.push(s.charAt(location));
				if (isValid(s, location+1)) return true;
				else {
					stack.pop();//backtracking
					return false;
				}
			}
		}
	}

	public static boolean pushToStackAndTestThenPop(Character c) {
		if (c == null)
			return testStack();
		else {
			stack.push(c);
			boolean result = testStack();
			stack.pop();
			return result;
		}
	}

	//traditional string stack problem
	public static boolean testStack() {
		String string="";
		for(int i=stack.size()-1; i>=0; i--) {
			string=stack.get(i)+string;
		}
		Stack<Character> test=new Stack<>();
		for(int i=0; i<string.length(); i++) {
			if(string.charAt(i)=='(') test.push('(');
			else if(string.charAt(i)==')') {
				if(test.isEmpty()||test.pop()!='(') return false;
			}
		}
		return test.isEmpty();
	}

- ahmed.abouhegaza October 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package swiggy;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class FindBalance {

public static void main(String args[]) {
System.out.println(isValid("(*)(*)(**"));
}

static boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
Stack<Character> queue = new Stack<>();
int count=0;;
int countStar=0;
int i=0;
for (i = 0; i < s.length(); i++) {
if(s.charAt(i)=='(' || s.charAt(i) == '*') {
stack.push(s.charAt(i));
}
else {
boolean isFound=false;
while(!stack.isEmpty()) {
char c = stack.pop();
if(c=='(') {
isFound = true;
break;
}else {
queue.push(c);
}
}
while(!queue.isEmpty()) {
stack.push(queue.pop());
}
if(!isFound) {
stack.push(')');
}
}
}
int star = 0;
if(!stack.isEmpty()) {
while(!stack.isEmpty() && stack.peek()!=')') {
char c = stack.pop();
if(c=='(') {
if(star>0)
star--;
else
return false;
}
if(c=='*') {
star++;
}
}
star = 0;
while(!stack.isEmpty()) {
char c = stack.pop();
if(c==')') {
star++;
}
if(c=='*') {
star--;
}
}
if(star>0) {
return false;
}
}
while(!stack.isEmpty()) {
if(stack.pop()==')'||stack.pop()=='(') {
return false;
}
}
if(stack.isEmpty()) {
return true;
}
return false;
}
}

- Anonymous October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package swiggy;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class FindBalance {

	public static void main(String args[]) {
		System.out.println(isValid("(*)(*)(**"));
	}

	static boolean isValid(String s) {
		Stack<Character> stack = new Stack<Character>();
		Stack<Character> queue = new Stack<>();
		int count=0;;
		int countStar=0;
		int i=0;
		for (i = 0; i < s.length(); i++) {
			if(s.charAt(i)=='(' || s.charAt(i) == '*') {
				stack.push(s.charAt(i));
			}
			else {
				boolean isFound=false;
				while(!stack.isEmpty()) {
					char c = stack.pop();
					if(c=='(') {
						isFound = true;
						break;
					}else {
						queue.push(c);
					}
				}
				while(!queue.isEmpty()) {
					stack.push(queue.pop());
				}
				if(!isFound) {
					stack.push(')');
				}
			}
		}
		int star = 0;
		if(!stack.isEmpty()) {
			while(!stack.isEmpty() && stack.peek()!=')') {
				char c = stack.pop();
				if(c=='(') {
					if(star>0)
						star--;
					else
						return false;
				}
				if(c=='*') {
					star++;
				}
			}
			star = 0;
			while(!stack.isEmpty()) {
				char c = stack.pop();
				if(c==')') {
					star++;
				}
				if(c=='*') {
					star--;
				}
			}
			if(star>0) {
				return false;
			}
		}
		while(!stack.isEmpty()) {
			if(stack.pop()==')'||stack.pop()=='(') {
				return false;
			}
		}
		if(stack.isEmpty()) {
			return true;
		}
		return false;
	}
}

- Anonymous October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package swiggy;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class FindBalance {

	public static void main(String args[]) {
		System.out.println(isValid("(*)(*)(**"));
	}

	static boolean isValid(String s) {
		Stack<Character> stack = new Stack<Character>();
		Stack<Character> queue = new Stack<>();
		int count=0;;
		int countStar=0;
		int i=0;
		for (i = 0; i < s.length(); i++) {
			if(s.charAt(i)=='(' || s.charAt(i) == '*') {
				stack.push(s.charAt(i));
			}
			else {
				boolean isFound=false;
				while(!stack.isEmpty()) {
					char c = stack.pop();
					if(c=='(') {
						isFound = true;
						break;
					}else {
						queue.push(c);
					}
				}
				while(!queue.isEmpty()) {
					stack.push(queue.pop());
				}
				if(!isFound) {
					stack.push(')');
				}
			}
		}
		int star = 0;
		if(!stack.isEmpty()) {
			while(!stack.isEmpty() && stack.peek()!=')') {
				char c = stack.pop();
				if(c=='(') {
					if(star>0)
						star--;
					else
						return false;
				}
				if(c=='*') {
					star++;
				}
			}
			star = 0;
			while(!stack.isEmpty()) {
				char c = stack.pop();
				if(c==')') {
					star++;
				}
				if(c=='*') {
					star--;
				}
			}
			if(star>0) {
				return false;
			}
		}
		while(!stack.isEmpty()) {
			if(stack.pop()==')'||stack.pop()=='(') {
				return false;
			}
		}
		if(stack.isEmpty()) {
			return true;
		}
		return false;
	}
}

- Nil October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class FindBalance {

	public static void main(String args[]) {
		System.out.println(isValid("(*)(*)(**"));
	}

	static boolean isValid(String s) {
		Stack<Character> stack = new Stack<Character>();
		Stack<Character> queue = new Stack<>();
		int count=0;;
		int countStar=0;
		int i=0;
		for (i = 0; i < s.length(); i++) {
			if(s.charAt(i)=='(' || s.charAt(i) == '*') {
				stack.push(s.charAt(i));
			}
			else {
				boolean isFound=false;
				while(!stack.isEmpty()) {
					char c = stack.pop();
					if(c=='(') {
						isFound = true;
						break;
					}else {
						queue.push(c);
					}
				}
				while(!queue.isEmpty()) {
					stack.push(queue.pop());
				}
				if(!isFound) {
					stack.push(')');
				}
			}
		}
		int star = 0;
		if(!stack.isEmpty()) {
			while(!stack.isEmpty() && stack.peek()!=')') {
				char c = stack.pop();
				if(c=='(') {
					if(star>0)
						star--;
					else
						return false;
				}
				if(c=='*') {
					star++;
				}
			}
			star = 0;
			while(!stack.isEmpty()) {
				char c = stack.pop();
				if(c==')') {
					star++;
				}
				if(c=='*') {
					star--;
				}
			}
			if(star>0) {
				return false;
			}
		}
		while(!stack.isEmpty()) {
			if(stack.pop()==')'||stack.pop()=='(') {
				return false;
			}
		}
		if(stack.isEmpty()) {
			return true;
		}
		return false;
	}
}

- Nil October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For an input string of length n
Time Complexity : O(n)
Space complexity : O(1)

Solution:

public static boolean validate(final String input) {
        int leftParanthesesCounter = 0;
        int rightParanthesesCounter = 0;
        int starParanthesesCounter = 0;

        for (char character : input.toCharArray()) {

            if (character == '(') {
                leftParanthesesCounter++;
            } else if (character == ')') {
                rightParanthesesCounter++;
            } else if (character == '*') {
                starParanthesesCounter++;
            }

            if (rightParanthesesCounter > leftParanthesesCounter + starParanthesesCounter) {
                return false;
            } else if (rightParanthesesCounter > leftParanthesesCounter) {
                int delta = Math.min(starParanthesesCounter, rightParanthesesCounter - leftParanthesesCounter);
                starParanthesesCounter -= delta;
                leftParanthesesCounter += delta;
            }
        }

        if (leftParanthesesCounter != rightParanthesesCounter) {
            return false;
        }
        return true;
    }

- aditya.2ky October 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To solve this problem we can check if the string is balanced without take into account the stars. During the check we'll store the open parenthesis position in a stack and when we find a close parenthesis we extract the matching one (the open parenthesis) from the stack and replece both position on the string with empty string. This way if the string is already balanced the fina string will has only stars or nothing. If the string isn't balanced we will get a pattern where the close parenthesis are at left of the open parenthesis, something like this:

*))**))))***((((****((((****

Note: this pattern can have how many stars and parenthesis how we wish, but the condition previously mentioned will apply always (all close parenthesis are on the left of open parenthesis).

Now, we can iterate this string from left to right and assume the stars are open parenthesis until we get a real open parenthesis. We can have a counter to increment it when a star is recognize and decrement it when we find a close parenthesis. If we found a open parenthesis we reset the counter and start again but from the end of the string until the position of the first open parenthesis, again we increment the counter on stars and decrement on open parenthesis. If in any case during the iterations the counter gets a value < 0 we can say the string is balanced. This is the code:

public static Boolean isBalanced(String str){
	ArrayDeque<Integer> parenthesis = new ArrayDeque<>(str.length());
        ArrayDeque<Integer> bracket = new ArrayDeque<>(str.length());
        ArrayDeque<Integer> keys = new ArrayDeque<>(str.length());
	char[] seq = str.toCharArray();
	
	for(int i = 0; i < str.length(); i++){
		if(str.charAt(i) == '(') 
			parenthesis.push(i);
		else if(str.charAt(i) == ')'){
                    if(!parenthesis.isEmpty()){
			int j = parenthesis.pop();
			seq[i] = ' ';
			seq[j] = ' ';
                    }
		}
                else if(str.charAt(i) == '[') 
			bracket.push(i);
		else if(str.charAt(i) == ']'){
                    if(!bracket.isEmpty()){
			int j = bracket.pop();
			seq[i] = ' ';
			seq[j] = ' ';
                    }
		}
                else if(str.charAt(i) == '{') 
			keys.push(i);
		else if(str.charAt(i) == '}'){
                    if(!keys.isEmpty()){
			int j = keys.pop();
			seq[i] = ' ';
			seq[j] = ' ';
                    }
		}
 	}
	
	int count = 0;
        int i = 0;
	for(; i < seq.length; i++){
		if(seq[i] == '*') count++;
		else if(seq[i] == ')' || seq[i] == ']' || seq[i] == '}'){
			count --;
			if(count < 0) return false;
		}
		else if(seq[i] == '(' || seq[i] == '[' || seq[i] == '{'){
			count = 0;
			break;
		}
	}

	for(int j = seq.length - 1; j >= i; j--){
		if(seq[j] == '*') count++;
		else if(seq[j] == '(' || seq[i] == '[' || seq[i] == '{'){
			count--;
			if(count < 0) return false;
		}
	}
	return true;
    }

- leobelizquierdo October 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The basic idea of the algorithm :
1. Start from the end of the string
2. Check for the edge cases, i.e., the string starts with ')' or ends with '('
3. Maintain two stacks -- one for the closing braces - ')' and one for the star '*'
4. If the character in the string is ')' push it in the closeBrace stack
5. If the character in the string is '*' push it in the star stack
6. If the character in the string is '(', the following cases need to be considered :
--- If both the star and closeBrace stacks are empty, return false
--- If the closeBrace stack is not empty, pop an item from closeBrace
--- If the star stack is not empty, pop an item from star
7. At the end, we keep popping from star and closeBrace stacks until any one of them is empty
8. If closeBrace stack is not empty, this means the parantheses are not balanced, we return false
9. For other cases, we return true

Time complexity : O(n), space complexity : O(n)

public static boolean isBalanced(String s) {
		int start = s.length() - 1;
		if(start < 0)
			return true;
		if(s.charAt(0) == ')' || s.charAt(s.length() - 1) == '(')
			return false;
		Stack<Character> closeBrace = new Stack<>();
		Stack<Character> star = new Stack<>();
		while(start >= 0) {
			char ch = s.charAt(start);
			if(ch == '(') {
				if(star.isEmpty() && closeBrace.isEmpty())
					return false;
				if(!closeBrace.isEmpty())
				{
					closeBrace.pop();

				}
				else if(!star.isEmpty()) 
				{
					star.pop();
				}
			}
			else if(ch == ')')
			{
				closeBrace.push(ch);
			}
			else if(ch == '*')
			{
				star.push('*');
			}
			start--;
		}
		while(!star.isEmpty() && !closeBrace.isEmpty()) {
			star.pop();
			closeBrace.pop();
		}
		if(!closeBrace.isEmpty())
			return false;
		
		return true;
		
	}

- skeeter November 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.anton.parenthesis;

import java.rmi.UnexpectedException;
import java.util.Stack;

/**
 * Created by anton.ve on 11/8/2017.
 */
public class Parenthesis {
    public static boolean check(String input) throws UnexpectedException
    {
        int inputLen = input.length();
        if (inputLen == 0)
            return true;

        int starsCount             = 0;
        int starsAfterOpeningCount = 0;
        int parenthesisCount       = 0;

        for (int inputIndex = 0; inputIndex < inputLen; inputIndex++)
        {
            Character inputChar = input.charAt(inputIndex);

            if (inputChar == '(')
            {
                parenthesisCount++;
                starsAfterOpeningCount = 0;
            }
            else
                if (inputChar == ')')
                {
                    if (parenthesisCount == 0)
                    {
                        if (starsCount == 0)
                            return false;
                        else
                            starsCount--;
                    }
                    else
                        parenthesisCount--;
                }
                else
                    if (inputChar == '*')
                    {
                        starsCount++;
                        starsAfterOpeningCount++;
                    }
                    else
                        throw(new UnexpectedException("Unexpected input"));
        }

        return (starsAfterOpeningCount - parenthesisCount) >= 0;
    }
}


package com.anton.parenthesis;

import org.junit.Assert;
import org.junit.Test;

import java.rmi.UnexpectedException;

/**
 * Created by anton.ve on 11/8/2017.
 */
public class ParenthesisTest {
    @Test
    public void Test_Empty_Success() throws UnexpectedException
    {
        Assert.assertTrue(Parenthesis.check(""));
    }

    @Test
    public void Test_NoStars_Success() throws UnexpectedException
    {
        Assert.assertTrue(Parenthesis.check("((()))()"));
    }

    @Test
    public void Test_NoStars_Fail() throws UnexpectedException
    {
        Assert.assertFalse(Parenthesis.check("(()))()"));
    }

    @Test
    public void Test_NoStarsOpening_Fail() throws UnexpectedException
    {
        Assert.assertFalse(Parenthesis.check("(((("));
    }

    @Test
    public void Test_Stars_Succeeded() throws UnexpectedException
    {
        Assert.assertTrue(Parenthesis.check("((***))**(****)"));
    }

    @Test
    public void Test_ParenthesisMissing_Succeeded() throws UnexpectedException
    {
        Assert.assertTrue(Parenthesis.check("((***)))**(****)"));
    }

    @Test
    public void Test_StarsOpening_Fail() throws UnexpectedException
    {
        Assert.assertFalse(Parenthesis.check("*("));
    }

    @Test
    public void Test_StarsNotEnough_Fail() throws UnexpectedException
    {
        Assert.assertFalse(Parenthesis.check("**())))"));
    }

    @Test
    public void Test_CareerCup() throws UnexpectedException
    {
        Assert.assertTrue(Parenthesis.check(""));
        Assert.assertTrue(Parenthesis.check("()"));
        Assert.assertTrue(Parenthesis.check("(*)"));
        Assert.assertTrue(Parenthesis.check("(*)(*)"));

        Assert.assertTrue(Parenthesis.check("*"));
        Assert.assertTrue(Parenthesis.check("**"));
        Assert.assertTrue(Parenthesis.check("*)"));

        Assert.assertTrue(Parenthesis.check("*(((()())()))())"));

        Assert.assertFalse(Parenthesis.check("*()("));
        Assert.assertFalse(Parenthesis.check("**()("));
        Assert.assertFalse(Parenthesis.check("**(**)*("));
        Assert.assertFalse(Parenthesis.check(")**"));
        Assert.assertTrue(Parenthesis.check("****()))))"));
        Assert.assertTrue(Parenthesis.check("****())))"));
        Assert.assertFalse(Parenthesis.check("****())))))"));
        Assert.assertFalse(Parenthesis.check("***********************(((((()"));

        Assert.assertTrue(Parenthesis.check("(*)(*)(**"));
        Assert.assertTrue(Parenthesis.check("*(((()())())())"));

        Assert.assertFalse(Parenthesis.check("(((()())()))())"));
        Assert.assertTrue(Parenthesis.check("*(((()())())*())"));

        Assert.assertTrue(Parenthesis.check("(*)"));
        Assert.assertTrue(Parenthesis.check("((*)"));
        Assert.assertTrue(Parenthesis.check("((*))"));
        Assert.assertTrue(Parenthesis.check("((*)))"));
        Assert.assertFalse(Parenthesis.check("((*))))"));
        Assert.assertTrue(Parenthesis.check("*((*))))"));
        Assert.assertTrue(Parenthesis.check("(*((*))))"));
        Assert.assertTrue(Parenthesis.check("(*)(*)(**"));
        Assert.assertTrue(Parenthesis.check("(*)(*)(***"));
        Assert.assertTrue(Parenthesis.check("((*)(*)(***"));
        Assert.assertFalse(Parenthesis.check("(()(*)("));
        Assert.assertFalse(Parenthesis.check("(()(*)("));
        Assert.assertTrue(Parenthesis.check("****()))))"));
        Assert.assertTrue(Parenthesis.check(""));
        Assert.assertTrue(Parenthesis.check("()"));
        Assert.assertTrue(Parenthesis.check("(*)"));
        Assert.assertTrue(Parenthesis.check("(*)(*)"));
        Assert.assertTrue(Parenthesis.check("*"));
        Assert.assertTrue(Parenthesis.check("**"));
        Assert.assertTrue(Parenthesis.check("*)"));
        Assert.assertTrue(Parenthesis.check("*(((()())()))())"));
        Assert.assertFalse(Parenthesis.check("*()("));
        Assert.assertFalse(Parenthesis.check("**()("));
        Assert.assertFalse(Parenthesis.check("**(**)*("));
        Assert.assertFalse(Parenthesis.check(")**"));
        Assert.assertTrue(Parenthesis.check("****()))))"));
        Assert.assertTrue(Parenthesis.check("****())))"));
        Assert.assertFalse(Parenthesis.check("****())))))"));
        Assert.assertFalse(Parenthesis.check("***********************(((((()"));
        Assert.assertTrue(Parenthesis.check("*(((()())())())"));
        Assert.assertFalse(Parenthesis.check("(((()())()))())"));
        Assert.assertTrue(Parenthesis.check("*(((()())())*())"));
    }
}

- Anton77 November 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isBalanced(String string) {
    char[] chars = string.toCharArray();
    int length = chars.length;

    int[] pitfalls = new int[length];
    int[] parenthesis = new int[length];

    int numParenthesis = 0;
    int numPitfalls = 0;

    if (length == 0) {
      return true;
    }

    if (chars[0] == ')' || chars[length-1] == '(') {
      return false;
    }

    for (int index = 0; index < length; index++) {
      char currChar = chars[index];
      
      if (currChar == '(') {
        parenthesis[numParenthesis++] = index;        
        pitfalls[index] = numPitfalls;
      } else if (currChar == ')') {
        if (numParenthesis > 0) {
          parenthesis[numParenthesis--] = -1;
        } else if (numPitfalls == 0) {
          return false;
        } else {
          numPitfalls--;
        }
        pitfalls[index] = numPitfalls;
      } else if (currChar == '*') {
        pitfalls[index] = ++numPitfalls;
      }
    }

    for (int parents = numParenthesis -1; parents >= 0; parents--) {
      int index = parenthesis[parents];
      if ( (numPitfalls - pitfalls[index]) == 0) {
        return false;
      }

      numPitfalls--;      
    }

    return true;
  }

- Anonymous November 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isBalanced(String string) {
char[] chars = string.toCharArray();
int length = chars.length;

int[] pitfalls = new int[length];
int[] parenthesis = new int[length];

int numParenthesis = 0;
int numPitfalls = 0;

if (length == 0) {
return true;
}

if (chars[0] == ')' || chars[length-1] == '(') {
return false;
}

for (int index = 0; index < length; index++) {
char currChar = chars[index];

if (currChar == '(') {
parenthesis[numParenthesis++] = index;
pitfalls[index] = numPitfalls;
} else if (currChar == ')') {
if (numParenthesis > 0) {
parenthesis[numParenthesis--] = -1;
} else if (numPitfalls == 0) {
return false;
} else {
numPitfalls--;
}
pitfalls[index] = numPitfalls;
} else if (currChar == '*') {
pitfalls[index] = ++numPitfalls;
}
}

for (int parents = numParenthesis -1; parents >= 0; parents--) {
int index = parenthesis[parents];
if ( (numPitfalls - pitfalls[index]) == 0) {
return false;
}

numPitfalls--;
}

return true;
}

- Daniel Almeida November 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;
import java.util.Stack;

public class ParanthesisBalance {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String str = scanner.nextLine();
		scanner.close();
		System.out.println(checkIfValidParantheses(str.toCharArray()));
	}

	private static boolean checkIfValidParantheses(char[] str) {
		Stack<Integer> openParanthesesStack = new Stack<>();
		Stack<Integer> closeParanthesesStack = new Stack<>();
		Stack<Integer> asterixParanthesesStack = new Stack<>();
		for (int i = 0; i < str.length; i++) {
			if (str[i] == '(') {
				openParanthesesStack.push(i);
			} else if (str[i] == ')') {
				if (!openParanthesesStack.isEmpty()) {
					str[openParanthesesStack.pop()] = '.';
				} else {
					closeParanthesesStack.push(i);
				}
			} else {
				asterixParanthesesStack.push(i);
			}
		}
		if (openParanthesesStack.isEmpty() && closeParanthesesStack.isEmpty()) {
			return true;
		} else if (!openParanthesesStack.isEmpty()) {
			if (asterixParanthesesStack.size() < openParanthesesStack.size()) {
				return false;
			}
			while (!openParanthesesStack.isEmpty()) {
				if (openParanthesesStack.pop() > asterixParanthesesStack.pop()) {
					return false;
				}
			}
			return true;
		} else {
			if (asterixParanthesesStack.size() < closeParanthesesStack.size()) {
				return false;
			}
			while (!closeParanthesesStack.isEmpty()) {
				if (closeParanthesesStack.pop() < asterixParanthesesStack.pop()) {
					return false;
				}
			}
			return true;
		}
	}

}

- PATIRA.NISHU December 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isBalanced(String s) {
        Stack<Integer> obIdxStack = new Stack<>(), starIdxStack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '*') {
                starIdxStack.push(i);
            } else if (ch == '(') {
                obIdxStack.push(i);
            } else {
                if (obIdxStack.size() > 0) {
                    obIdxStack.pop();
                } else {
                    if (starIdxStack.isEmpty()) {
                        return false;
                    }
                    starIdxStack.pop();
                }
            }
        }

        while (!obIdxStack.isEmpty()) {
            int top1 = obIdxStack.pop();
            if (starIdxStack.isEmpty() || starIdxStack.peek() < top1) {
                return false;
            }
            starIdxStack.pop();
        }

        return true;
    }

- Jeebs February 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Checking if an expression is balanced can be done in O(n) by using a stack and it's a very well known problem. For this problem we can extend the idea and use backtracking to handle the wildcards. Time complexity would be O(3^n).

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	public static boolean isBalanced(String exp){
		int n = exp.length();
		char[] expArray = new char[n];
		for (int i = 0; i < n; i++){
			expArray[i] = exp.charAt(i);
		}
		return helper(expArray, 0, new Stack<Character>());
	}

	public static boolean helper(char[] exp, int index, Stack<Character> stack){
		int n = exp.length;
		if (index == n){
			return stack.isEmpty();
		}
		else {
			char c = exp[index];
			if (c == '('){
				stack.push(c);
				boolean result = helper(exp, index + 1, stack);
				stack.pop();
				return result;
			}
			else if (c == ')'){
				if (stack.isEmpty()){
					return false;
				}
				stack.pop();
				boolean result = helper(exp, index + 1, stack);
				stack.push(c);
				return result;
			}
			else{
				// c == '*'
			}
			if (helper(exp, index + 1, stack)){
				return true;
			}
			exp[index] = '(';
			if (helper(exp, index, stack)){
				return true;
			}
			exp[index] = ')';
			return helper(exp, index, stack);
		}
	}

	public static void main (String[] args){
		System.out.println(isBalanced("(*)(*)(**"));
	}
}

- Anonymous October 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

boolean checkParenthesis(String str) {
		int lp = 0;
		int rp = 0;
		int sp = 0;
		boolean isValid = true;
		
		for(char c : str.toCharArray()){
			if(c == '(') lp++;
			else if(c == ')') rp++;
			else if(c == '*') sp++;
		}
		
		for(char c : str.toCharArray()){
			if(c == '(') lp--;
			else if(c == ')') rp--;
			else if(c == '*') sp--;
		}
		
		if((lp==0 && sp==0 && rp>0) || (rp==0 && sp== 0 && lp>0) || (lp==0 && rp== 0 && sp>0)){
			isValid = false;
		}
		
		return isValid;
	}

- ilovecoding85 October 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Brute Force -

public static void main(String[] args) {
		String str = "(*)(*)(**";
		char[] carr = str.toCharArray();
		System.out.println(validString(carr, 0, false));
	}

	// (*)(*)(**
	public static boolean validString(char[] carr, int i, boolean valid) {
		int n = carr.length;

		Stack<Character> stack = new Stack<Character>();
		while (i < n) {
			if (carr[i] == '(' || carr[i] == ' ')
				stack.push(carr[i]);
			else if (carr[i] == ')') {
				while (!stack.isEmpty()) {
					char c = stack.pop();
					if (c == ' ')
						continue;
					else if (c == ')')
						return false;
					else
						break;
				}
			} else if (carr[i] == '*') {
				carr[i] = '(';
				valid |= validString(carr, 0, valid);
				carr[i] = ')';
				valid |= validString(carr, 0, valid);
				carr[i] = ' ';
				valid |= validString(carr, 0, valid);
				carr[i] = '*';
			}
			i++;
		}
		while (!stack.isEmpty() && stack.peek() == ' ')
			stack.pop();
		if (stack.isEmpty())
			valid = true;
		else if(!valid)
			valid = false;
		return valid;
	}

- sudip.innovates October 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The most important thing is to know what are the exact rules of using the wildcard character.

Assumptions:
1. wildcard max count sequentially is 2.
2. wildcard can open, close or be inside parenthesis.
3. if a wildcard is used to close parenthesis then it should be used twice, like in the example.

package com.cracking.amazon;

import java.util.EmptyStackException;
import java.util.Stack;

public class ValidateParenthesisStr {
	
	public static enum Parenthesis {
		REGULAR( '(', ')' ),
		SQUARE( '[', ']' ),
		CURLED( '{', '}' ),
		WILDCARD( '*', '*');
		
		Parenthesis(char openChar, char closeChar) {
			this.openChar = openChar;
			this.closeChar = closeChar;
		}
		
		public char openChar;
		public char closeChar;
		
		public boolean isParenthesis(char ch) {
			return this.openChar == ch || this.closeChar == ch;
		}
	}
	
	public static final String input = "(*)(*)(*){**";
	
	public static void main(String[] args) {
		String output = String.format("Input = %s\nValidation = %s\n", input,validate(input));
		System.out.println(output);
	}
	
	public static boolean validate(String input) {
		Stack<Parenthesis> parenthesisStack = new Stack<Parenthesis>();
		for(int i=0; i<input.length(); i++) {
			char ch = input.charAt(i);
			Parenthesis ps = getParenthesis(ch);
			
			if(ps == null) return false;
			if(ps == Parenthesis.WILDCARD && !parenthesisStack.isEmpty() && parenthesisStack.peek() == Parenthesis.WILDCARD) {
				// 2 wildcards sequentially
				parenthesisStack.pop(); //pop wildcard
				if(!parenthesisStack.isEmpty()) parenthesisStack.pop(); //pop open char if exist
				continue;
			}
			
			if(ch == ps.openChar) {
				parenthesisStack.push(ps);
				continue;
			}
			
			try {
				Parenthesis openP = parenthesisStack.pop();
				if(openP == ps) {
					//No action needed
				}else if(openP == Parenthesis.WILDCARD && parenthesisStack.isEmpty()) {
					//No action needed
				}else if(openP == Parenthesis.WILDCARD && parenthesisStack.peek() == ps) {
					openP = parenthesisStack.pop();
				}else {
					return false;
				}
			}catch(EmptyStackException e) {
				return false;
			}
		}

		return parenthesisStack.isEmpty();
	}
	
	public static Parenthesis getParenthesis(char ch) {
		if( Parenthesis.REGULAR.isParenthesis(ch) ) {
			return Parenthesis.REGULAR;
		}
		if( Parenthesis.SQUARE.isParenthesis(ch) ) {
			return Parenthesis.SQUARE;
		}
		if( Parenthesis.CURLED.isParenthesis(ch) ) {
			return Parenthesis.CURLED;
		}
		if( Parenthesis.WILDCARD.isParenthesis(ch) ) {
			return Parenthesis.WILDCARD;
		}
		
		return null;
	}

}

- ProTechMulti October 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote
public class StringOfParenthesis { static char c; static int roundParen = 0; static int squareParen = 0; static int otherParent = 0; static int star = 0; public static void main(String[] args) { // TODO Auto-generated method stub if(isStringValid("ajnfajk*{}]]****[[{{{{{nfj)()")){ System.out.println("String is valid"); } else { System.out.println("String is not valid"); } } private static Boolean isStringValid (String validateString) { for(int i = 0; i< validateString.length(); i++){ c = validateString.charAt(i); if(c == '('){ roundParen++; } else if(c == ')') { roundParen--; } else if(c == '{') { otherParent++; } else if(c == '}') { otherParent--; } else if(c == '[') { squareParen++; } else if(c == ']') { squareParen--; } else if(c == '*') { star++; } } System.out.println("roundParen: "+roundParen + " otherParent: "+otherParent + " squareParen: "+squareParen + " star: "+ star); if((roundParen != 0 || roundParen != 0 || roundParen != 0) && star ==0 ){ return false; } if(roundParen != 0){ if (roundParen > 0){ star = star - roundParen; } else { star = star + roundParen; } } if(squareParen != 0){ if (squareParen > 0){ star = star - squareParen; } else { star = star + squareParen; } } if(otherParent != 0) { if (otherParent > 0){ star = star - otherParent; } else { star = star + otherParent; } } if(star < 0) { return false; } return true; } } - Dhruval Patel October 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote
public class StringOfParenthesis { static char c; static int roundParen = 0; static int squareParen = 0; static int otherParent = 0; static int star = 0; public static void main(String[] args) { // TODO Auto-generated method stub if(isStringValid("ajnfajk*{}]]****[[{{{{{nfj)()")){ System.out.println("String is valid"); } else { System.out.println("String is not valid"); } } private static Boolean isStringValid (String validateString) { for(int i = 0; i< validateString.length(); i++){ c = validateString.charAt(i); if(c == '('){ roundParen++; } else if(c == ')') { roundParen--; } else if(c == '{') { otherParent++; } else if(c == '}') { otherParent--; } else if(c == '[') { squareParen++; } else if(c == ']') { squareParen--; } else if(c == '*') { star++; } } System.out.println("roundParen: "+roundParen + " otherParent: "+otherParent + " squareParen: "+squareParen + " star: "+ star); if((roundParen != 0 || roundParen != 0 || roundParen != 0) && star ==0 ){ return false; } if(roundParen != 0){ if (roundParen > 0){ star = star - roundParen; } else { star = star + roundParen; } } if(squareParen != 0){ if (squareParen > 0){ star = star - squareParen; } else { star = star + squareParen; } } if(otherParent != 0) { if (otherParent > 0){ star = star - otherParent; } else { star = star + otherParent; } } if(star < 0) { return false; } return true; } } - Dhruval Patel October 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote
{{{public class StringOfParenthesis { static char c; static int roundParen = 0; static int squareParen = 0; static int otherParent = 0; static int star = 0; public static void main(String[] args) { // TODO Auto-generated method stub if(isStringValid("ajnfajk*{}]]****[[{{{{{nfj)()")){ System.out.println("String is valid"); } else { System.out.println("String is not valid"); } } private static Boolean isStringValid (String validateString) { for(int i = 0; i< validateString.length(); i++){ c = validateString.charAt(i); if(c == '('){ roundParen++; } else if(c == ')') { roundParen--; } else if(c == '{') { otherParent++; } else if(c == '}') { otherParent--; } else if(c == '[') { squareParen++; } else if(c == ']') { squareParen--; } else if(c == '*') { star++; } } System.out.println("roundParen: "+roundParen + " otherParent: "+otherParent + " squareParen: "+squareParen + " star: "+ star); if((roundParen != 0 || roundParen != 0 || roundParen != 0) && star ==0 ){ return false; } if(roundParen != 0){ if (roundParen > 0){ star = star - roundParen; } else { star = star + roundParen; } } if(squareParen != 0){ if (squareParen > 0){ star = star - squareParen; } else { star = star + squareParen; } } if(otherParent != 0) { if (otherParent > 0){ star = star - otherParent; } else { star = star + otherParent; } } if(star < 0) { return false; } return true; } } }}} - Dhruval Patel October 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <stack>
#include <iostream>
#include <string>

void main()
{
	string teststrings[] = {		"*)",
							"()",
							"(*)(*)",
							"",
							"(*)",
							"*",
							"**",
							"*(((()())()))())",
							"*()(",
							"**()(",
							"**(**)*(",
							")**",
							"****()))))",
							"****())))",
							"****())))))",
							"***********************(((((()" };

	
	string valid[] = { "Not Valid", "Valid" };
	for each (string var in teststrings)
	{
		bool Res = ValidateParenthesis_withwideChar(var);
		cout << var << "\t" << valid[Res] << "\n";
	}
}
	static bool ValidateParenthesis_withwideChar(string str)
	{
		bool valid = true;
		stack<char> *Left_Parenthesis = new stack<char>();
		stack<char> *stars = new stack<char>();
		char *y = &str[0];
		while (*y) {
			if (*y == '(')
			{
				Left_Parenthesis->push(*y);
			}
			else if(*y == '*')
			{
				stars->push(*y);
			}
			else if (*y == ')')
			{
				//  Both stacks are Empty
				if (Left_Parenthesis->empty() && stars->empty())
				{
					return false;
				}
				//  Left is not
				else if(!Left_Parenthesis->empty())
				{
					Left_Parenthesis->pop();
				}
				//  Left is Empty and Stars is not
				else if(Left_Parenthesis->empty() && !stars->empty())
				{
					stars->pop();
				}

			}
			y++;
		}
		return Left_Parenthesis->empty();
	}

- Anonymous October 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I just submitted a code but it did not show up

- Mustafa October 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int low = 0, high =0;

for(char ch:s.toCharArray()){

low += ch == '('? 1:-1;
high += ch != ')'? 1:-1;
if(high<0) break;
low = Math.max(0,low);
}
return low ==0;

- Anonymous November 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

boolean checkParenthesis(String str) {
int lp = 0;
int rp = 0;
int sp = 0;
boolean isValid = true;

for(char c : str.toCharArray()){
if(c == '(') lp++;
else if(c == ')') rp++;
else if(c == '*') sp++;
}

for(char c : str.toCharArray()){
if(c == '(') lp--;
else if(c == ')') rp--;
else if(c == '*') sp--;
}

if((lp==0 && sp==0 && rp>0) || (rp==0 && sp== 0 && lp>0) || (lp==0 && rp== 0 && sp>0)){
isValid = false;
}

return isValid;
}

- ilovecoding85 October 16, 2017 | 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