Walmart Labs Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
I wrote pretty much the same code (used switch case instead of if-else).
However this has a bug.
Case "a(b" is not handled.
Before you return the maxOpenParen, you need to check openParenCount is 0 or not. If not zero throw the IllegalArgumentException.
Otherwise good :)
public static int getMaxParanthesisDepth(String str){
int maxDepth=0;
int potentialMaxDepth=0;
int curDepth = 0;
for(int i=0; i<str.length(); ++i ){
//left brace
if(str.charAt(i) == '('){
curDepth++;
potentialMaxDepth++;
}
//right brace
else if(str.charAt(i) == ')')
{
curDepth--;
//unmatched right brace
if(curDepth < 0){
System.out.println("unmatched brace");
maxDepth = -1;
break;
}
//one nest is processed
if(curDepth == 0){
if(potentialMaxDepth > maxDepth){
maxDepth = potentialMaxDepth;
potentialMaxDepth=0;
}
}
}
}
////unmatched left brace
if(curDepth != 0){
System.out.println("Unmatched braces");
return -1;
}
else return maxDepth;
}
Here is my solution. The standard approach is to use stack.
import java.util.Stack;
public class StringUtilities {
public static int nestedParenthesesDepth(String input) throws IllegalArgumentException{
Stack<Character> stack = new Stack<Character>();
int depth = 0;
int maxDepth = 0;
for(int i=0; i<input.length();i++){
if (input.charAt(i)=='(') {
stack.push(input.charAt(i));
depth++;
}
if(maxDepth<depth) maxDepth = depth;
if (input.charAt(i)==')') {
stack.pop();
depth--;
}
}
if(stack.size()>0) throw new IllegalArgumentException();
return maxDepth;
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package Careercup;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.lang.IllegalArgumentException;
/**
*
* @author
*/
public class CountBracketBalance {
static BufferedReader br;
static StringTokenizer st;
static int head=0,N=0,count=0;
static ArrayList<Character> queue=new ArrayList<Character>();
public static void init() throws IOException
{
if(st==null)
st=new StringTokenizer(br.readLine().replace("", " "));
}
public static void push(Character ch)
{
if(N>=queue.size()) //cases where N==arraylist.size
{
queue.ensureCapacity(queue.size()*2);
for(int i=N+1;i<queue.size();i++)
queue.add(null);
}
//stack.set(N++, ch);
queue.add(N++, ch);
}
public static Character pop()
{
if(queue.isEmpty())
{ System.err.println("Underflow operation requested, exiting");
System.exit(0); }
Character temp=queue.get(head);
queue.set(head, null);
head++;
N--;
return temp;
}
public static void main(String args[]) throws IOException
{
int maxcount=0;
br=new BufferedReader(new InputStreamReader(System.in));
init();
while(st.hasMoreTokens())
{
//push(st.nextToken().charAt(0));
String temp=st.nextToken();
push(temp.charAt(0));
}
while(N>0)
{
Character ch=pop();
if(ch=='(')
{ count++;
maxcount=Math.max(maxcount, count);}
if(ch==')')
count--;
if(count<0)
throw new IllegalArgumentException();
}
if(count!=0)
throw new IllegalArgumentException();
System.out.println(maxcount);
}
}
Edit: added fix to catch "a(b" cases. Thanks anonymous and JSDUDE
- zortlord June 04, 2015