## Google Interview Question for Software Engineers

Country: Korea
Interview Type: In-Person

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

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

SOLUTION:
ExpTree build() is not required. Solution from equals() below

``````from collections import defaultdict
class TreeNode():
def __init__(self, val):
self.val = val
self.left = None
self.right = None
if val != '+' and val != '-':
self.isLeaf = True
else:
self.isLeaf = False

class ExpressionTree():
def __init__(self, exp):
self.root = self.build(exp)

def build(self, exp):
if not exp:
return
if len(exp) == 1:
return TreeNode(exp)
mid = (len(exp) - 1) / 2
if exp[mid] != '+' and exp[mid] != '-':
mid += 1
if exp[mid] == '-':
exp = self.flip(exp, mid + 1)
node = TreeNode(exp[mid])
node.left = self.build(exp[:mid])
node.right = self.build(exp[mid + 1:])
return node

def flip(self, exp, idx):
ls = list(exp)
for i in range(idx, len(exp)):
if ls[i] == '+':
ls[i] = '-'
elif ls[i] == '-':
ls[i] = '+'
return "".join(ls)

def equals(self, other):
#print self.result()
#print other.result()
return self.result() == other.result()

def result(self):
d = self.calculate(self.root)
for key, value in d.items():
if value is 0:
del d[key]
return d

def calculate(self, node):
if not node:
return defaultdict(lambda:0)
if node.isLeaf:
d = defaultdict(lambda:0)
d[node.val] += 1
return d

left = self.calculate(node.left)
right = self.calculate(node.right)

for entry in right:
left[entry] = left[entry] + (right[entry] if node.val == '+' else -right[entry])
return left``````

A tester

``````A = 'a+b-c-a-b-c-a-b'
B = 'b+a+c+a+b-c+b'
print ExpressionTree(A).equals(ExpressionTree(B))``````

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

can you please elaborate more in details

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

May I know why we have to construct a tree the the first place? Can we just count number of +A and -A to a dictionary?

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

2 trees are given as input. You just have to implement equals()

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.