## Microsoft Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

Step 1 :- Square each element ( O(n) time ). This reduces the problem to check if an element is the sum of any other two elements.

Step 2 :- Sort this new array in ascending order( O(nlog(n)) time ).

Step 3 :- Now consider each element array[i] , For any array[i] = array[j] + array[k] , both k and j are strictly lesser than i (Question says all positive distinct integers) !

Step 4 :- Write a for loop where j increases from 0 to i and k decreases from i to 0 until j and k meet ,

If array[j] + array[k] < array[i]
j++;

else if array[j] + array[k] > array[i]
k--;

else (if equal)
print the square roots of array[i],array[j],array[k] !

So totally O(n) operations !!!

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

JAVA CODE :-

``````import java.util.Collections;

public class PythagoreanTriplet extends QuickSort{

public static void main(String []args)
{
PythagoreanTriplet obj = new PythagoreanTriplet();
int []input = {3,5,4,10,8,6,44,13,265,5,23,96,12,90,7,41,40,9,117,125,247,264,161,240,289,68,285,293};
obj.printPythagoreanTriples(input);

}
public int[] squareArrayElements(int []input)
{
for(int i = 0;i < input.length;i++)
{
input[i] = input[i] * input[i];
}
return input;
}
public void displayArray(int []input)
{
for(int i = 0;i < input.length;i++)
{
System.out.print(input[i] + " ");
}
System.out.print("\n");
}
public void printPythagoreanTriples(int []input)
{
input = squareArrayElements(input);
quickSort2(input,0,input.length - 1);

displayArray(input);
for(int i = 0;i < input.length;i++)
{
for(int j = 0,k = i;j < k;)
{

if(input[i] == input[j] + input[k])
{
System.out.println("{ " + Math.sqrt(input[j]) + " , " + Math.sqrt(input[k]) + " , " + Math.sqrt(input[i]) + " }");
break;
}
else if(input[i] > input[j] + input[k])
j++;
else
k--;
}
}
}
}``````

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

I am afraid there is a mistake in this solution. Specifically, you are setting all three indices i, j, and k to zero at the commencement of the nested loops. So, the condition j<k is not satisfied. Even if it was, then the next comparison would have caused the k-- segment to execute, resulting to k=-1 for the next iteration.

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

I haven't looked at the code, but from your description, I see what approach you're trying to take. I just wanted to let you know that the approach is O(n^2), not O(n).

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

Possible optimizations:
Pythagorean: square(c) = square(b) + square(c)
1.) once you have selected a b, then just subtract square(b) from square(c). this will give you square(a).
2.)Now do binary search for square(a) or a (depending on if you choose to square first and use the sorted array or just sort the original array).
3.) if you find such a 'square(a)' or 'a' you need to stop the loop for b only till the index where a was found. You do this since for values lower than 'a' you cannot find a sum that can be equal to square(c) or c (whichever you choose depending on your approach).

If you don't choose to square first then you won't have to find the square roots of the values to get the original values for printing the triple.

Correct me if you find issues with this approach.

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

@Anonymous :- First time i = j = k = 0! The inner loop is not executed , next time when j = 0 , i = k = 1 , the inner loop is executed and k is never = -1 !

I have tested the code and it works error free.

@eugene :- I know overall its not O(n) , I just mentioned it for step by step , sorting alone takes O(nlog(n)).
Overall probably O(n^2)

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

@Nik :- I like the idea of it , instead of keeping two pointers to the same array , I could subtract two squared elements and check if the other exists in the same array.

I don't think this will optimize the time/space complexity in any way.
Its basically the same in Big O notation.

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

Why do you think that there is only one pair a_j, a_k as a match for a_i?
Consider 47 1104 1105 and 744 817 1105.

Nevertheless, it's close to proper solution with O(n^2) complexity.

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

@nikita++ I know . for eg. (23, 264, 265) (96, 247, 265)
If u remove the ' break ' statement from the checking condition , it will print all triples but will make it slower for normal cases.

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

codes-to-problem.blogspot.in/2012/11/finding-pythagorean-triplets-in-array.html

``````http://codes-to-problem.blogspot.in/

import java.util.Arrays;
public class PythagoreanTripletsInArray {

public static double [] getSquare(String [] args){
double [] array = new double[args.length];
for(int i=0;i<args.length;i++){
double j=Integer.parseInt(args[i]);
array[i]=j*j;
}
return array;
}

public static void main(String [] args ){
double [] array =getSquare(args);
Arrays.sort(array);
Boolean flage = true;
for(double aInt : array){
for(int i=0,j=(array.length-1);i<j;){
double sum = array[i]+array[j];
if(aInt == sum){
System.out.println(Math.sqrt(aInt)+", "+Math.sqrt(array[i])+", "+Math.sqrt(array[j]));
flage = false;
break;
}
else if(aInt > sum)
i++;
else
j--;
}
}
if(flage)
System.out.print("No such solution exist");
}
}

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

The loops aren't that optimized. For instance, given aInt, you know j can't be bigger than the position of the aInt, yet you are starting from the end of the array...

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

1. Save the square of numbers in an array.
2. For each number a, initiate two pointers(b&c) to the middle of the array, find b+c. if sum is greater than a, binary-decrement b and if sum is less than a, binary increment c
3. repeat step 2 until a=b+c or both pointers(b&c) go out of scope. if a=b+c, print a,b,c
4. complexity is O(N)*O(LogN)*O(LogN) and i think it is better than O(N)*O(N)

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

What do you mean by 'binary in/decrement'?

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

similar to how you do a binary search

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

By your logic b & c would always lie on each side of the middle of array. This might not be true.

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

# include<stdio.h>
# include<stdlib.h>
# include<conio.h>
# include<math.h>
int compare(const void*a,const void*b)
{
return(*(int*)a-*(int*)b);
}//end of compare used by qsort
int find_triplet(int *a,int n)
{
int i,k,j,m,sum,flag=1;
//first modify the array if it can not be modified then create its copy first
for(i=0;i<n;i++)
a[i]=a[i]*a[i];
qsort(a,n,sizeof(int),compare);
for(i=0;i<n;i++)
printf("%d\n",a[i]);
for(i=0;i<n;i++)
{
k=a[i];
j=0;
m=n-1;
while(j<m)
{
sum=a[j]+a[m];
if(sum==k&&j!=i&&m!=i)
{
flag=0;
puts("found triplets");
printf("%d %d %d",(int)sqrt(k),(int)sqrt(a[j]),(int)sqrt(a[m]));
printf("\n");
j++;m--;
}
else if(sum>k)
m--;
else
j++;
}//end of while
}//end of for loop
if(flag==1)
puts("no such triplet occurs");
return 0;
}

int main()
{
int n,i,*a;
printf("enter the number of elements you want to enter in the array");
scanf("%d",&n);
a=(int*)malloc(sizeof(int)*n);
if(a==NULL)
{
puts("not enough memory to store array elements");

}
else
{
for(i=0;i<n;i++)
{
printf("Enter element:");
scanf("%d",&a[i]);
}//end of for loop

find_triplet(a,n);
}
getch();
return 0;
}//end of main

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

``````step1:   Square the array in place  and add square ie) a[i]*a[i] as key and value as a[i] in a dictionary for all elements of the array
step 2:  Sort the array in ascending order.
Step 3: Traverse the array picking adjacent elements and sum them and see if it is in dictionary, if so print the corresponding values in dictionary as pythogorian triplets.

eg:- a[]={3,2,4,5}
after step 1:
a[]={9,4,16,25}
dict = { 4:2, 9:3, 16:4, 25:5}

after step2:
a[]={4,9,16,25}

step 3:

4+9=13 not in dict
9+16=25 in dict

output values dict[9],dict[15],dict[25] is 3,4,5

proceed till the end of the array``````

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

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

void merge(int *a,int p,int q,int r)
{
int n1=q-p+1;
int n2=r-q;
int i,j,k;
long L[n1+1],R[n2+1];

for(i=0;i<n1;i++)
L[i]=a[p+i];
L[n1]=1000000000;

for(i=0;i<n2;i++)
R[i]=a[q+i+1];
R[n2]=1000000000;
i=0;
j=0;
for(k=p;k<=r;k++)
{
if(L[i]<=R[j])
{
a[k]=L[i];
i++;
}

else
{
a[k]=R[j];
j++;
}
}
}

void mergesort(int a[28],int p,int r)
{
int q;
if(p<r)
{
q=(p+r)/2;
mergesort(a,p,q);
mergesort(a,q+1,r);
merge(a,p,q,r);
}
}

int main()
{
int a[28]={3,5,4,10,8,6,44,13,265,5,23,96,12,90,7,41,40,9,117,125,247,264,161,240,289,68,285,293};
int p=0,r=27,i;
int *x,*y;
mergesort(a,p,r);

for(i=27;i>=0;i--)
{
x=&a[0];
y=&a[i-1];
while(x!=y)
{
if((*x)*(*x)+(*y)*(*y)==a[i]*a[i] && (*x)!=(*y) && (*y)!=a[i] )
{
printf("\n%d %d %d",*x,*y,a[i]);
break;
}

if((*x)*(*x)+(*y)*(*y)>a[i]*a[i])
y--;

else
x++;
}
}

getch();
return 0;

}

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

``````WORKING code in turbo c with  time O(n^2);just copy and run this code...
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<math.h>
void main()
{
int n,i,j,m,flag;    float f;
int *a,*hashtable;
clrscr();
n=100;//scanf("%d",&n);
a= (int*) malloc (n*(sizeof(n)));
for(i=0;i<n;i++)
a[i]=i+31;//scanf("%d",&a[i]);
i--;
m=a[i];flag=m;
hashtable=(int*) malloc(m*(sizeof(m)));
for(i=0;i<m;i++)
hashtable[i]=0;
for(i=0;i<n;i++)
{
m= a[i];
hashtable[m]=flag;
}
for(i=0;i<n-2;i++)
{
for(j=i+1;j<n-1&&i!=j;j++)
{
m=(a[i]*a[i]+a[j]*a[j]);
f=sqrt(m)-(int)sqrt(m);
m=(int)sqrt(m);
if(f>0.0)
continue;
if(hashtable[m]==flag)
{
printf("a=%d  b=%d  c=%d\n",a[i],a[j],m);
i=j=n;
}
}
}
free(hashtable);
free(a);
getch();
}``````

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

Can u explain your logic ??

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

a^2+b^2 = c^2
create an array of [a1"2, a2^2 ... an^2 ]
Now the problem reduces to find pair of numbers whose some is equal to a third number .
for this sort the array in NLog(N) and the take one pass to solve this problem.

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

@addy: there's a flaw in that analysis. You need one pass per each possible third number. There are N of these, so you will require O(N^2 log N) time (or O(N^2) if you sort only once and then do the N passes in O(N) each).

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

For the first solution,

You can start from i=2 and initialize j and k as j=0, k=i-1

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

For the first solution,

You can start from i=2 and initialize j and k as j=0, k=i-1

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

``````public void FindPythagoreanTriples(int[] numbers)
{
int n = numbers.Length;

//This would take O(N log N)
Sort(numbers);

int[] squares = new int[n];

//This would take O(N)
for (int i = 0; i < n; i++)
{
squares[i] = numbers[i] * numbers[i];
}

//Outer loop
for (int i = 0; i < n - 2; i++)
{
//Inner loop
for (int j = i+1; j < n - 1; j++)
{
int sum = squares[i] + squares[j];

//If the number corresponding to the hypotenuse * hypotenuse exists
//in the remaining array we have found a pythagorean triplet
//This would take O(log N)
int k = BinarySearch(squares, j+1, n);
if (k != -1)
{
Console.Writeline("{0}^2 + {1}^2 = {2}^2", numbers[i], numbers[j], numbers[k]);
}
}
}
}``````

Since BinarySearch will run in O(log N) and for every iteration of Inner loop we will be calling the BinarySearch on a smaller array then previous iteration it should take total time according to the sum of the following series:

log (N-1) + log (N-2) + ... + log 1

I'm not sure what's the outcome of the above series. But if it is less than N then combined with the Outer loop overall it should be better than O(N ^2).

What do you think?

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

``````public void FindPythagoreanTriples(int[] numbers)
{
int n = numbers.Length;

//This would take O(N log N)
Sort(numbers);

int[] squares = new int[n];

//This would take O(N)
for (int i = 0; i < n; i++)
{
squares[i] = numbers[i] * numbers[i];
}

//Outer loop
for (int i = 0; i < n - 2; i++)
{
//Inner loop
for (int j = i+1; j < n - 1; j++)
{
int sum = squares[i] + squares[j];

//If the number corresponding to the hypotenuse * hypotenuse exists
//in the remaining array we have found a pythagorean triplet
//This would take O(log N)
int k = BinarySearch(squares, j+1, n);
if (k != -1)
{
Console.Writeline("{0}^2 + {1}^2 = {2}^2", numbers[i], numbers[j], numbers[k]);
}
}
}
}``````

Since BinarySearch will run in O(log N) and for every iteration of Inner loop we will be calling the BinarySearch on a smaller array then previous iteration it should take total time according to the sum of the following series:

log (N-1) + log (N-2) + ... + log 1

I'm not sure what's the summation of the above series.

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

The series sums to theta(NlogN). However, you do this for each of N iterations of the outer loop, so the overall algo is O(N^2logN).

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

public class pytho {

public static int numPythagoreanTriplets(int N) {
int x = 0;
for (int c = N; c > 1; c--) {
int squarec = c*c;
for (int b = c-1; b > 1; b--) {
int squareb = b*b;
int squarea = squarec - squareb;
if (squarea > squareb) continue;
double a = Math.sqrt(squarea);
if ( Math.abs(a - Math.floor(a)) ==0) {
x++;
}
}
}
return x;

}
public static void main(String[] args) {
int v = numPythagoreanTriplets(1000);

System.out.println(v);

}

}

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

This code works for all test cases:
int n;
cout<<"Enter the size of array";
cin>>n;
vector<int> a;
for(int i=0;i<n;i++)
a.push_back(0);
cout<<"Enter the array elements";
for(int i= 0;i<n;i++)
{
cin>>a[i];
a[i]*=a[i];//square each element
}
//Sort the array
sort(a.begin(),a.end());
// Main Logic
for(int k=n-1;k!=0;k--)
for( int i= 0, j=k-1; i!=j; )
{
if( a[i]+ a[j] == a[k])
{

cout<<"array elements"<<sqrt(double(a[i]))<<"\t"<<sqrt(double(a[j]))<<" and"<< sqrt(double(a[k]))<<" form a triplet"<<"\n";
break;
}
else if( a[i]+ a[j] < a[k])
i++;
else
j--;
}

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

Time complexity O(n^2)

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

Euclid's formula is a fundamental formula for generating Pythagorean triples given an arbitrary pair of positive integers m and n with m > n. The formula states that the integers
a=m.m-n.n,b=2.m.n,c=m.m+n.n
form a Pythagorean triple.
example:
if m = 5 and n = 7, n.n - m.m = 49 - 25 = 24, 2.m.n = 70, and
n.n + m.m = 49 + 25 = 74.

24, 70, 74 is a PT, because 24.24 + 70.70 = 74.74.

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

This doesn't answer how you intend to check for Pythagorean triplets within a specified list of numbers, like in this question.

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

apply this idea on (3,4,5), you will see your self...

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

You're completely missing the point. Yes, this works for generating triplets. What it doesn't do is provide any particularly efficient way to find all triplets present within a given list of numbers.

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

This comment has been deleted.

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

instead, define hashtable of size n (input size) and store all the elements. when calculating m = a[i]*a[i] + a[j]*a[j] , find sqrt (m) and check if it exists in hashtable or not . O(n) space.

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

finding a[i]^2 +a[j]^2 is O(n^2)

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

@guest Thanks Guest098.... you are right...i'll change it but it's not O(n) it is O(inputArray[lastIndex])...

@niraj.niraj yes, it is O(n^2).. i can't do less than O(n^2).do u have any idea ?

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

I am trying to write the code, but my algo is n^2.

I don't think it can be less than this.

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

@niraj.nijju yes
that's what i thought tooo...

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

Here is my algo :

``````j,k;
for i from 2:N-1
j=0;k=i-1;
while(j < k)
if(A[j]*A[j] + A[k]*A[k] < A[i]*A[i])
j++;
else if(A[j]*A[j] + A[k]*A[k] > A[i]*A[i])
k--;
else
break;
print i,j,k;``````

Now as you can see, any Pythagorean triplet the 2nd larger number is much nearer to largest, and smallest number is much smaller to 0, so the loop will run very less, or i can say for const(ya i know in some cases the loop might run for n/3 many cases also). amount of time for any "i", so here i can say , that on an avg. the complexity somewhat less then O(n*n)

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

One of the ways is to do this is in O(N) as time complexity and O(N) as space complexity by putting the elements in Map, which is not difficult to implement. Another way to implement in O(N log N) as time complexity and O(1) as space complexity was something that interviewer was probably looking for. Here is the code for O(N logN) and O(1) for time and space respectively.

``````public void findPythagoreanTriplets (int[] x) {
//Input [ 9, 2, 3, 4, 8, 5, 6, 10]
//Output [3,4,5] and [6,8,10]
Arrays.sort(x);
int j = x.length - 1;
for (int i = 0; i < x.length - 1 && j < x.length;) {
double d1 = Math.pow(x[i++], 2) + Math.pow(x[i], 2);
double d2 = Math.pow(x[j], 2);
System.out.println(d2);
i--;
if (d1 == d2) {
System.out.println("[" + x[i] + "," + x[i + 1] + "," + x[j] + "]");
i++;
j = x.length - 1;
} else if (d2 > d1) {
j--;
} else if (d2 < d1 || j <= (i + 1)) {
i++;
j = x.length - 1;
}
}
}``````

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

Why would the first two numbers of the triplet be next to each other in the input? There's no such restriction.

I doubt you can beat O(n^2) for this problem.

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

You can keep anywhere you want.. you are sorting the array anyways, so it does not matter. O(N log N) is the solution for this.

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

Not correct, I'm afraid. See the test case [9, 36, 2, 12, 16, 39, 8, 20, 6, 10, 15] here: ideone. com/0lJ8M3

I expect to find [12 16 20] and [15 36 39], but no such luck.

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.