I came across a question in an interview. I tried solving it but couldnot come up with a solution. Question is: You are given two expressions with only “+” and “-” operators, check if given two expressions are mathematically equivalent. For eg “A+B-C” is equivalent to “A-(-B+C)”.
My thought process : I was thinking in terms of building an expression tree out of the given expressions and look for some kind of similarity. But I am unable to come up with a good way of checking if two expression trees are some way same or not.
Can some one help me on this 
Thanks in advance !
Ok so an expression like {10, -15} is same as {-15, 10}. Here is a simple algo
- go through the input
- parse the numbers (negative signs and brackets)
- store numbers in a map
- iterate through map. if any map value is non zero -> not equivalent, else eq.
Eg. A + (-A + B) being equal to B, create a map ds with the key being the abs(number) itself and the frequency as the data. So if you encounter a positive A, add 1 to that map key, else subtract 1 (-A case). Finally iterate through the map elements, if there is a entry with non zero value(or data) it means we have an extra term in one of the equations and thus they are not equivalent.
For your example, after adding the elements of the first array, map -> [{A, 1}, {B, 1}, {C, -1}]
After adding elements of second array, map -> [{A, 0}, {B, 0}, {C, 0}]
PS. 2nd array elements must be subtracted for proper working. Alternatively you can come up with a different way like addition of both array element frequencies and checking for odd values.
Does that answer your question? Any example that I seem to have missed that wouldn’t work?
Can you find out the time and space complexity for this approach?