I have joined the Facebook interview recently. And the following question has been asked on the coding interview.
Given a sequence of numbers and a total target, return whether there exists a continuous sub-sequence that sums up to target.
[1, 3, 1, 4, 23], 8 : True (because 3 + 1 + 4 = 8)
[1, 3, 1, 4, 23], 7 : False
I have written the exact pseudo-code to solve the solution. Which describes the inside of the method. The approach is the sliding window.
The start and end index starts from 0 and through the array it continues to increment the end index and keep adding the existing value array[end] to the temp value if the temp is smaller than the target sum. If every time checks if temp reached the target value, it is it returns true, else if it is bigger form the temp it starts to increment the start index and shrink the window form the beginning. And decreasing the exact value from the temp. And keep checking if it is equal to the target value after it is decreased.
After the interview result came, they told me that "I have solved it wrong because the sequence must be contiguous". I am %100 sure that this is the correct answer, and they saying is I was wrong and I should try 12 months later.
Please put your comment about my solution? What would be the problem to cause misunderstanding?
// [1, 3, 1, 4, 23]
int start = 0
int end = 0
int total = 0;
int target = 8;
while(end < arr.length){
total += arr[end]; // 1 3 1 4 = 9
while(total>=target){
total-=arr[start]; // 8
start++;
if(total == target){
return true;
}
}
end++;
}
return false;