Software Engineer Interview Questions (2)

Here is another one

Given an array of integers eg [1,2,-3,1] find whether there is a sub-sequence that sums to 0 and return it (eg 1,2,-3 or 2,-3,1) Checking every sub-sequence is O(n^2) which is too inefficient

This is simple. For all the sub-sequence problem, one trick is to use Cumulative sum.

For example, the cumsum of [1,2,-3,1] is [0,1,1+2,1+2-3,1+2-3+1] = [0,1,3,0,1]

The power of cumsum, is once you have it, you can easily get the sum of any sub-sequence. For example, let a be the original array, b be the cumsum of a. To calculate sum of a[i..j], instead of adding j-i+1 numbers, we only need 1 subtract b[j+1]-b[i]. This is because

b[j+1]-b[i]=(a[1]+a[2]+...+a[j])-(a[1]+a[2]+...+a[i-1])
           =a[i]+a[i+1]+...+a[j].

To get the cumsum is O(N). Once we have that, we need to find i, j, where a[i]+…+a[j] is 0. That means b[j+1]-b[i]=0, which means b[j+1] and b[i] are equal.

So the problem is to find two equal numbers in array b. Usually there are 2 solutions.

Solution one: First do sorting, this is O(nlogn), while doing the sort, every number in b will also store an index of the original position in b. So after the sorting we can still construct i and j of the original b from the sorted b.

Solution two: Use a hash table. Just scan b from left to right and put whatever you have seen in to a hash table. Before you put it, check if it was already there. This is O(N) assume the hash code is not that bad. When doing the coding, we don’t have to construct array b explicitly. Here is the code in C++

void find(vector a) {
  int cumsum = 0;
  unordered_map<int, int> seen;
  seen[0] = 0;
  for (int i = 0; i < a.size(); ++i) {
    cumsum += a[i];
    auto it = seen.find(cumsum);
    if (it == seen.end()) {
      seen[cumsum] = i + 1;
    } else {
      cout << it->second << " " << i << endl;
      return;
    }
  }
  cout << "no found" << endl;
}