sophia
BAN USER- 0of 0 votes
AnswersGiven a series of numbers as the input, the last one as the result. Use the rest numbers to calculate the result,only +, -, *, / are allowed. The order of the input cannot be changed. If there is an equation, print it; or print "no equation". If more than one solution, any working equation is fine.
- sophia in United States
example:
input: 2, 3, 1, 4
output: 2+3-1 = 4.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer
@shondik, well, I think @SRB has given some examples.
Here are some thoughts:
1. Use a stack to save each operation with priority, as well as saving the current number as the input stream. To do */ first, and push the result back to the stack, then do +-.
2. The solution above does check the situations with *0 or /0, there can be more situation to check -- like "+" may not be a proper choice for the last operation when the current result is already larger than the last number, etc. It might be tricky to implement all possible cases, but to some extent, it does help a little for the exponential solution space.
3. Just as @SRB said, the problem never says the input array is int, which shouldn't be, considering "/" operation. When I did it in the interview, I mentioned this, and the interviewer said "what do you think? Make it right".
It could be better. don't need the "carry", and don't need "%" in the loop. I write it by java.
public int[] Add1(int[] a){
for(int i=a.length-1; i>=0; i++){
if(a[i]==9){
a[i]=0;
if(i==0){
int[] new_array=new int[a.length+1];
new_array[0]=1;
for(int j=1;j<a.length+1;j++){
new_array[j]=a[j-1];
return new_array;
}
}
}
else{
a[i]+=1;
break;
}
}
return a;
}
I'm thinking the similar way. Just when the sum is larger than the given number, I check if the last added number itself is larger than given number. If it is, put the sum=0, and track the array[i+1] as the new front of the sub_array; if not, subtract the current front from the sub_array, and check if the sum of rest sub_array is still larger than the given number.
- sophia June 14, 2012
negative will be the same, if the input array allows it. just put all the value to the hashmap.
- sophia August 30, 2012