Country: United States
Interview Type: Phone Interview

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

Loop through the array...for every item reduce the problem to classic "pairs with sum" problem and solve using HashMap. The time would be O(n^2).
E.g. [-1,-3,5,4]
for first item -1 find all the pairs with sum= (0-(-1)=1. which would be -3 and 4 (-3+4=1),so triplet will be -1,-3 and 4.

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

My decision on python:

``````def find_triples(numbers):
res = []
positions = []
length = len(numbers)
i = 0

while i < length:
j = 0
while j < length:
if j == i:
j += 1
continue
k = 0
while k < length:
if k == i or k == j:
k += 1
continue
if sorted([i, j, k], key=int) not in positions:
first = numbers[i]
second = numbers[j]
third = numbers[k]
if int(first) + int(second) + int(third) == 0:
res.append([first, second, third])
positions.append(sorted([i, j, k], key=int))
k += 1
j += 1
i += 1
return res``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

Iterate over the array and for each item reduce the problem to classic "pairs with sum" problem.
E.g. For [-1,-3,4,5] for first item -1 find all the pairs in remaining [-3,4,5] whose sum is 0-(-1) =1. You can use HashMap to find the pairs. The time eff. would be O(n^2).

Comment hidden because of low score. Click to expand.
0
of 2 vote

it is 3 sum problem.
first of all, sort the array,
then for each array[i], it is our job to find two elements from array[i+1] to array[n-1] that their sum is 0.
then this question becomes 2sum problem.

if the array is unique the time complexity is O(n^2)
if the array has replicated elements, time complexity is O(n^2log(n))

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

``````int searchit(int *t, int v, int i, int size)
{
int h=v%size;

if(t[h]==v && h!=i)
return h;
int pos=(h+1)%size;
int p=h-1;
if(p<0)
p=size;
while(pos!=p)
{
if(t[pos]==v && pos!=i)
return pos;
pos=(pos+1)%size;
}
printf("\n");
return -1;
}

void ContinousSubArraySumZero_LimitedCount(int a[], int n, int count)
{
int *t=new int[n+1];

memset(t,INT_MIN,sizeof(int)*(n+1));
t[0]=0;
int i,j,k;

for(i=1;i<n+1;i++)
t[i]=t[i-1]+a[i-1];
for(i=0;i<n+1;i++)
{
if(t[i]<0)
t[i]*=-1;
}

for(i=0;i<n+1;i++)
{
j=searchit(t,t[i],i,n+1);
if(j!=-1 && j!=i && j>i && (j-i<=count))
{
for(k=i;k<j;k++)
printf("%d\t",a[k]);
printf("\n");
}
}
delete [] t;
}``````

Comment hidden because of low score. Click to expand.
0

Sorry, my mistake! This is a wrong post. It produces continuous sub-arrays with sum equal to zero.

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

first we solve the classic subset sum problem,then we find the triplets subset..

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

Can be solved in O(n^2). Iterate the array (i = 0 to n) and for each (i) add each other element in the array (j = i to n)m and check if difference to form sum 0, exist in the hashtable(h). if not found in h, add that a[j] to h as key and value as j (position). Here is the code:

``````static void PrintTriplet_SumZero(int[] a)
{
int n = a.Length;
for (int i = 0; i < n; i++)
{
Hashtable h = new Hashtable();
for (int j = i+1; j < n; j++)
{
int x = 0 - a[i] - a[j];
if (h.ContainsKey(x)) // check if differencee to form "0" exist in hash table
{
Console.WriteLine("Triplet form 0 sum {0} {1} {2}",a[i],a[(int)h[x]],a[j]);
}
else
{
h.Add(a[j], j); // trick, save number a key, and position as value
}
}
}
}``````

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

If the array does not contain duplicated numbers, The algorithm's time complexity is O(n^2)。
But if not, let's set the array {-3, -3, 0, 3}.
is the output:
-3, 0, 3
or:
-3, 0, 3 and -3, 0, 3?
should we print all the duplicated triplets?
If yes, I guess the problem is much more complex.
Some one can give the code?

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

``````void printTriplet(const int a[], int n)
{
for( int x = 0; x < n ; x ++ )
{
for( int y = 0; y < n; y ++ )
{
result[x][y] = a[x] + a[y];
processed[x][y] = false;
}

int[] sortedArray = sort( a, n );

for( int x = 0; x < n ; x ++ )
{
for( int y = 0; y < n - x; y ++ )
{
if( processed[x][y] )
continue;

processed[x][y] = true;
int itemToLook = 0 - result[x][y];
bool found = binarySearch( sortedArray, n, itemToLook );
if( found )
{
int z = search( a, n, itemToLook );
processed[y][x] = true;
processed[x][z] = true;
processed[y][z] = true;
processed[z][x] = true;
processed[z][y] = true;
print( a[x], a[y], itemToLook );
}
}
}
}``````

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

``````static void ArrayTriplesNoDupe(int[] sequence)
{
HashSet<Tuple<int,int,int>> hs = new HashSet<Tuple<int,int,int>>();

int executions = 0;
for (int i = 0; i < sequence.Length - 2; i++)
{
for (int j = i + 1; j < sequence.Length - 1; j++)
{
for (int k = j + 1; k <= sequence.Length - 1; k++)
{
Tuple<int,int,int> t = new Tuple<int,int,int>(sequence[i],sequence[j],sequence[k]);

if (hs.Contains(t))
{
Console.WriteLine("Collision: {0}", t.ToString());
continue;
}
executions++;
if ((sequence[i] + sequence[j] + sequence[k]) == 0)
{
Console.WriteLine("{0},{1},{2}", sequence[i], sequence[j], sequence[k]);
}
}
}
}

Console.WriteLine("Executions: {0}", executions);
}``````

Comment hidden because of low score. Click to expand.
0

You can also shortcircuit the creation of the tuple block by checking to see if the current value of the sequence is the same as the previous value of the position on each loop.

For example, if you have {0,0,0,0,0}, you can execute that once with no need to do the hash lookup for each triple.

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

divide the array in 2 arrays A1,A2. +ve numbers and -ve numbers.
repeat the approach for both the arrays:
- for each element e in array A1, find two elements in A2 such that A2[i]+A2[j]+e = 0.

you can sort the arrays to make searching efficient

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````public class TripletSumToZero {

public static void main(String[] args){
int [] A={ 1, 3,0, -5, 2, 4, -9 , 7, 8, 5, -6, -7, 4, 2};
int l= A.length;
tripletSumZero(A, l);
}

static void tripletSumZero(int [] A, int l){

for(int i=0; i<l; i++)
for(int j=i+1; j<l-1; j++)
for(int k=j+1; k<l-2; k++)
if(A[i]+A[j]==-A[k])
System.out.print("("+A[i]+" "+A[j]+" "+A[k]+") ");
}
}``````

Comment hidden because of low score. Click to expand.
0

I think, for loop's end conditions need little correction.

i < l - 2
j < l - 1
k < l

Comment hidden because of low score. Click to expand.
0

Hei i want the triplets to be unique
suppose 1,4,-5 if it comes,then (1,-5,4) should not come

Comment hidden because of low score. Click to expand.
0

Mukesh, by using your's loop's end condition, the result will show repeated triplets, as questioned by vara.

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

``````public class TripletSumToZero {

public static void main(String[] args){
int [] A={ 1, 2, -3, 5, -7, 2, 4, -6};
int l= A.length;
tripletSumZero(A, l);
}

static void tripletSumZero(int [] A, int l){

for(int i=0; i<l-2; i++)
for(int j=i+1; j<l-1; j++)
for(int k=j+1; k<l; k++)
if(A[i]+A[j]==-A[k]){
System.out.print("("+A[i]+" "+A[j]+" "+ A[k]+") ");
}
}
}

vara, the triplets will be repeating only when the digits are repeated in array.``````

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

LOL.

Comment hidden because of low score. Click to expand.
0

What is meant by LOL here..??

Comment hidden because of low score. Click to expand.
0

Try input, {-1, 4, -3, -2}

Your code will print out, "No triplet exists". While there exists a triplet of first 3 elements.

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

@Mukesh
Now i have updated the code and i think it works now you can check

Comment hidden because of low score. Click to expand.
0

@vgeek, try this input {-1,-3,-5,4,11,-6}

It is only able to find one triplet {-1, -3, 4}, not second one {-5, 11, -6}.

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

@Mukesh
I think it is working..Please check it again

Comment hidden because of low score. Click to expand.
0

@vgeek, let us take a simple case, {-1, -3, -5}

- For first two numbers, your code will go into first if condition, marking bin[1] and bin[4] as 1, count_trip as 3.
- For third number, it will go into second if condition, printing "Triplet exists ", which is incorrect.

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.

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