Yahoo Microsoft Interview Question






Comment hidden because of low score. Click to expand.
1
of 1 vote

Just form the prefix Sums array B[i] = a[0] + ... + a[i] and check for dupes. Also maintain idx values in the array B, so that we can check for slice length >= 2.

Can be done in O(n) time using hash table or O(nlogn) by sorting.

- 1/11 January 28, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice Solution

- Anonymous January 28, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Care to give more details? Don't quite understand your explanation..

Much appreciated if you do.

- Shitsumon January 31, 2009 | Flag
Comment hidden because of low score. Click to expand.
2
of 0 votes

Explanation for the algorithm mentioned by 1/11:

Take another array of same size, at each position, fill in sum from ele at index 0 upto that position.
For example:
sum[0] = a[0]
sum[1] = sum[0] + {a[1]}
sum[2] = sum[1] + {a[2]}
and so on.

Now you want to find a duplicate value in this array. For that purpose, sort this 'sum' array. Find two consecutive values in this array which have same value.
For example:
sum[4] and sum[7] (in previous unsorted array, not the sorted one) may have same value, or any others.
Since these two values are same, it means sum of values between a[4] and a[7] should sum to 0. Precisely, (a[5] + a[6] + a[7]) should sum to zero here.

Thats it.
Complexity:
Time: O(n),
Space: O(n).

- GA February 02, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, time complexity: O(nlogn)

- GA February 02, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well, a hash table can be used to find duplicates so, complexity will be O(n)

- Anonymous March 03, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice and easy solution :)
Thanks !!

- addy June 10, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome solution

- Deb July 21, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

good sol

- Anonymous November 10, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wonderful...

- Anonymous November 11, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Beautiful. And thanks GA for the explanation.

- bp February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The following is my way to solve this problem.

1. Check if the sum of any two consecutive elements in this array is equal to zero. If yes, the slice is found; else, go to step 2.
2. Check if the sum of any three consecutive elements in this array is equal to zero.If yes, the slice is found; else, go to step 3.
....
Final step: Check if the sum of n consecutive elements in this array is equal to zero( n is the number of elements in this array).If yes, the slice is found; else no slice required is found in this array.

The worst case for the complexity of this algorithm is 2^n.

- TJ January 27, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse the array from left to right.

For each element e in the array:
- Set a running sum to the value of e
   For each element x to the right of e in the array:
    - Add x to the running sum
    - If the running sum equals zero:
       * Add to a list of slices equal to 0 [e, x]

The worst case running time is n^2

- Eli January 27, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But what if you have to exclude one of the elements to the right of the current element in order to get zero...your algorithm does not account for that.

- Sunny March 29, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

slicing must make sure that the order of elements in the array be preserved.
Immediate Heuristic to this problem is as below:
Logic:
+ Find the suffix sum of all the elements in the array.
during the generation if the sum equals 0, we found atleast one slice
which has sum 0.
+ Observation is that, it might be impossible to do this in O(n) with out
extra space. Any solutions better than this O(n^2) ?.

void find_max_sum(int*a, int n){ 
  int sum=0, i=0, j, st=0,end=0;
  for(i=0;i<n;++i){
    sum=0; st = i;
    for(j=i;j<n;++j){
      sum+=a[j];
      if(sum == 0){
        end = j;
        n =-1; //to break the outer loop
        break;
      }
    }
  }
  cout << "From " << st << " to " << end <<"\n";
}

- cnb January 28, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sirish,
Are you sure it works.I think it noly finds if there exists 2 numbers that add up to zero .for eg- if array is 1,2,3,-1 the above algo would return true which is wrong

- Anonymous January 30, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Splice means a continuous block or array. If we sort the array we loose the original order. So sorting array logic doesn't work. Please reread the question and analyse.

- cnb January 31, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ CNB ...
your solution will not work in case the first element of array is '0'

- stallion March 03, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How abt this minor modification to support min. subarray length of 2 and avoid the '0' case mentioned above ?

void find_max_sum(int*a, int n){
int sum=0, i=0, j, st=0,end=0;
for(i=0;i<n;++i){
sum=0; st = i;
for(j=i;j<n;++j){
sum+=a[j];
if(sum == 0 && (j-i) >=2 ){
end = j;
n =-1; //to break the outer loop
break;
}
}
}
cout << "From " << st << " to " << end <<"\n";
}

- stallion March 03, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

stallion: still the answer is NO, your solution is not going to work, just try it out and you'll know why the hell its not working, right?

- sirish October 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1/11's solution is awesome.

But just one addition - we also have to check if any of B[i]s is 0.
Because for ex: [-1, -2, 3] is the array. Then B=[-1, -3, 0]. No duplicates.

- Anonymous December 28, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice catch... 1/11's solution is cool.

- Nithishhe April 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

smart solution - 1/11

- Anonymous May 16, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C# solution based on 1/11's solution. Clever solution, I only hope he hard struggled to get it for some time. My solution can be argued to run in linear time but O(2n) extra space (for count array and hash)

int[] SpliceAddingToZero(int[] ar)
        {
            if (ar == null || ar.Length < 2) return ar;
            int[] counts=new int[ar.Length];
            int sum=0;
            for(int i=0;i<ar.Length;i++)
            {
                sum=sum+ar[i];
                counts[i]=sum;
            }
            Dictionary<int,int> countIndex=new Dictionary<int,int>();
            for(int i=0;i<counts.Length;i++)
            {
                if(counts[i]==0 && i>0)
                {
                  return ar.Take(i+1).ToArray();
                }
                //If the countIndex already has an element of the same counts
                //it means that we can form a zero starting from previous clashed 
                //count to this count
                if (countIndex.ContainsKey(counts[i]))
                {
                    int clashedCount = counts[i];
                    int firstIndex= countIndex[counts[i]]+1;
                    int numElementsInSubArray = i - countIndex[counts[i]];
                    return ar.Skip(firstIndex).Take(numElementsInSubArray).ToArray();
                }
                else
                    countIndex.Add(counts[i], i);
            }
            return null;
        }
        /*Test cases
         * [2,3,-1,2,-4]    [3,-1,2,-4]
         * [0,-3,3,2]       [0,-3,3]  starting with zero
         * [1,2,-3]         [1,2,-3] whole array
         * [2,3,-4]         null     nothing
         * [8,-5,4,3,1,-2,2,1]  [3,1,-2]  multiple slices first should return
         * [-1,-2,-3]      null  all negative
         * all positive
         * [2,-2,3,-1,-2] [2,-2] first two
         * null array 0, 1 array
         * 
         */

- getAjob September 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct Node {
    int sum;
    int index;
    Node() : sum(0), index(0) {}
};
bool lessx(const Node & l, const Node & r)
{
    return ((l.sum == r.sum) && (l.index < r.index)) || (l.sum < r.sum);
}

int run()
{
    int A[] = {1, 4, -7, 2, 1, 2, -2, -10};
    int sz = sizeof(A)/sizeof(A[0]);
    Node B[sz]; B[0].sum = A[0];
    for(int i = 1; i < sz; i ++) {
        B[i].sum = B[i-1].sum + A[i];
        B[i].index = i;
    }   
    sort(B, B + sz, lessx);
    Node old; old.sum = (1 << 31) - 1; old.index = 0;
    int i = 0;
    while(i < sz) {
        if((old.sum == B[i].sum) && (B[i].index - old.index >= 2)) {
            for(int j = old.index + 1; j <= B[i].index; j ++) printf("%d ", A[j]);
            printf("\n");
            break;
        }
        old = B[i++];
    }
    return 0;
}

- zombie July 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I came up with this. But on second thoughts, this is O(n^2)

public static void PrintZeroSumSlice(int[] arr)
        {
            int sum = 0;
            foreach (int item in arr)
            {
                sum += item;
            }
            PrintZeroSumSliceInternal(arr, 0, arr.Length - 1, sum);
        }
        public static void PrintZeroSumSliceInternal(int[] arr, int start, int end, int sum)
        {
            if (end - start <1)
                return;
            
            if(sum ==0)
            {
                for (int i = start ; i <= end; i++)
                {
                    Console.Write(arr[i] + " ");
                }
                Console.WriteLine();
            }
            PrintZeroSumSliceInternal(arr, start + 1, end, sum - arr[start]);
            PrintZeroSumSliceInternal(arr, start , end -1, sum - arr[end]);
            PrintZeroSumSliceInternal(arr, start + 1, end-1, sum - arr[start] - arr[end]);
        }

- bp February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
// JavaScript implementation

function sumZero(arr) {
var sum = 0;
var sums = {0: 0};
var map = {};
var i;
if (arr.length === 0) {
return arr;
}
// first interation to gather all sums from index 0 to i;
for (i = 0; i < arr.length; i++) {
sum += arr[i];
if (sum === 0) {
// return immediately if we happen to find a slice early
return arr.slice(0, i + 1);
}
sums[i + 1] = sum;
}
// find dup value in all sums. the 2 dup values' keys are indices we'll slice from and to
for (i in sums) {
if (map[sums[i]]) {
return arr.slice(map[sums[i]], i);
}
map[sums[i]] = i;
}
return [];
}

var assert = require('assert');

assert.equal(sumZero([-4,4,2]).join(','), '-4,4');
assert.equal(sumZero([2,3,-1,2,-4,8,9]).join(','), '3,-1,2,-4');
assert.equal(sumZero([-3,5,-2,8,10]).join(','), '-3,5,-2');

}}

- realpeterz March 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// JavaScript implementation. Sorry for the non-formated code
function sumZero(arr) {
  var sum = 0;
  var sums = {0: 0};
  var map = {};
  var i;
  if (arr.length === 0) {
    return arr;
  }
  // first interation to gather all sums from index 0 to i;
  for (i = 0; i < arr.length; i++) {
    sum += arr[i];
    if (sum === 0) {
      // return immediately if we happen to find a slice early
      return arr.slice(0, i + 1);
    }
    sums[i + 1] = sum;
  }
  // find dup value in all sums. the 2 dup values' keys are indices we'll slice from and to 
  for (i in sums) {
    if (map[sums[i]]) {
      return arr.slice(map[sums[i]], i);
    }
    map[sums[i]] = i;
  }
  return [];
}

var assert = require('assert');

assert.equal(sumZero([-4,4,2]).join(','), '-4,4');
assert.equal(sumZero([2,3,-1,2,-4,8,9]).join(','), '3,-1,2,-4');
assert.equal(sumZero([-3,5,-2,8,10]).join(','), '-3,5,-2');

- realpeterz March 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 0 vote

you can do it in O(nlogn).
+ sort the array nlogn
+ take two pointers pstart and pend - this is done in o(n)
start = 0;
end = strlen(p);
if (p[start] + p[end] ) > 0 then end--;
if (p[start] + p[end] ) < 0 then start++;
if (p[start] + p[end] ) == 0 found it return ture;
if start > = end then return didn't find;
return didn't find.

- sirish January 29, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

wrong...

- Anonymous January 30, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

wrongy...lal

- Anonymous February 27, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what a moron

- Anonymous September 24, 2009 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More