Walmart Labs Interview Question
Country: United States
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;
}
}
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;
}
}
@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();
}
}
@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();
}
}
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);
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;
}
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;
}
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;
}
countNested <- function(input){
s <- strsplit(input,"")[[1]]
if(length(which(c('(',')') %in% s == T)) == 0) {
noquote('Please try again')
} 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()())")
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);
}
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;
}
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;
}
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)
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);
System.out.println("answer is ->" + ans);
}
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);
}
}
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);
}
}
}
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;
}
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);
}
}
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);
}
}
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);
}
}
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;
}
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;
}
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]==')')
{
l2.add(c);
c=0;
}
}
Collections.sort(l2);
System.out.println(l2.get(l2.size()-1));
}
}
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'))
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.
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.
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
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;
}
}
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;
}
}
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;
}
}
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;
}
}
This reminded be of a nasty problem of calculating or possible parenthesis based on an integer.
- Nelson Perez February 23, 2015public 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; }