Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
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--;
}
}
}
}
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.
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).
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.
@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)
@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.
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.
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");
}
}
Let me know your thoughts
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)
# 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
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
#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;
}
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();
}
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.
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?
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.
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);
}
}
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--;
}
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.
This doesn't answer how you intend to check for Pythagorean triplets within a specified list of numbers, like in this question.
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.
@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 ?
I am trying to write the code, but my algo is n^2.
I don't think it can be less than this.
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)
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;
}
}
}
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.
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.
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.
- Buzz_Lightyear November 22, 2012Step 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 !!!