1. 7
  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.