1. 7
marcofoco.com
1.

2. 5

For me, the C++ clutters an otherwise interesting problem. The basic algorithm is simple, but the edge cases (starting indexes / starting sum value, the literal array endpoints, keeping the lower dynamic endpoint <= upper one, no solution found) make it non-trivial to implement cleanly. This is my best effort in JS:

``````function sum(target, arr) {
let [a, b, cur] = [0, 0, arr[0]]

while (cur != target  && b < arr.length) {
if (cur < target || a == b) {
b += 1
cur += arr[b]
}
else {
cur -= arr[a]
a += 1
}
}

if (cur != target) return null

return [a, b]
}
``````

Try it online!

Another variation is to find the shortest such contiguous sub-sequence.

1. 2

Given an unsorted array (sequence) of non-negative integers, find a continuous sub-array (sub-sequence) which adds to a given number S. Implement the solution as a generic algorithm, but visualize the results with indices that are 1-based.

Despite the fact that I don’t like those artificial interview questions, I was curious to see how my naîve solution would look like. I was using a sum variable inside the outer loop, which results in an O(N^2) algorithm: Go.

This version isn’t very useful for the final solution that will be presented below, but allows us to calculate the complexity of this solution, O(N3), as we have 3 nested loops (with N being the number of elements in the sequence)

Where is the third inner loop, is it the call to `std::accumulate(`?

1. 2

Where is the third inner loop, is it the call to std::accumulate(?

I don’t understand singpolyma’s reply, so I might be missing something, but yes `std::accumulate` has linear time complexity.

1. 1

O(N3)

… I think they mean `N3` also known as `O(N)`

1. 1

The loops are nested, so it’s not O(N). That said, I only see two nested loops, and the naive solution is to test every possible pair of endpoints, which is nC2, which is O(N^2).

1. 1

I wasn’t doing analysis, only commenting that `O(N3)` would be nonsense. If they mean `O(N^3)` that’s fine of course.

1. 6

You can tell it’s a copypaste error because nobody would write N3 to mean N×3, they’d write 3N.

1. 2

That’s just how it looks in the cut and paste. In the article the 3 is super-scripted.