Samsung Interview Question for Software Engineer / Developers

Country: United States

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

Basic idea is to use expression tree to evaluate both the strings and then return true or false based on the output of both.

If 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

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

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 ?

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

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.

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

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

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

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.

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

i think building expression tree only will not solve. how will you check the following expression, please solve.
3*x+y/x+2 and y/x+2+3*x

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

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.

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

Make an expression tree and evaluate

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

It seems like the problem can't be solved using expression trees. Using multiple set of random variables(to avoid the possibility of same answer for some values) , we can determine whether two expressions are equivalent , but can't decide they are same or not.

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.