Yahoo Microsoft Interview Question
Care to give more details? Don't quite understand your explanation..
Much appreciated if you do.
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).
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.
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
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";
}
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";
}
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.
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
*
*/
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;
}
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]);
}
{{
// 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');
}}
// 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');
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.
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.
- 1/11 January 28, 2009Can be done in O(n) time using hash table or O(nlogn) by sorting.