Samsung Interview Question
Software Engineer / DevelopersCountry: United States
the random number substitution seems interesting ...
but, for that i need to scan both of the strings to extract variables, other than integers, operators . any better algo for this ?
but, even in that case there is a possibility that the randomly generated input substitution could produce the same result for both expressions, right ?
so, how to avoid this ?
By your post, I assume that there are variables in both the equations.
As per my knowledge, only way to solve this problem is to parse and find variables
What I meant by random numbers is
if you substitute x by 2 in equation (1) do the same in equation(2), by this way you can ensure that both the expressions are same only if they evaluates to same output.
yeah, thats what I was interpreting by your previous answer, but what I suspect is, that even if we substitute randomly generated numbers, same in 1st & 2nd string, then there might be a possibility that, even if strings were not identical, then they might produce the same result for this sub-case. So, in this case it fails
I think you do not need to substitute any variable for any random value. Instead, just build the expression trees for both input strings and see whether those trees are identical in their structures and input parameters. For the most cases, it's going to be a binary tree, since most of the operators are binary (require two operands), though there can be nodes where the root may contain 3 children, which will be the case for ternary operators.
I'm thinking the original question must have had some additional constraints (like that it involved no variables, or that the equations are in the same order but have different bracketing, something along those lines), otherwise there'd be the need to simplify the equation [e.g (a+b)^2 is equal to a^2 + b^2 + 2*a*b, but then there's (a+b)^n and so on] which seems way too complex.
Basic idea is to use expression tree to evaluate both the strings and then return true or false based on the output of both.
- siva November 29, 2012If the equations are something like "2x+3(y*z)" and "3x-2y/(x^z)" think of replacing x, y and z in both the strings to some random number.
Note: validation is required before blindly replacing, because both the expressions can be completely different, one with a,b,c and other with x,y,z..
Life is easy when the expressions are just numbers and operators