Facebook Interview Question
SDE1sCountry: United States
Assume 1) no overflow, 2) the / operator is used with truncation. This is with exponential complexity. Is there a way to make it faster?
class Solution {
private:
bool bt(vector<int>& v, int n, int i, int left, int right){
if(i==(int)v.size())return left+right==n;
return bt(v,n,i+1,left+right,v[i])
|| bt(v,n,i+1,left+right,0-v[i])
|| bt(v,n,i+1,left,right*v[i])
|| bt(v,n,i+1,left,right/v[i]);
}
public:
bool getTarget(vector<int>& v, int n){
return v.size() && (bt(v,n, 0, 0, v[0]) || bt(v, n, 0, 0, 0-v[0]));
}
};
TEST(x, y) {
vector<int> v={7,2,4};
Solution sol;
EXPECT_EQ(true, sol.getTarget(v,7));
}
please provide some hints about the desired time and space complexity. There were answers with exponential run time on your previous post with the same question.
- Chris July 27, 2017