Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
Although your solution is perfectly fine and can be used to solve more generalized equations but we can take advantage of the special assumptions given for the input. Thus we can avoid constructing a parse tree.
We scan the input and process LHS and RHS of the equation and identify tokens and processing them according to the operators encountered. After this the solution is trivial.
I know I didn't realise use the domain restrictions to simplify the solution, but I can't really see how since there is no restriction on brackets (right?) for instance how can you parse some crazy complex brackets as tokens? Something like:
((4*(5-X+X*(4/5))+1)*6)*(7*(X/(6+1)))+5X=0
some absolute idiot, not saying it is you, kept begging people to help him to code this from around a week ago (on chat)
expand both sides out, collect like terms (3 counters a2++, a1++, a0++ on left side, and -- when seen on right side... for coefficients of a2*x^2 + a1*x + a0).
After all that is said and done, check if a2 is 0, if so easy...
If a2 is not zero, check discriminant and build 3 cases on that
The actual code for this seems beyond the scope of an interview but the solution I've sketched out is:
- shinsetsu November 02, 20131. Parse the input string into a tree structure with = at the root and each node either an operator (+-/*) or a value. The tree is structured with lower order operators higher in the tree. Take care to respect brackets when creating the tree.
2. Evaluate each side of the tree root. Each node evaluates to a composite value of x^2's, x's and a constant. Take care when multiplying two sub-nodes that have x^2 and x values. If you ever hit an x^3 value or higher order x, throw exception.
3. Subtract the right hand side values from the left hand side values to get something in the form ax^2 + bx + c = 0. Use the quadratic formulae to solve it.