CareerCup

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))

can you please elaborate more in details

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?