Amazon Interview Question SDE-2s
Team: Global Payment Services
Country: India
Interview Type: Phone Interview
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 .
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).
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.
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.
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).
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).
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!
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)]);
}
}
}
}
}
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])]);
}
}
}
}
}
{
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]+" }");
}
}
}
}
}
}
/**
* 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)
*/
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.
a little changed 3sum question.
- buffhack January 20, 20141. 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)