## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

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

1)sort the array
2)find the square of all the numbers
3)use 3SUM techinque (search 3SUM in wiki)

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

We need to print indices also.. In that case if we sort vaues
Actual indices will be lost right??

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

use tow for loops to find a2+b2 and serach for that value in the sorted array.

O(n2logn) is complexity.

otherwise, if you store n numbers in hashtable O(n2) time and O(n) space complexity.

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

``````public class PythaTriplet {
public static void main(String[] args) {
int [] A={2, 9, 4, 5, 3, 60, 8, 30, 33, 45, 10, 40, 7, 50, 6};
int l=A.length;
int []b=sortArr(A, l);
for(int i=0; i<l; i++){
System.out.print(b[i]+" ");
}
System.out.println("\n");
//pythaTripletN3(A, l);
pythaTripletN2(A, l);
}

static int [] sortArr(int []A, int l){
for(int i=0; i<l; i++){
for(int j=i+1; j<l; j++){
if(A[i]>A[j]){
int temp=A[i];
A[i]=A[j];
A[j]=temp;
}
}
}
return A;

}

//n^3
static void pythaTripletN3(int [] A, int l){
int c=0;
int []B=new int [l];
for(int i=0; i<l; i++){
B[i]=(int) Math.pow(A[i], 2);
}
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(B[i]+B[j]==B[k]){
System.out.print("("+A[i]+", "+A[j]+", "+A[k]+")"+" ");
c++;
}
System.out.println("\n"+c);
}

//n^2
static void pythaTripletN2(int [] A, int l){
int c=0;
int []B=new int[l];
for(int i=0; i<l; i++){
B[i]=A[i]*A[i];
}
for(int j=2; j<l; j++){
int k=0, n=j-1;
while(k<n){
if(B[k]+B[n]==B[j]){
System.out.print("("+A[k]+", "+A[n]+", "+A[j]+")"+" ");
k++;
n--;
c++;
}
else if(B[k]+B[n]>B[j])
n--;
else
k++;
}
}
int index=c;
System.out.print("\n\n"+"index= " +index);
}
}

output:
2 3 4 5 6 7 8 9 10 30 33 40 45 50 60

(3, 4, 5) (6, 8, 10) (30, 40, 50)

index= 3``````

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

In an array have all the square of the numbers stored, sort them and find the pair whose sum is the third number in that arrray

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

Hi,
Would this work when the triplets are not consequitive ?
Ex- 3,4,1,5,7,2,14,12,10,13

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

yes for triplet, it will give two set of numbers.

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

ok. Actually what i meant to ask was, to find a pair of numbers whose sum is the 3rd one, to find that pair, we have to add up every element with all the remaining elements (one at a time) and then look for the resultant number right ?

Am i missing anything ?

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

``````for (i = 0; i < N; i++)
Arr[i] = Arr[i] * Arr[i];
for (i = 0; i < N - 2; i++)
{
for (j = i + 1; j < N - 1; j++)
{
for (k = j + 1; j < N; j++)
{
if (Arr[i] + Arr[j] == Arr[k])
{
Console.WriteLine("{0}\t{1}\t{2}", Arr[i], Arr[j], Arr[k]);
Console.WriteLine("{0}\t{1}\t{2}", i, j, k);
}
else if (Arr[i] + Arr[k] == Arr[j])
{
Console.WriteLine("{0}\t{1}\t{2}", Arr[i], Arr[j], Arr[k]);
Console.WriteLine("{0}\t{1}\t{2}", i, j, k);
}
else if (Arr[k] + Arr[j] == Arr[i])
{
Console.WriteLine("{0}\t{1}\t{2}", Arr[i], Arr[j], Arr[k]);
Console.WriteLine("{0}\t{1}\t{2}", i, j, k);
}
}
}
}``````

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

``````int a[] = {1, 5, 4, 3, 9, 4, 30, 40, 25, 50};

for(int i = 0; i < a.length; i++)
a[i] *= a[i];

Arrays.sort(a);

if(a.length > 3)
{
for(int i = 2; i < a.length; i++)
{
int start = 0, end = i - 1;
while(start < end)
{
if(a[start] + a[end] == a[i])
{
System.out.println(Math.sqrt(a[start]) + "^2 + " + Math.sqrt(a[end]) + "^2 = " + Math.sqrt(a[i]) + "^2");
start++;
end--;
}
else if(a[start] + a[end] < a[i])
start++;
else
end--;
}
}
}
}``````

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

@anon: why can't we use the fact that in sorted array of all the squares."C" will be always ahead of of b.
a^2 + b^2 = c^2
I think that will decrease the number of comparisons.Won't it?

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

n^2logn

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

public static void pythogoreanTriplets(int[] a)
{
if (a.Length == 0)
return;
Dictionary<int, int> d = new Dictionary<int, int>();
for (int i = 0; i < a.Length; i++)
{
if (!d.ContainsKey(a[i] * a[i]))
{
}
}

for (int i = 0; i < a.Length; i++)
{
for (int j = 0; j < a.Length; j++)
{
int sumOfTwoNum = a[i]*a[i]+a[j]*a[j];

if (d.ContainsKey(sumOfTwoNum))
{
int dIndex;
d.TryGetValue(sumOfTwoNum, out dIndex);
Console.WriteLine("Triplet Found, {0} at index {1}, {2} at index {3}, {4} at index {5}",a[i],i,a[j],j,Math.Sqrt(sumOfTwoNum),dIndex);
d.Remove(sumOfTwoNum); // this is to prevent displaying duplicate results
}
}
}
}

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

``````public static void printPythagaron() {
int[] a = {3, 5, 7, 4, 12, 24, 11, 21, 13, 25, 8, 15, 17, 35, 37};
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < a.length; i++) {
map.put(a[i], a[i]);
}

for (int i = 0; i < a.length; i++) {

if (a[i] % 2 != 0) {
int b = a[i] / 2;
b = a[i] * b + b;
if (map.get(b) != null) {
if (map.get(b + 1) != null) {
System.out.println("("+ a[i] + "," + b + "," + (b + 1) + ")");
}
}
}
if(a[i]%4 == 0){
int b = a[i]/4;
b = a[i]*b-1;
if (map.get(b) != null) {
if (map.get(b + 2) != null) {
System.out.println("("+ a[i] + "," + b + "," + (b + 2) + ")");
}
}
}

}``````

}

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

Output:
(3,4,5)
(5,12,13)
(7,24,25)
(4,3,5)
(12,35,37)
(8,15,17)

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.