## Amazon Interview Question for SDE-2s

Team: Global Payment Services
Country: India
Interview Type: Phone Interview

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

a little changed 3sum question.

1. get the square of the array.

2. iterate from the last element of the array, let us say i, make it as the target sum. and use 2 pointer, one is from 0 and the other one is from i-1. if the current sum > target, right pointer --; else left pointer ++ ;

run time O(n^2)

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

can't see if the solution will work, " if the current sum > target, right pointer --; " array is not sorted , how will this work ?

the real N^2 involves an extra data structure (bring N^3 down to N^2 in trade of space)-

use a HashTable to store a Key Value Pair, where the key is the square of the value and the value is the index.

Iterate from the beginning of the array using 2 pointers, calculate P1^2 + P2^2 and check if it matches any value in the hash table.
The iteration costs N^2 .

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

This solution works for a sorted array.
Based on this algorithm I have completed the code and it does work fine.
And note I use below struct as array items so that original value/index are recorded. Sort uses squareValue as key.

``````struct {
unsigned long squareValue;
int value;
int index;
}``````

Sorting costs O(N*logN), iteration costs O(N^2).

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

Square up each of the elements of the array and put them in a hash table. This requires O(n) extra space. Then for all of the n^2 combinations of elements, check if their sum of their squares exists in the hash table with O(n^2) time complexity.

A complete graph of the elements with nodes holding the squares of elements may also get the job done. Running DFS from each node and traversing a depth of up to 3 levels, can help check for the existence of Pythagorean squares.

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

Assuming the numbers are whole numbers, not fractional

1. Get the maximum and minimum number of given array and store square numbers into hashing DS.

2. Store squares from minimum to that maximum number in a hashing DS (if it's not suitable then use BST for fast searching). Tag immediate lowest square with each element.
Ex: Maximum number is 10 and minimum is 2. Store 2 ^2 to 10^2. For 16 tag 9.

3. Iterate the hash table, suppose 16 found go to previous hash table/tree and find possible triplet. So for 16, tagged number is 9 now remaining is 7 and 7 does not exist. Result is cancel. Suppose 25 found, tagged number is 16 then find 9, both found. Now find 16 and 9 in original list.

The complexity depends on the range given. For large range space should be high.

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

Ok Guys!

I found the solution. Sort the original list. Then square those numbers and put it into a Hash Set (maintain duplicate number also).

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

I think I know the solution:

Sort the original list. Then square those numbers and put it into a Hash Set (maintain duplicate number also).

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

Note when sorting the original list, you may lose the index information, so probably we should generate a index map that map the index from sorted array to the origina array's index. This algorithm may be O(n^2).

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

A second thought is, we can have a struct with original value, square value and its original index, sort the struct with sqaure value, and do the search for the pythagorean triplets. This is O(N*logN)
Then we have both the original value (even it's negtive) and index.

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

I did answered along the same line that most of you have answered. However, interviewer gave following remark to my answer.

1. If input array has negative numbers? in which case, squaring it could result in printing invalid Pythagorean triplets.
2. If we have sort, then we will loose the index numbers which we have retrieve to print the Triplets.
3. Interviewer seems to be in agreement with time complexity. i.e O(n^2)*log(n).
[O(n^2) to pick two numbers] * [O(log n) for binary search]. But for binary search, i would have to sort and it is erroneous. Here i was caught!

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

Nothing but a 3-sum question.
Easy.

O(n^2)

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

can we avoid sorting and just use hashtable if space is not a constraint, it takes O(1) time to lookup the element.

``````public class PythogoreanTriplets {

public static void main(String[] args) {

int[] array = {3, 2, 1, 5, 6, 4, 9, 10};

Map<Integer, Integer> hashmap = new HashMap<Integer, Integer>();

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

hashmap.put(array[i] * array[i], i);
}

for (int i = 0; i < array.length; i++) {
for (int key : hashmap.keySet()) {
if (hashmap.containsKey(array[i] * array[i] + key)) {

System.out.println("the triplets are: " + array[i] + " " + array[hashmap.get(key)] + " " + array[hashmap.get(array[i] * array[i] + key)]);
}
}

}
}

}``````

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

improved version of the above code

``````public class PythogoreanTripletSort {

public static void main(String[] args) {

int[] array = {3,7, 2,24,12,1,5,6,4,9,13,10,25};

int[] newarray = new int[array.length];
List<int[]> list = new ArrayList<int[]>();

Map<Integer, Integer> hashmap = new HashMap<Integer, Integer>();

for (int i = 0; i < array.length; i++) {
newarray[i] = array[i] * array[i];
hashmap.put(newarray[i], i);
}

QuickSort q = new QuickSort();
q.quickSort(newarray, 0, newarray.length - 1);

for (int i = 0; i < newarray.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (hashmap.containsKey(newarray[i] - newarray[j])) {
System.out.println("");
list.add(new int[]{array[hashmap.get(newarray[i])], array[hashmap.get(newarray[j])], array[hashmap.get(newarray[i] - newarray[j])]});
System.out.print(array[hashmap.get(newarray[i])]+"  "+array[hashmap.get(newarray[j])]+" "+array[hashmap.get(newarray[i] - newarray[j])]);
}

}

}

}

}``````

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

``````{

public class FindPythagoreanTripltes {

public static void main(String[] args) {
findPythagoreanTriplets();
}

public static void findPythagoreanTriplets()
{

int arr[]= { 3,6,9,4,8,5,10,12,15 };

for(int i=0;i<arr.length;i++)
{
for(int j=1;j<arr.length;j++)
{
for(int k=2;k<arr.length;k++)
{
if((Math.pow(arr[i],2)+Math.pow(arr[j],2))==Math.pow(arr[k],2))
{
System.out.println("Pythagoreans sets= { "+arr[i]+","+arr[j]+","+arr[k]+" }");
}
}

}
}

}
}``````

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

Output:-
Pythagoreans sets= { 3,4,5 }
Pythagoreans sets= { 6,8,10 }
Pythagoreans sets= { 9,12,15 }
Pythagoreans sets= { 8,6,10 }
Pythagoreans sets= { 12,9,15 }

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

``````/**
* Step1: Square each of the elements in the array [O(n)]
* Step2: Sort the array [O(n logn)]
* Step3: Find all the pairs whose sum is equal to the an element in the array [O(n logn)]
*
* Time Complexity: O(n2)
*/``````

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

Total time complexity is O(nlogn).

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

the overal complexity would be O(n2logn)

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

It can be done in O(n) because the numbers are integers. Pythagorean integers are 3,4,5. and all of the multiplications od them like 6,8,10, ....
Put all the elments in a hash map. After that iterate through the elements and look for the corresponding other 2 missing. This way we would obtain duplicates but these can easily be avoided if we look only for multiplications of 3, instead of 3,4,5.

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

13^2 = 12^2 + 5^2

So a O(n) solution does not work

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.