## Linkedin Interview Question for Software Engineer / Developers

Country: United States

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

Actually, we needn't compare the occurrence of ( or ), we just need to replace "(00)" with "0" and recur the process, return the times of replacement. See my code below:

``````<?php

\$input = ')0(';
getDepth(\$input);

function getDepth(\$input) {
\$replace = '0';
\$pattern = '/\(00\)/';
\$count = 0;
\$str = \$input;
\$time = -1;
//    echo \$input . "<br />";
do {
\$time = \$time + 1;
\$str = preg_replace(\$pattern, \$replace, \$str, -1, \$count);
//        echo "<br /> count:";
//        echo \$count;
//        echo "<br />";
} while (\$count != 0);
if (\$time != 0 && \$str == '0' && \$input != '0') {
\$res = \$time - 1;
} else {
\$res = - 1;
}
//    echo "result:\$res";
return \$res;
}

?>``````

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

It is a very nice idea, but what it returns is the *number of nodes* rather than the depth of the tree. However this nice idea can be used to first check if the tree presentation is valid or not. If not valid, return -1. Otherwise, count the number of '(' minus ')' at each location and take maximum.

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

The complexity is depth * N? because each preg_replace is a linear search. And we need to do this depth time.

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

We may use a stack to push "(" onto the stack and popping it off when we find a ")", tracking that it always represents a valid tree. Then, based on the max count of the stack that we see, we can determine the depth of the tree.

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

Need to also take care that there are only two child nodes. The above logic will not catch something like (00)(00)(00).

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

is that a valid expression as per the grammar, because it leaves open the argument for which operator should the operand bound too.

((00)((00)(00)))

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

An interesting problem. Can be solved by recursion.

``````public static void main(String[] args) {
String s = "(00)";
System.out.println(find_dept(s,0,s.length()-1));
}

private static int find_dept(String s, int startIndex, int endIndex){
int split = getSplit(s,startIndex + 1, endIndex-1);
if (s.charAt(startIndex) == '(' && s.charAt(endIndex) == ')' && split > -1
&& (s.charAt(startIndex + 1) == '(' || s.charAt(startIndex + 1) == '0')
&& (s.charAt(endIndex - 1) == ')' || s.charAt(endIndex - 1) == '0')
&& startIndex < endIndex-2)
return 1 + Math.max(find_dept(s,startIndex+1,split), find_dept(s,split+1,endIndex-1));
else
return -1;
}

/**
* Find a potential for the recursive call
*/
private static int getSplit(String s, int startIndex, int endIndex) {
int c = 0;
int split = -1;
for (int i=startIndex;i<=endIndex;i++) {
if (s.charAt(i) == '(')
c++;
else if (s.charAt(i) == ')')
c--;
if (c == 0) {
split = i;
break;
}
}
return split;
}``````

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

(00))

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

SInce the question only asks for the depth and to determine whether the string is well formed, we only have to check whether the parentheses match and all chars other than '(' and ')' are '0', which can be done as follows:

``````int findDepth(String treeString) {
if (treeString == null || treeString.length() < 4) return -1;
char[] chars = treeString.toCharArray();
int depth = 0;
int maxdepth = 0;
for (int i = 0; i < chars.length; i++) {
char next = chars[i];
if (next == '(') {
depth++;
maxdepth = Math.max(depth, maxdepth);
} else if (next == ')') {
depth--;
} else if (next != '0') {
return -1; // an illegal character has been encountered
}
}
return (depth==0)?(maxdepth-1):-1; // not well-formed unless
parentheses match (depth=0)
}``````

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

Will this work for inputs like
(())()
((0000))
Whose results should be -1

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

Nope, you are correct. Should have stuck with the first idea; a simple recursive descent parser, that would have caught those cases

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

well, i think this method is still doable. just need to check # of 0 at the end.

``````public class stringBinaryTree {

public static int findDepth( String s )
{
int countLeft = 0;
int countLeftTotal = 0;
int countZero = 0;
int depth = -1; // countLeft - 1
for( int i = 0; i < s.length(); i++)
{
char a = s.charAt( i );
switch( a ){
case '0':	countZero++; break;
case '(':	{ 	countLeft++; countLeftTotal++; }; break;
case ')':	{ if( depth < countLeft - 1 )
depth = countLeft - 1;
countLeft = 1;
};break;
default: return -1;
}
/* if( a == '(' )
countLeft++;
else if( a == ')' && depth < ( countLeft - 1 ) )
{
depth = countLeft - 1;
countLeft = 1;
}
else if( a != '0' )
return -1;*/
}
if( countZero == countLeftTotal + 1 )
return depth;
else
return -1;
}
/**
* @param args
*/
public static void main(String[] args) {
String s1 = "(00)";     		//0
String s2 = "((00)0)"; 			// 1
String s3 = "((00)(00))"; 		// 1
String s4 = "((00)(0(00)))";	// -> 2
String s5 = "((00)(0(0(00))))";	// -> 3
String s6 = "x";				// -> -1
String s7 = "0";				// -> -1
String s8 = "()"; 				// -> -1
String s9 = "(0)";				// -> -1
String s10 = "(00)x";			// -> -1
String s11 = "(0p)";			// -> -1*/

System.out.println( findDepth(s1));
System.out.println( findDepth(s2));
System.out.println( findDepth(s3));
System.out.println( findDepth(s4));
System.out.println( findDepth(s5));
System.out.println( findDepth(s6));
System.out.println( findDepth(s7));
System.out.println( findDepth(s8));
System.out.println( findDepth(s9));
System.out.println( findDepth(s10));
System.out.println( findDepth(s11));
}
}``````

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

I don't think checking #0 is enough.
It will not work for the following --> ((00)0((0(00))))
Should return -1 but returns 3.

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

``````int get_depth(char ** cur)
{
int ld = 0, rd = 0, depth = 0;
if(**cur == NULL)
return 0;
switch(**cur)
{
case '(':
(*cur)++;
// process left node
ld = get_depth(cur);
// process right node
rd = get_depth(cur);
if(**cur == ')' && ld != -1 && rd != -1)
{
(*cur)++;
if(ld > rd)
return ld+1;
else
return rd+1;
}
else return -1;
case '0':
(*cur)++;
return 0;
default:
return -1;
}
}

int find_depth (char * k)
{
char * tmp = k;
int depth = get_depth(&tmp);
if(depth != -1)
depth--;
if(*tmp != NULL)
depth = -1;
return depth;
}

void main()
{
//   char* str = "((00)(0(0(00))))";
//   char* str = "(0)";
//   char* str = "(00)";
char* str = "(00)x";
printf("depth for %s: %d\n", str, find_depth(str));
}``````

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

Recursive Implementation in Python

``````"""
Synopsis:
Check the well-formedness at each level
- Recursively call for each child node (if it's found)

Example:
((00)(0(0(00)))) # returns 3
(00)x # returns -1
"""

# Return depth of tree if it's well-formed
# @param input : input string
# @param depth : current depth
# @return : depth of tree (if well-formed)
def paren_tree(input, depth = 0):
print "[paren_tree] "+input
if input == "(00)":
return depth
elif input[0] != "(" or input[-1] != ")":
return -1
# Only left or right child
elif input[1] == "(" and input[-2] == "0":
return paren_tree(input[1:-2], depth + 1)
elif input[1] == "0" and input[-2] == ")":
return paren_tree(input[2:-1], depth + 1)
# Both left and right child
elif input[1] == "(" and input[-2] == ")":
lchild, rchild = split_children(input[1:-1])
ldepth, rdepth = paren_tree(lchild, depth+1), paren_tree(rchild, depth+1)
if ldepth > 0 and rdepth > 0:
return max(ldepth, rdepth)
else:
return -1
else:
return -1

# Split two instances of paren_tree
def split_children(input):
count_lp, count_rp = 1, 0
i = 1
while count_lp > count_rp:
if input[i] == "(":
count_lp += 1
elif input[i] == ")":
count_rp += 1
i += 1
print "[split_children] ",input[:i], input[i:]
return [input[:i], input[i:]]

print paren_tree("((00)(0(0(00))))")
print paren_tree("((00)(0(0(000))))")``````

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

``````public int find_depth(String tree) {

if(tree == null || tree.length() < 4 || tree.charAt(0) != '(') {
return -1;
}

int height = -1;
int lengthOfString = tree.length();
int isBalanced = 0;
int countZeros = 0;

for(int i = 0 ; i < lengthOfString; i++) {
char c = tree.charAt(i);
if(c == '0' || c == '(' || c == ')') {
if( c == '(' ) {
isBalanced++;

} else if ( c == ')') {
isBalanced--;
} else {
countZeros++;
}
} else  {
return -1;
}
}
boolean value = hasRoot(tree);
if(isBalanced == 0 && countZeros >= 2 && value) {
if(tree.matches("\\(\\(00\\)0\\)")) {
return 1;
}
// find number of "(0" and return count -1 as dept.
Pattern pattern = Pattern.compile("\\(0");
Matcher matcher = pattern.matcher(tree);
while(matcher.find()) {
height++;
}
}
return height;
}

private boolean hasRoot(String str) {
// Find if it contains following sequence.
return str.contains("(00)");
}``````

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

Some additional case it will cater.

find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1

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

Some additional case it will cater.

find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1

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

Some additional case it will cater.

find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1

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

Some additional case it will cater.

find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1

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

Some additional case it will cater.

find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1

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

Some additional case it will cater.

find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1

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

Some additional case it will cater.

find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1

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

Sorry for repeated comments...I clicked submit multiple times

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

``````int find_depth(char *str)
{
int depth = -1;
char *curr = str;
try
{
expectopen(&curr);
expectchild(&curr, &depth);
expectchild(&curr, &depth);
expectclose(&curr)
depth++;
catch (exception)
{
return -1;
}
}

void expectopen(char **pstr)
{
if (**pstr != '(') throw;
*pstr++;
}

void expectclose(char **pstr)
{
if (**pstr != ')') throw;
*pstr++;
}
void expectchild(char **pstr, int *pdepth)
{
if (**pstr == '0')
{
*pstr++;
return;
}

expectopen(pstr);
expectchild(pstr, &depth);
expectchild(pstr, &depth);
expectclose(pstr);

*pdepth++;
}``````

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

A slightly big version. Most of the code is error handling.

#!/usr/bin/env python

import sys

def get_matching_bracket(line, start, count):
if start >= len(line):
return -1
elif line[start] == '(':
return get_matching_bracket(line, start + 1, count + 1)
elif line[start] == ')':
if count == 1:
return start
else:
return get_matching_bracket(line, start + 1, count - 1)
else:
return get_matching_bracket(line, start + 1, count)

def get_one_node(line, start):
if start >= len(line):
return -1, None

if line[start] == '(':
end = get_matching_bracket(line, start, 0)
if end == -1:
return -1, None
return line[start : end + 1], end + 1
elif line[start] == ')':
return -1, None
elif line[start] == '0':
return line[start], start + 1
else:
return -1, -1

def get_left_right(line):
left, rightStart = get_one_node(line, 0)
if rightStart is None:
return -1, -1

right, rightEnd = get_one_node(line, rightStart)
if rightEnd is None:
return -1, -1

if rightEnd <= len(line) - 1:
return -1, -1

return left, right

# ((00)(00))
# (00)
def get_depth(line):
if line[0] == '(':
end = get_matching_bracket(line, 0, 0)
if end == -1:
return -1

left, right = get_left_right(line[1:end])
if -1 in (left, right):
return -1

leftDepth = get_depth(left)
rightDepth = get_depth(right)

if -1 in (leftDepth, rightDepth):
return -1

return 1 + max(get_depth(left), get_depth(right))

else:
return 0

depth = get_depth(sys.argv[1])
if depth != -1:
depth -= 1
print depth

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

``````#include <iostream>
#include <string>
using namespace std;

int checkTree(string inp) {
try {
string left,right;
if(inp=="0") return 0;
if(inp=="(00)") return 1;
if(inp[1]=='0') {
left = inp[1];
right = inp.substr(2,inp.length()-3);
}
else {
int index=1,count = 0;
do {
if(inp[index] == '(' ) count ++;
if(inp[index] == ')' ) count --;
index++;
} while(count>0);
left = inp.substr(1,index-1);
right = inp.substr(index,inp.length()-index-1);
}
int lTree = checkTree(left);
int rTree = checkTree(right);
if(lTree==-1 || rTree==-1) return -1;
else return (std::max(lTree,rTree) + 1);
}
catch(...) {
return -1;
}
};

main()
{
cout << "(00): " << checkTree("(00)") << endl;
cout << "((00)0): " << checkTree("((00)0)") << endl;
cout << "((00)(00)): " << checkTree("((00)(00))") << endl;
cout << "((00)(0(00))): " << checkTree("((00)(0(00)))") << endl;
cout << "((00)(0(0(00)))): " << checkTree("((00)(0(0(00))))") << endl;
cout << "x: " << checkTree("x") << endl;
cout << "0: " << checkTree("0") << endl;
cout << "(): " << checkTree("()") << endl;
cout << "(0): " << checkTree("(0)") << endl;
cout << "(00)x: " << checkTree("(00)x") << endl;
cout << "(0p): " << checkTree("(0p)") << endl;
}``````

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

in javascript,

function getDepth(str){
if(str=='(00)'){
return 0;
}
var count = str.split(/\(00\)/).length-1;
if(count==0){
throw new Error('invalid char');
}
str = str.replace(/\(00\)/g, '0');
return getDepth(str)+1;
}

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

int solve(string s){
if (s == "(00)")
return 0;
if (s.size() <= 4 || s[0] != '(' || s[s.size()-1] != ')')
return -1;
int i, n = (int)s.size(), lhs = -1, rhs = -1;
if (s[1] == '0'){ // left node is null
rhs = solve(s.substr(2, n-3));
if (rhs == -1)
return -1;
return rhs + 1;
}
else if (s[n-2] == '0'){ // right node is null
lhs = solve(s.substr(1, n-3));
if (lhs == -1)
return -1;
return lhs + 1;
}
else{
i = 1;
if (s[i] != '(')
return -1;
int cnt[2] = {1, 0};
i++;
for (; i < n-1; i++){
if (s[i] == '(')
cnt[0]++;
else if (s[i] == ')'){
cnt[1]++;
if (cnt[1] == cnt[0])
break;
}
else if (s[i] != '0')
return -1;
}
if (i == n - 1)
return -1;
lhs = solve(s.substr(1, i));
rhs = solve(s.substr(i+1, n-i-2));
if (lhs == -1 || rhs == -1)
return -1;
return max(lhs, rhs) + 1;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote
Leaf node must be '(00)'. If we replace a leaf '(00)' with '0' we are effectively shrinking the depth of the tree. Repeat until only '(00)' is left. Following Java code works well for all the test cases here. {{{ public static int findDepth(String str) { int depth = 0; String tempStr = str; while(!tempStr.equals("(00)")) { if(tempStr.indexOf("(00)") == -1) return -1; tempStr = tempStr.replace("(00)", "0"); depth++; } return depth; }
Comment hidden because of low score. Click to expand.
0

OOps! posting the code again.

``````public static int findDepth(String str) {
int depth = 0;
String tempStr = str;

while(!tempStr.equals("(00)")) {
if(tempStr.indexOf("(00)") == -1)
return -1;
tempStr = tempStr.replace("(00)", "0");
depth++;
}
return depth;
}``````

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

Each replacement of '(00)' with '0' only removes a node of the binary tree, it not necessarily shrinks the tree depth.

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

``````public static int findDepth(String str){
Stack<Integer> stack = new Stack<Integer>();
int maxdep = -1;
stack.push(0);
for(int i = 0; i < str.length(); i ++){
char c = str.charAt(i);
if(stack.isEmpty()) return -1;
Integer oldcount = stack.pop();
switch(c){
case '(':
if(oldcount >= 2) return -1;
stack.push(oldcount+1);
stack.push(0);
break;
case '0':
if(oldcount >= 2) return -1;
stack.push(oldcount+1);
break;
case ')':
if(oldcount != 2) return -1;
if(maxdep < stack.size()-1) maxdep = stack.size()-1;
break;
default:
return -1;
}
}
if(stack.size()!=1 || stack.pop()!= 1) return -1;
else return maxdep;
}``````

}

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

``````/**
* Consider this string representation for binary trees. Each node is of the form (lr),
* where l represents the left child and r represents the right child. If l is the character 0,
* then there is no left child. Similarly, if r is the character 0, then there is no right child.
* Otherwise, the child can be a node of the form (lr), and the representation continues recursively.
For example: (00) is a tree that consists of one node. ((00)0) is a two-node tree in which the root has a left child,
and the left child is a leaf. And ((00)(00)) is a three-node tree, with a root, a left and a right child.
*/

/**
* Solution:
*
* The idea is to verify the following three cases:
*
* (0 , (..))
* ((...) , 0)
* ((...) (...))
*
* At each recursive step we identify which possible case (the ones listed above) are we at and we verify if the string is correct.
* As we traverse the subtrees, at each recursive step we check if the "inner" brackets forming the subtrees are valid or not. This
* applied recursively checks that every string representing a subtree is well formed.
*/
public class SerializedTreeDepth {

public static void main(String [] args) {

String tree ="((00)((00)(00)))" ;
calculateDepth(tree);

tree = "(0(00))";
calculateDepth(tree);

tree = "()()";
calculateDepth(tree);

tree = "((1234)(5678))";
calculateDepth(tree);

tree = "(00)" ;
calculateDepth(tree);

}

private static int calculateDepth(String tree) {
int begin = 0 ;
int end = tree.length() - 1;
int depth =  findDepth(begin , end , tree , 0);
System.out.println("Depth: " + depth);
return depth;
}

public static int findDepth(int begin, int end, String tree , int depth) {
//System.out.println("Substring: " + tree.substring(begin, end+1) + " depth:" + depth);

boolean leftSubTreeNull = false ;
boolean rightSubTreeNull = false;

int leftSubTreeBegin ;
int leftSubTreeEnd ;

int rightSubTreeBegin  ;
int rightSubTreeEnd ;

int depthLeft = 0 ;
int depthRight = 0 ;

// We have a valid subtree so far
if(tree.charAt(begin)  != '(' ||
tree.charAt(end) != ')' ) {
return -1;
}

// Is the left subtree null ?
if(tree.charAt(begin + 1) == '0') {
leftSubTreeNull = true;
}

// Is the right subtree null ?
if(tree.charAt(end - 1) == '0') {
rightSubTreeNull = true;
}

// If this is a leaf node ; then the length of the current subtree string must be 3 ; otherwise this string is invalid
if(leftSubTreeNull && rightSubTreeNull) {
if(end - begin == 3)  {
return  depth ;
}  else {
return -1 ;
}
}

// Case 1: If the left subtree is null and the right subtree is not null
// Example: (0( ...))
if(leftSubTreeNull && !rightSubTreeNull) {

if(tree.charAt(begin + 2) != '(') {
return -1 ;
}

if(tree.charAt(end -1) != ')') {
return -1 ;
}

rightSubTreeBegin = begin + 2 ;
rightSubTreeEnd = end -1 ;

if(verifyBrackets(tree , rightSubTreeBegin, rightSubTreeEnd)) {
depthRight = findDepth(rightSubTreeBegin , rightSubTreeEnd , tree , depth+1);
return depthRight;
}  else {
return -1 ;
}
}

// Case 2: Same logic as above but vice versa
// Example: ((...) 0)
if(rightSubTreeNull && !leftSubTreeNull) {

if(tree.charAt(begin + 1) != '(') {
return -1 ;
}

if(tree.charAt(end - 2) != ')') {
return -1 ;
}

leftSubTreeBegin = begin + 1 ;
leftSubTreeEnd = end - 2 ;

if(verifyBrackets(tree, leftSubTreeBegin , leftSubTreeEnd)) {
depthLeft = findDepth(leftSubTreeBegin , leftSubTreeEnd , tree , depth+1);
return depthLeft;
}  else {
return  -1 ;
}
}

// Case 3: The structure should look like:
// ((...) (...))
if(!leftSubTreeNull && !rightSubTreeNull) {

if(tree.charAt(begin + 1) !=  '(') {
return -1 ;
}

if(tree.charAt(end -1) != ')'){
return -1 ;
}

int j = begin + 1  ;
int k = end - 1 ;

int bracketsRight = 0 ;
int bracketsLeft = 0;

leftSubTreeBegin = begin + 1 ;
rightSubTreeEnd = end -1 ;

while(j < tree.length()) {
if(tree.charAt(j) == '(') {
bracketsLeft++;
} else if (tree.charAt(j) == ')') {
bracketsLeft--;
}
if(bracketsLeft == 0) {
break;
}
j++;
}

// If the brackets are not valid or the right subtree is missing ; the string is invalid
if(bracketsLeft != 0 || j == tree.length()) return -1 ;

leftSubTreeEnd = j ;

while (k >= 0) {
if(tree.charAt(k) == '(') {
bracketsRight--;
} else if (tree.charAt(k) == ')') {
bracketsRight++;
}
if(bracketsRight == 0) {
break;
}
k--;
}

rightSubTreeBegin = k ;

if (bracketsRight != 0 || rightSubTreeBegin != leftSubTreeEnd + 1) return -1 ;

depthLeft = findDepth(leftSubTreeBegin , leftSubTreeEnd , tree , depth+1);
depthRight = findDepth(rightSubTreeBegin , rightSubTreeEnd , tree , depth+1);
}

if(depthLeft > depthRight) return  depthLeft; else return depthRight;
}

private static boolean verifyBrackets(String tree, int begin, int end) {

int brackets = 0;

for(int i  = begin ; i <= end ; i++) {
if(tree.charAt(i) == '(' ) {
brackets ++;
} else if (tree.charAt(i) == ')') {
brackets--;
}
}

return brackets == 0 ;
}

}``````

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

* Four cases:

* (00)
* (0 , (..))
* ((...) , 0)
* ((...) (...))

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

Use Stack and it's very easy.
1) Your stach contains '(' at the start
2) Now scan 1 char at a time in given string
2a) if char is '(' , push 2 '(' on stack
2b) if char is '0' or ')' then pop one char from stack. is stack is empty then return -1;
3) At the end your stack must be empty.

``````public static int cntNodes(String str) {
int cnt = 0;
Stack <Character> st = new Stack <Character>();
st.push('(');
int n = str.length();
for(int i = 0; i < n; i++) {
char ch = str.charAt(i);
switch(ch) {
case '(':
cnt++;
st.push('(');
st.push('(');
break;
case ')':
case '0':
if(st.size() == 0) {
return -1;
}
st.pop();
break;
default:
return -1;
}
}
if(st.size() == 0) {
return cnt;
} else {
return -1;
}
}``````

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

This doesn't work for many cases.
Example -
For this case
( ( (00) 0 ) ) , output should be 1 , while your logic will increment count 3 times.

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

Working C code. Seems to pass the test cases which have been discussed.

``````void findDepth(char * str){
int i=0,depth =0,counter =0;
int len = strlen(str);
if(len < 4){
printf("\n Malformed String \n");
}
else{
for(i=0;i<len;i++){

if(str[i] == '('){

depth++;
if(str[i+1]=='0' && str[i+2]=='0');

if(str[i+1]=='0' && str[i+2]==')'){
printf("\n Malformed String \n");
break;
}
if(str[i+1]== '0' && str[i+2]=='(')
counter++;
}
else if(str[i] == ')' && depth == 0){
printf("\n Malformed String \n");
break;
}
else if( str[i] == ')' && depth > 0){
depth --;
}
else if(str[i]!='0' || str[i] !='(' || str[i] != ')'){
// printf("\n Malformed String");
break;
}

}
if(depth == 0)
printf("\n The depth of the given tree is %d", counter == 0? counter:counter +1);
else
printf("\n Malformed String");
}
}``````

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

``````#include <stdio.h>
using namespace std;

//edge case: ()
//edge case: 0)
//edge case: (00)
//edge case: (0(0(00)))
//edge case: ((00)(00))
//edge case: ((00)(((00)(00))0))
//edge case: (0)
//edge caes: (0p)
//edge case: (000)
//edge case: (0(00)
//edge case: )(00)

#define N 100

int find_depth_2(const char* str)
{
int depth = 0;
int top = -1;
char stack[N + 1] = {0};
int max_depth = -1;
const char* p;
for (p = str; *p; p++)
{
if (*p == ')')
{
if (top > 1 && stack[top] == '0' && stack[top - 1] == '0' && stack[top - 2] == '(')
{
top-=3;
stack[++top] = '0';
max_depth = (max_depth < depth ? depth : max_depth);
depth--;
}
else
{
return -1;
}
}
else
{
stack[++top] = *p;
if (*p == '(')
{
depth++;
}
}
}
if (top == 0 && stack[top] == '0')
{
return max_depth;
}
return -1;
}

int find_depth(const char* str)
{
int depth = 0;
int max_depth = -1;
int stack[N + 1] = {0};
int top = 0;
const char* p;
for (p = str; *p ; p++)
{
if (*p == '(')
{
if (stack[top] == 1)
{
stack[++top] = 2;
stack[++top] = 1;
}
else if(stack[top] == 2)
{
stack[++top] = 3;
stack[++top] = 1;
}
else if (stack[top] == 0)
{
stack[++top] = 1;
}
else
{
return -1;
}
depth++;
}
else if (*p == ')')
{
if (stack[top] == 3)
{
top--;
if (stack[top] == 2)
{
top--;
if (stack[top] == 1)
{
top--;
max_depth = (max_depth < depth ? depth : max_depth);
depth--;
continue;
}
}
return -1;
}
else
{
return -1;
}
}
else if (*p == '0')
{
if (stack[top] == 1)
{
stack[++top] = 2;
}
else if (stack[top] == 2)
{
stack[++top] = 3;
}
else
{
return -1;
}
}
else
{
return -1;
}
}
if (*p == 0 && top == 0 && stack[top] == 0)
{
return max_depth;
}
return -1;
}

int main() {
const char* test = ")(00)";
printf("%d\n", find_depth(test));
printf("%d\n", find_depth_2(test));
return 0;
}``````

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

in Java you can write:

int parseTree(String s) {

if (s.length() < 4)
return -1;

Stack<Character> stack = new Stack<Character>();
int maxLevel = -1, level = -1;

try {
int i=0;
while ( i < s.length() ) {
if (s.charAt(i) == '(') {
stack.push('(');
++level;
if (level > maxLevel)
maxLevel = level;
}
else if (s.charAt(i) == '0') {
stack.push('0');
}
else if (s.charAt(i) == ')') {
if (stack.peek() != '0') return -1;

stack.pop();

if (stack.peek() != '0') return -1;

stack.pop();

if (stack.peek() != '(') return -1;

stack.pop();

stack.push('0');
--level;
}
else {
return -1;
}

++i;
}

if (stack.size() == 1 && stack.peek() == '0') {
return maxLevel;
}
}
catch (Exception e) {
}

return -1;
}

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

I have a O(dn) solution where d is the depth of the tree and n is the length of the string.

``````int find_depth(string str) {
int count = -1;
bool found;
if (str.length() < 4)
return -1;
while (str != "0") {
cout << str << endl;
found = false;
int len = str.length();
int i = 0;
while (i<len){
if (str[i] == ')') {
if (i >= 3 && str.substr(i-3,4)=="(00)") {
string temp = str.substr(0, i - 3) + "0" + str.substr(i + 1, len - i - 1);
len = len - 3;
str = temp;
found = true;
}
else
return -1;
}
i++;
}
if (found == false)
return -1;
else
count++;
}
return count;
}``````

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

A Simple Solution which runs in O(n) and O(n) extra space (Stack space)

``````exception e;
void popStack(stack<char>& stk, char popChar) {
if (stk.empty() || stk.top() != popChar)
throw e;
stk.pop();
}
int find_depth(string str) {
stack<char> stk;
int depth = -1;
int currentLevel = -1;

int length = str.length();
char currentChar;
if (length<4)
return -1;
int i;
for (i=0; i<length; i++) {
currentChar = str[i];
if (currentChar == '(' || currentChar == '0') {
stk.push(currentChar);
if (currentChar == '(')
currentLevel++;
if (depth < currentLevel)
depth = currentLevel;
}
else if (currentChar == ')') {
try {
popStack(stk, '0');
popStack(stk, '0');
popStack(stk, '(');
currentLevel--;
}
catch (exception &e) {
return -1;
}
if (stk.empty())
break;
stk.push('0');
}
else
return -1;
}
if (i != length - 1)
return -1;
return depth;
}``````

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

``````int getDepth(string s)
{
int depth = 0;
int depthMax = 0;
vector<char> v;//convert (00) to 0
if(s.back() != ')')
return -1;
for(int i=0;i<s.length();i++)
{
if(s[i] == '(')
{
depth++;
if(depth > depthMax)
depthMax = depth;
v.push_back('(');
}
else if(s[i] == '0')
{
v.push_back('0');
}
else if(s[i] == ')')
{
depth--;
if(v.empty() || v.back() != '0')
return -1;
v.pop_back();
if(v.empty() || v.back() != '0')
return -1;
v.pop_back();
if(v.empty() || v.back() != '(')
return -1;
v.pop_back();
v.push_back('0');
}
else
return -1;
}
if(v.back() != '0' || v.size() != 1)
return -1;
return depthMax-1;
}``````

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

``````#include <iostream>
#include <string>
#include <stack>
#include <limits.h>

using namespace std;

bool validate(string s) {
string& last = s;
while(last.find("(00)") != string::npos) {
int i = 0;
int n = last.size();
string temp="";
while(i < n) {
if (string(last, i, 4) == "(00)") {
i += 4;
temp += "0";
} else {
temp.append(1,last[i]);
i++;
}
}
last = temp;
}

return (last == "0" ? true : false);
}

int getDepth(string s) {
if (validate(s) == false) {
return -1;
}

int n = s.size();
stack<char> st;
int depth = INT_MIN;
for (int i = 0; i < n; ++i) {
if (s[i] == '(') {
st.push(s[i]);
} else if (s[i] == ')') {
st.pop();
}
depth = max(depth, (int)st.size());
}
return depth;
}

int main() {
cout << getDepth("(00)") << "\n";
cout << getDepth("(00)0") << "\n";
cout << getDepth("((00)0)") << "\n";
cout << getDepth("((00)00)") << "\n";
cout << getDepth("((00)(00))") << "\n";
cout << getDepth("((00)0(00))") << "\n";
cout << getDepth("((00)(0o))") << "\n";
cout << getDepth("()") << "\n";
cout << getDepth("(0)") << "\n";
cout << getDepth("((0((00)0))(00))") << "\n";
}``````

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

public static int getHeight(String expression) {
if (expression == null || expression.isEmpty()) {
return 0;
}

if (expression.length() < 4) {
return -1;
}

int height = 0;
while(expression.contains("(00)")) {
expression = expression.replaceAll("\\(00\\)", "0");
height++;
}

if (expression.equals("0")) {
return height;
} else {
return -1;
}
}

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

This is a parsing program. We have a grammar like:

``````P = '(' Q Q ')'
Q = 0 | P``````

So the following top-down recursion based parsing should work. The complexity is N.

``````int P(string &input, int &curr) {
if (input.size() >= input.size()) {
return -1;
}

if (str.at(curr++) != '(') {
return -1;
}

int d1 = Q(input, curr);

if (d1 < 0) {
return -1;
}

int d2 = Q(input, curr);

if (d2 < 0) {
return -1;
}

if (curr >= input.size()) {
return -1;
}

if  (input.at(curr++) != ')') {
return -1;
}

return 1 + max (d1, d2);

}

int Q(string &input, int &curr) {
if (curr >= input.size()) {
return -1;
}

switch (input.at(curr++)) {
case '0': return 0;
case '(': return P(input, curr);
default: return -1;
}
}

int parse(string &input) {
int curr = 0;
return P(input, curr);
}``````

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

It can be done in two phases:

Step 1: Find if the string represents valid binary tree
Step 2: If valid tree, find depth

Step 1 Approach: Replace all (00) occurances with 0, At end, if you end up with a 0, then it is valid binary tree, else not. We can use simple stack to do this,

As we go from left to right in the string,
if element == '(' or '0', push element
if element == ')', then pop last three elements, check if the order of popped elements is
0, 0, ( and if yes, push 0

else return -1 (means not valid binary tree)

At end, check if the stack has only element 0, then return 1 (means valid binary tree), else return -1.
This is O(N)

Step 2 logic: - done only if step 1 return true or valid binary tree
Again go from left to right in string, and incement count when '(' and decrement when ')'.
When incrementing, always check if count is greater than max, and if yes, update max to new count.
After going thru all elements, the value of max -1 is depth. (max minus 1 needed since depth starts numbering from 0)

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.