## Walmart Labs Interview Question

• 0

Country: United States

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

This reminded be of a nasty problem of calculating or possible parenthesis based on an integer.

``````public static int CountMaxParenthesis(string S)
{
if(S == null)
throw new ArgumentNullException();

int count = 0;
int max = 0;
for(int i = 0; i < S.Length; i++)
{
char s = S[i];
if(s == '(')
{
count++;
if(count > max)
{
max = count;
}
}
else if(s == ')')
{
count--;
}
}

if(count != 0)
throw new ArgumentException(
"Parameter S does not have a balanced parenthesis nesting");

return max;
}``````

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

This solve was something I was trying for. I like the solve, except that it does not take care of the input= ")()(" or "()(("
So I debugged and fixed it this way.

``````public static void main(String args[]){
//		System.out.println(nestedParenthesisDepth("abc(123(xyz))m(((n)))o"));
System.out.println(nestedParenthesisDepth(")()("));
//		System.out.println(nestedParenthesisDepth("()()()()("));
//		System.out.println(nestedParenthesisDepth("((()))()()"));
}

/**
* Count the maximum depth of parenthesis nesting, i.e. "abc(123(xyz))m(((n)))o" -> 3.
*
* @param input
*            any string
* @return deepest parenthesization level
* @throws IllegalArgumentException
*             if input is null or contains a mismatch "a)b(c" or "a(b"
*/
public static int nestedParenthesisDepth(String input)
throws IllegalArgumentException {
int maxcount = 0;
int par_count = 0;

for(int i=0; i<input.length(); i++){
if(input.charAt(i) == '('){
par_count++;
if(par_count > maxcount){
maxcount = par_count;
}
}else if(input.charAt(i) == ')'){
if(par_count > 0){
par_count--;
}
}
}
if(par_count!=0){
throw new IllegalArgumentException();
}
return maxcount;
}

}``````

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

``````public static void main(String args[]){
System.out.println(nestedParenthesisDepth("abc(123(xyz))m(((n)))o"));
System.out.println(nestedParenthesisDepth(")()("));
System.out.println(nestedParenthesisDepth("()()()()("));
System.out.println(nestedParenthesisDepth("((()))()()"));
}

public static int nestedParenthesisDepth(String input)
throws IllegalArgumentException {
int maxcount = 0;
int par_count = 0;

for(int i=0; i<input.length(); i++){
if(input.charAt(i) == '('){
par_count++;
if(par_count > maxcount){
maxcount = par_count;
}
}else if(input.charAt(i) == ')'){
if(par_count > 0){
par_count--;
}
}
}
if(par_count!=0){
throw new IllegalArgumentException();
}
return maxcount;
}

}``````

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

@jobPrep.. Your solution will not work for this case
"()()()()))"

This will return par_count =0 at the end even though it is invalid expression. You need to do minor modification in the code.
Something like

else if(input.charAt(i) == ')'){
if(par_count > 0){
par_count--;
}
else
{
throw new IllegalArgumentException();
}
}

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

@jobPrep.. Your solution will not work for this case
"()()()()))"

This will return par_count =0 at the end even though it is invalid expression. You need to do minor modification in the code.
Something like

else if(input.charAt(i) == ')'){
if(par_count > 0){
par_count--;
}
else
{
throw new IllegalArgumentException();
}
}

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

``````int parcount = 0;
int maxcount = 0;
for (char c : input.toCharArray()) {
if (c == '(') {
parcount ++;
maxcount = Math.max(maxcount, parcount);
}
if (c == ')') {
if (parcount > 0) {
parcount--;
} else {
System.out.print("Incorrect");
}
}
}``````

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

``````int parcount = 0;
int maxcount = 0;
for (char c : input.toCharArray()) {
if (c == '(') {
parcount ++;
maxcount = Math.max(maxcount, parcount);
}
if (c == ')') {
if (parcount > 0) {
parcount--;
} else {
System.out.print("Incorrect");
}
}
}

System.out.println("res=" + maxcount);``````

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

will fail at "(("

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

``````bool gotMaxDepthOfParanthesis(CString inputStr, int &maxDepthOfParentheis)
{
bool isValidString = true;
maxDepthOfParentheis = 0;
int localDepth = 0;
int numOfLeftSideParenthesis = 0;
int numOfRightSideParenthesis = 0;

for (int i = 0; i < inputStr.GetLength(); i++)
{
if (numOfRightSideParenthesis > numOfLeftSideParenthesis)
{
isValidString = false;
maxDepthOfParentheis = -1;
break;
}
if (inputStr[i] == '(')
{
numOfLeftSideParenthesis++;
localDepth++;
if (localDepth > maxDepthOfParentheis)
{
maxDepthOfParentheis = localDepth;
}
}
if (inputStr[i] == ')')
{
numOfRightSideParenthesis++;
localDepth--;
}
}

return isValidString;
}``````

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

bool gotMaxDepthOfParanthesis(CString inputStr, int &maxDepthOfParentheis)
{
bool isValidString = true;
maxDepthOfParentheis = 0;
int localDepth = 0;
int numOfLeftSideParenthesis = 0;
int numOfRightSideParenthesis = 0;

for (int i = 0; i < inputStr.GetLength(); i++)
{
if (numOfRightSideParenthesis > numOfLeftSideParenthesis)
{
isValidString = false;
maxDepthOfParentheis = -1;
break;
}
if (inputStr[i] == '(')
{
numOfLeftSideParenthesis++;
localDepth++;
if (localDepth > maxDepthOfParentheis)
{
maxDepthOfParentheis = localDepth;
}
}
if (inputStr[i] == ')')
{
numOfRightSideParenthesis++;
localDepth--;
}
}

return isValidString;
}

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

bool gotMaxDepthOfParanthesis(CString inputStr, int &maxDepthOfParentheis)
{
bool isValidString = true;
maxDepthOfParentheis = 0;
int localDepth = 0;
int numOfLeftSideParenthesis = 0;
int numOfRightSideParenthesis = 0;

for (int i = 0; i < inputStr.GetLength(); i++)
{
if (numOfRightSideParenthesis > numOfLeftSideParenthesis)
{
isValidString = false;
maxDepthOfParentheis = -1;
break;
}
if (inputStr[i] == '(')
{
numOfLeftSideParenthesis++;
localDepth++;
if (localDepth > maxDepthOfParentheis)
{
maxDepthOfParentheis = localDepth;
}
}
if (inputStr[i] == ')')
{
numOfRightSideParenthesis++;
localDepth--;
}
}

return isValidString;
}

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

``````countNested <- function(input){

s <- strsplit(input,"")[[1]]

if(length(which(c('(',')') %in% s == T)) == 0) {
} else{

open  <- c()
count <- 0
top <- 0

for(i in 1:length(s)){

if(s[i]=="("){
open <- c(open, "(")
} # end nested opener

if(length(open)>0) {

if(s[i]==")"){

open <- open[-length(open)]
count <- count + 1
top <- max(top, count)

if(length(open)==0){
count <- 0
} # start over again and keep looking

} # end nested closer

} #end if length(open) > 0

} # end loop

return(top)

} #end string check

}

countNested("abc(123(xyz))m(((n)))o")

countNested("(as)(as)s(a()())")``````

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

I was not sure what to do in the case of (()()) Is it two or three?

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

This should work

``````public static void findMaxDepth(String input){
int left = 0;
int closed = 0;
int maxcount = 0;
for (char c : input.toCharArray()) {
if (c == '(') {
left++;
}
if (c == ')') {
if(left>0){
closed++;
left--;
}
maxcount = Math.max(closed, maxcount);

if(left == 0) {
closed = 0;
}
}
}
System.out.println(maxcount);
}``````

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

Try this......
public static int gotMaxDepthOfParanthesis(String input) {
input = input.replaceAll("[^(-)]", "");
System.out.println(input + " " + input.length());
int count = 0;
int Depth = 0;
for (int i = 0; i < input.length(); i++) {
if (count < 0)
count = 0;
if (input.charAt(i) == '(') {
count++;
Depth = Math.max(Depth, count);
} else if (input.charAt(i) == ')') {
count--;
}
}

return Depth;
}

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

Try this ..

``````public static int gotMaxDepthOfParanthesis(String input) {
input = input.replaceAll("[^(-)]", "");
System.out.println(input + " " + input.length());
int count = 0;
int Depth = 0;
for (int i = 0; i < input.length(); i++) {
if (count < 0)
count = 0;
if (input.charAt(i) == '(') {
count++;
Depth = Math.max(Depth, count);
} else if (input.charAt(i) == ')') {
count--;
}
}

return Depth;``````

}

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

gautam.dev36-- I checked your code and you are making a very important and small mistake is "when ever you count goes to negative reset it to 0", then it will work. I made this change in your code and it worked in all possible combination of parentheses ..

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

``````import re
from timeit import Timer

def find_depth_fast(val):
magic = lambda s, n=1: magic(*re.subn(r'\)\(', '', s)) if n else s
left, right = re.match(r'(\(+)(\)+)', magic(re.sub(r'[^()]', '', val))).groups()
if len(left) != len(right):
raise ValueError('Mismatch opening/closing parenthesis')
return len(left)

def find_depth(val):
count = 0
depth = 0
for char in val:
if char == '(':
count += 1
if count > depth:
depth = count
elif char == ')':
count -= 1
if count != 0:
raise ValueError('Mismatch opening/closing parenthesis')
return depth

string = "abc(123(x()((()a()))yz))m(((n)))o(()()a)(()())"
print Timer(lambda: find_depth(string)).timeit(1)
# >> 3.0994415283203125e-06 (3-6)
print Timer(lambda: find_depth_fast(string)).timeit(1)
# >> 0.00032591819763183594 (always less then 1)``````

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

import java.util.Scanner;

public class paranthesis {

public static void main(String[] args) {
String str;
int ans;
Scanner s = new Scanner(System.in);
paranthesis p=new paranthesis();
System.out.println("Enter a string");
str = s.nextLine();
ans = p.checkParanthesis(str);
}

int checkParanthesis(String str){
int ans=0,str_index=0,pr=0;

if(str == null){
return(0);
}
else if(str != null){
while(str_index != str.length()){
if(str.charAt(str_index) == '('){
str_index++;
pr++;
}
else if(str.charAt(str_index) == ')'){
str_index++;
pr--;
ans++;
}
else{
str_index++;
}
}
if(pr == 0){
return(ans);
}
else if(pr != 0){
System.out.println("entered string is wrong!");
System.exit(0);
}
}

return(ans);
}

}

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

``````public class Depth{
public static void main(String [] args){
String str="abs(123xyz))m(((n)))o";
int depth=0;
int max=0;
int l=str.length();
char [] arr=new char[l];
int t=-1,i=0,v=0,total=0,j=0;
for(i=0;i<str.length();i++){
char c=str.charAt(i);
if(c=='('){
t++;
depth++;
arr[t]=c;
if(max<depth)
max=depth;
v++; j++;
}
else if(c==')'){
j++;
if(t!=-1){
t--;
depth--;
v++;
if(t==-1){
if(v%2!=0){
System.out.println("invalid");
break;
}
total+=v;
v=0;
}

}
}

}
if(j!=total)
System.out.println("Invalid  ");
else if(v%2==0){
System.out.println("valid  & depth = "+max);
}

}
}``````

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

You could add an extra count for the current depth and instead of doing the check every time you see a '(' to set the max depth you could just do one check when the open count == 0. Probably doesn't matter much either way but could lead to a speed vs space discussion, however minor it is.

``````int GetMaxParenthesisDepth(char* inputString)
{
int maxDepth = 0;
int openCount = 0;

while (*inputString != '\0')
{
// Found open
if (*inputString == '(')
{
openCount++;

if (openCount > maxDepth)
maxDepth = openCount;
}
// Found close
else if (*inputString == ')')
{
// If found a close but there was no open so far then this is a mismatch
if (openCount == 0)
{
maxDepth = -1;
break;
}

openCount--;
}

inputString++;
}

// If we didn't close everything then this is an error
if (openCount != 0)
maxDepth = -1;

return maxDepth;
}

int _tmain(int argc, _TCHAR* argv[])
{
char inputString[] = "abc(123(xyz))m(((n)))o";
cout << inputString << " = " << GetMaxParenthesisDepth(inputString) << endl;

char inputString1[] = "abc(123(xyz))m(((n))o";
cout << inputString1 << " = " << GetMaxParenthesisDepth(inputString1) << endl;

char inputString2[] = "abc)(123(xyz))m(((n)))o";
cout << inputString2 << " = " << GetMaxParenthesisDepth(inputString2) << endl;

char inputString3[] = "(((())))";
cout << inputString3 << " = " << GetMaxParenthesisDepth(inputString3) << endl;

char inputString4[] = "()()()()";
cout << inputString4 << " = " << GetMaxParenthesisDepth(inputString4) << endl;

return 0;
}``````

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

package com.algorithm;

public class MaximumParanthesis {

public static void main(String[] args) {

String str = "abc(123(xyz))m((((n))))o";

findDepthElement(str);
}

static void findDepthElement(String str ) {
Stack st = new Stack();
int i = 0;
int count = 0;
while( i < str.length() ) {
System.out.println(str.charAt(i));
if(str.charAt(i) == '(') {
st.push(str.charAt(i));
if( count < st.top ) {
count = st.top;
}
}
if(str.charAt(i) == ')' ) {
if(st.top > 0 ) {
st.pop();
}
else {
System.out.println("Wrong pranthesis ");
}

}
i++;
}

System.out.println("Total Value : " +count);

}

}

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

public class MaximumParanthesis {

public static void main(String[] args) {

String str = "abc(123(xyz))m((((n))))o";

findDepthElement(str);
}

static void findDepthElement(String str ) {
Stack st = new Stack();
int i = 0;
int count = 0;
while( i < str.length() ) {
System.out.println(str.charAt(i));
if(str.charAt(i) == '(') {
st.push(str.charAt(i));
if( count < st.top ) {
count = st.top;
}
}
if(str.charAt(i) == ')' ) {
if(st.top > 0 ) {
st.pop();
}
else {
System.out.println("Wrong pranthesis ");
}

}
i++;
}

System.out.println("Total Value : " +count);

}
}

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

``````public class MaximumParanthesis {

public static void main(String[] args) {

String str = "abc(123(xyz))m((((n))))o";

findDepthElement(str);
}

static void findDepthElement(String str ) {
Stack st = new Stack();
int i = 0;
int count = 0;
while( i < str.length() ) {
System.out.println(str.charAt(i));
if(str.charAt(i) == '(') {
st.push(str.charAt(i));
if( count < st.top ) {
count = st.top;
}
}
if(str.charAt(i) == ')' ) {
if(st.top > 0 ) {
st.pop();
}
else {
System.out.println("Wrong pranthesis ");
}

}
i++;
}

System.out.println("Total Value : " +count);

}

}``````

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

``````public static int countMaxNumberOfParenthesis(String str) {
int count = 0, max_count = 0;

Stack<Character> s = new Stack<Character>();
for(int i=0; i<str.length(); i++) {
if(str.charAt(i) == '(') {
s.push(str.charAt(i));
count = 0;
}

if(str.charAt(i) == ')') {
if(!s.empty() && s.pop()!=null) {
count ++ ;
if (max_count < count) {
max_count= count;
}
} else {
return -1;
}

}
}

if(!s.empty()) {
return -1;
}
return count;
}``````

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

``````public static int countMaxNumberOfParenthesis(String str) {
int count = 0, max_count = 0;

Stack<Character> s = new Stack<Character>();
for(int i=0; i<str.length(); i++) {
if(str.charAt(i) == '(') {
s.push(str.charAt(i));
count = 0;
}

if(str.charAt(i) == ')') {
if(!s.empty() && s.pop()!=null) {
count ++ ;
if (max_count < count) {
max_count= count;
}
} else {
return -1;
}

}
}

if(!s.empty()) {
return -1;
}

return count;
}``````

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

public class CheckParenthesis {
public static void main(String[] args) {
String str3="abc(123(xyz)m((((n))))o";
char ch[]=str3.toCharArray();
int c=0;
ArrayList l2= new ArrayList();
for(int j=0;j<ch.length;j++)
{
if(ch[j]=='(')
{
c++;

}
else if(ch[j]==')')
{
c=0;
}
}
Collections.sort(l2);
System.out.println(l2.get(l2.size()-1));
}
}

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

``````class Solution:
def countMaxParenthesis(self, s):
result = []
maxValid = 0

for i in s:
if i == '(':
result.append('(')
elif i == ')':
if len(result) > 0:
result.pop()
else:
return 0
else:
pass
maxValid = max(maxValid, len(result))
return 0 if len(result) > 0 else maxValid

S = Solution()
print(S.countMaxParenthesis('abc(123(xyz))m(((n)))o'))
print(S.countMaxParenthesis('((()))()()'))
print(S.countMaxParenthesis('a)b(c'))``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use a stack. Push on open paren and pop on closed paren. Every push operation increases depth For every pop operation compare the current depth with the current maximum depth and then decrease current depth. A mismatch will be caught by attempting to pop an empty stack.

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

I though of that many times before but you don't really need to any information to stack them you can just count them and make sure that there are the same number of parenthesis closing.

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

I think you need the stack for mismatch checking. and such method is parsing's standard solution that can be used in other expression parsing problems, and be tested on compiler construction.

Python with stack

``````#find max paranthesis depth, throw if mismatch

def max_depth(s):
stack = []
depth = 0
max_depth = 0
for c in s:
if c == '(':
stack.append(c)
depth += 1
if depth > max_depth:
max_depth = depth
elif c == ')':
if (len(stack) == 0 or
stack[len(stack)-1] != '('):
raise ValueError("paran mismatch")
else:
stack = stack[:-1]  #pop
depth -= 1
return max_depth``````

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

Oh yea just realized that the stack only has one type of element, the open parenthesis, so instead of keeping the stack, you can just keep the stack height to save space.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use a stack. Push on open parent and pop on closed paren. In the case of a mismatch an attempt to pop an empty stack will be made. With every push op increase the current depth. For every pop op compare current depth with maximum and then decrease current depth.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.util.Scanner;

public class Parenthesis {

public static void main(String[] args) {
String paren;
System.out.println("Enter the parenthesis");
Scanner sc=new Scanner(System.in);
paren=sc.nextLine();
int count=0;
count =parenthes(paren);
System.out.println("Depth of parenthesis is "+count);

}

private static int parenthes(String paren) {
int i=0,count=0,method=0;
for(i=0;i<paren.length();i++){
if(paren.length()==0){
break;
}
char com=paren.charAt(i);
if(com=='('){
count++;
method=count;
}
else if(com==')'){
count--;
}
}
return method;
}

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````import java.util.Scanner;
public class Parenthesis {
public static void main(String[] args) {
String paren;
System.out.println("Enter the parenthesis");
Scanner sc=new Scanner(System.in);
paren=sc.nextLine();
int count=0;
count =parenthes(paren);
System.out.println("Depth of parenthesis is "+count);

}

private static int parenthes(String paren) {
int i=0,count=0,method=0;
for(i=0;i<paren.length();i++){
if(paren.length()==0){
break;
}
char com=paren.charAt(i);
if(com=='('){
count++;
method=count;
}
else if(com==')'){
count--;
}
}
return method;
}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````import java.util.Scanner;
public class Parenthesis {
public static void main(String[] args) {
String paren;
System.out.println("Enter the parenthesis");
Scanner sc=new Scanner(System.in);
paren=sc.nextLine();
int count=0;
count =parenthes(paren);
System.out.println("Depth of parenthesis is "+count);
}
private static int parenthes(String paren) {
int i=0,count=0,method=0;
for(i=0;i<paren.length();i++){
if(paren.length()==0){
break;
}
char com=paren.charAt(i);
if(com=='('){
count++;
method=count;
}
else if(com==')'){
count--;
}
}
return method;
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````import java.util.Scanner;
public class Parenthesis {
public static void main(String[] args) {
String paren;
System.out.println("Enter the parenthesis");
Scanner sc=new Scanner(System.in);
paren=sc.nextLine();
int count=0;
count =parenthes(paren);
System.out.println("Depth of parenthesis is "+count);
}
private static int parenthes(String paren) {
int i=0,count=0,method=0;
for(i=0;i<paren.length();i++){
if(paren.length()==0){
break;
}
char com=paren.charAt(i);
if(com=='('){
count++;
method=count;
}
else if(com==')'){
count--;
}
}
return method;
}
}``````

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.

### 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.