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 !!!

- Buzz_Lightyear November 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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--;
				}
			}
		}
}

- Buzz Lightyear November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous November 22, 2012 | Flag
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).

- eugene.yarovoi November 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Nik November 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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)

- Buzz_Lightyear November 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Buzz_Lightyear November 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- nikita++ November 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Buzz_Lightyear November 24, 2012 | Flag
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");
 }
}

Let me know your thoughts

- niraj.nijju November 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sunny December 19, 2012 | Flag
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)

- Avinash November 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Wyverald November 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

similar to how you do a binary search

- Avinash November 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous December 04, 2012 | Flag
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

- c7c7 November 22, 2012 | Flag Reply
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

- Sam November 23, 2012 | Flag Reply
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;


}

- puneet kumar November 25, 2012 | Flag Reply
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();
   }

- Kumaresan Saravanan November 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can u explain your logic ??

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

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.

- addy December 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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).

- eugene.yarovoi December 03, 2012 | Flag
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

- Anonymous November 28, 2012 | Flag Reply
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

- Kiran November 28, 2012 | Flag Reply
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?

- vstudio November 28, 2012 | Flag Reply
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.

- vstudio November 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi December 04, 2012 | Flag
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);

}

}

- sujith17889 November 29, 2012 | Flag Reply
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--;
}

- Ankit January 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Time complexity O(n^2)

- c7c7 November 22, 2012 | Flag Reply
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.

- mailtarunjain November 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sonesh November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This comment has been deleted.

- Administrator November 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- guest098 November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- niraj.nijju November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 ?

- Kumaresan Saravanan November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

- niraj.nijju November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kumaresan Saravanan November 25, 2012 | Flag
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)

- sonesh November 27, 2012 | Flag Reply
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;
			} 
		}
	}

- Sam November 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Sam November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi November 22, 2012 | 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