Generate a valid expression that computes to given N
This was asked to me in an interview,
Given a list of integer numbers, a list of symbols [+,-,*,/] and a target number N,
provide an expression which evaluates to N or return False if that is not possible.
e.g. let the list of numbers be [1,5,5] and the target number is 9, one possible
solution could be 5+5-1.
Now, my solution was a brute-force recursive solution that runs through all possible numbers and all possible operations and the recursion terminated either when the number exceeded N or was equal to N.
This got me wondering if there was a better, more refined solution. Any thoughts on this? I was thinking some kind of reverse construction of an expression tree.
I'm gonna go ahead and say this interview question cannot be about anything more than trying to narrow the problem down by asking questions. There is an extremely large list of questions you haven't covered that could be important to the solution, for
One thing from those questions I notice is that if division works by rounding and you have a + and / in the operator list, you can always divide until it rounds to 1 and then just add. Also if you can repeat multiplication is essentially irrelevant because it can be replaced by many additions.
The reason I am sure that your interviewer wanted you to ask more clarifying questions is because even the small set of questions that I thought of change the problem in a big way.
One last thing to consider, this problem is a superset of the knapsack problem which is already known to be np-complete, so there is obviously no polynomial time solution.
链接地址: http://www.djcxy.com/p/77184.html下一篇: 生成计算给定N的有效表达式