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

- siva November 29, 2012 | Flag Reply
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 ?

- Sai Nikhil November 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- siva November 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sai Nikhil November 29, 2012 | Flag
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.

- ashot madatyan November 30, 2012 | Flag Reply
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

- ifty November 30, 2012 | Flag Reply
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.

- Anonymous December 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Make an expression tree and evaluate

- Megha Mantri December 05, 2012 | Flag Reply
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.

- praveenkcs28 January 30, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More