Amazon Interview Question
Country: India
Interview Type: In-Person
There are two solutions
1. Naive O(n^3) approach
Use three for loops and check for Pythagorean property.
2. Better O(N^2) approach
A.Convert original array into an array containing square of all the elements. Call it A.
B.Put all elements of A into an HashMap say H.
C. Do below steps
For each element in A
{
required sum=A[i]
call printSum(required_sum,A,H)
}
void printSum(required_sum,A,H)
{
for each element in A say x
check if sum-x is present in H
if yes print square root of required_sum,x and required_sum -x.
}
Thus the overall complexity of this approach is O(n^2)
Note:
Some Special handling also needs to be done if array contains duplicate,else you will return the same triplets again and again.
How is your code O(n^2)
For each element in A (executed n times) -> for each element in A say x (executed n times) -> if sum-x is present in H (May be log(n) if sorted)
Loop->Loop->Search
Hi Amit H is a HashMap not an array.And I believe you already know searching for an element in an HashMap takes O(1) time.
>> searching for an element in an HashMap takes O(1) time.
It's not always true. Technically speaking, it takes about O(1) + O(elementCount/mapSize) time.
We need to find i,j,k such that
i*i + j*j = k*k
Step-1 Sort the array
for(int k = n-1; k >=2; k--)
{
while(i <j)
{
if(i*i + j*j == k*k)
{
break;
}
if(I*i + j*j < k*k)
{
i++;
}
else
{
j--;
}
}
Note:- This way one can find only 1 tuple of i,j,k
If we want all possible tuple then we need extra space and scan array indexwise, check if we can find k*k - j*j = i*i in stored extra array and that element should not be used. Once we printed that we find then flag that both element used.
int arr[11] = {0,1,2,4,3,5,6,8,7,10,11} ;
int tempArr [11] ;
int temp ;
for ( int a = 0 ; a < 10 ; a++ )
{
if ( arr [a] > arr [a+1] )
{
temp = arr [a+1] ;
arr [a+1] = arr [a] ;
arr [a] = temp ;
tempArr [a] = temp * temp ;
cout << tempArr[a] << "\t" ;
}
else {
tempArr [a] = arr [a] * arr[a] ;
cout << tempArr[a] << "\t" ;
}
}
int i = 0 ;
int j = 1, k = 2, count = 0 ;
while ( count < 9)
{
if ( tempArr[i] + tempArr [j] == tempArr [k] )
{
cout << "{" << arr[i] << "," << arr[j] << "," << arr[k] << "}" << endl ;
}
else{}
i++;
j++;
k++;
count++;
}
public static void main(String[] args)
{
int[] input = new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
Set<Integer> elements = new HashSet<Integer>();
for (int i = 0; i < input.length; i++) {
elements.add(input[i]*input[i]);
}
System.out.println(Arrays.toString(input));
int n = input.length;
for (int i = 0; i < n; i++) {
int j = i;
while(j < n-1)
{
j++;
Integer sum = input[i]*input[i]+input[j]*input[j];
if (elements.contains(sum)) {
System.out.println(input[i] + "," + input[j] + "," + (int)(Math.sqrt(sum)));
}
}
}
}
int[] arr = { 5,6,7,8,9,10,11,12,13,14,15,17,24,25 };
int[] sqArr = new int[arr.Length];
for (int i = 0; i < arr.Length; i++)
{
sqArr[i] = arr[i] * arr[i];
}
for (int i = 0; i < arr.Length - 2; i++)
{
for (int j = i + 1; j < arr.Length - 1; j++)
{
for (int k = j + 1; k < arr.Length; )
{
if (sqArr[i] + sqArr[j] > sqArr[k])
{
k++;
}
else if (sqArr[i] + sqArr[j] < sqArr[k])
{
break;
}
else
{
Console.WriteLine("Pairs: {0}, {1}, {2}", arr[i], arr[j], arr[k]);
break;
}
}
}
findPythagorean(int[] arr) {
HashMap<Integer, String> arrList = new HashMap<Integer, String>();
int[] temp = arr;
for (int i = 0; i < temp.length; i++) {
for (int j = i + 1; j < temp.length; j++) {
// System.out.print((pow(temp[i]) + pow(temp[j])) + " ");
arrList.put((pow(temp[i]) + pow(temp[j])),
temp[i] + ", " + temp[j]);
}
System.out.println();
}
for (int i = 0; i < temp.length; i++) {
int var1 = pow(temp[i]);
if (arrList.get(var1) != null) {
String var2 = arrList.get(var1);
System.out.println(var2 + ", " + temp[i]);
}
}
}
static int pow(int i) {
return i * i;
}
This is the best answer.
The key is mapping it to a known problem (half the questions here are small changes to a known problem)
@eugene: You have missed the point. There is no proof that this is 3SUM hard. Yes, it can be _reduced TO_ 3SUM, but there is no proof of the vice-versa case...
Don't put words in my mouth. I said the interviewer expected you to map it to 3SUM. 3SUM is easy to solve, so this is clearly the route for a coding interview.
Not everyone applying to programming jobs have a Ph.D. in number theory... what more would they expect?
public static void findPythagoreanTriplets(int[] array)
{
int[] newArray = new int[array.length];
Map<Integer,Integer> map = new HashMap<Integer, Integer>();
int count = 0;
for (int i : array) {
newArray[count] = i*i;
map.put(i, newArray[count]);
count++;
}
for (int i = 0; i < newArray.length - 1; i++) {
for(int j = i+1; j < newArray.length; j++)
{
int sum = newArray[i] + newArray[j];
if( map.containsValue(sum))
System.out.println((int)Math.sqrt(newArray[i])+","+(int)Math.sqrt(newArray[j])+","+(int)Math.sqrt(sum));
}
}
}
/
* time: O(N)
* space: O(N)
*/
private void printPythagorian( int[] arr ){
Set<Integer> set = new HashSet<>();
for( int value : arr ){
set.add( value );
}
for(int value1 : arr ){
if( value1 % 3 == 0 ){
int k = value1 / 3;
int value2 = 4*k;
int value3 = 5*k;
if( set.contains(value2) && set.contains(value3) ){
System.out.println( String.format("(%d, %d, %d)", value1, value2, value3) );
}
}
}
}
/*
* time: O(N)
* space: O(N)
*/
private void printPythagorian( int[] arr ){
Set<Integer> set = new HashSet<>();
for( int value : arr ){
set.add( value );
}
for(int value1 : arr ){
if( value1 % 3 == 0 ){
int k = value1 / 3;
int value2 = 4*k;
int value3 = 5*k;
if( set.contains(value2) && set.contains(value3) ){
System.out.println( String.format("(%d, %d, %d)", value1, value2, value3) );
}
}
}
}
/*
* time: O(N*lgN)
* space: O(1)
*
* a^2 + b^2 = c^2
*
* a = 3k
* b = 4k
* c = 5k
*
*/
private void printPythagorian( int[] arr ){
Arrays.sort(arr);
for(int i = 0; i < arr.length-2; i++ ){
int value1 = arr[i];
if( value1 % 3 == 0 ){
int k = value1 / 3;
int value2 = k << 2; // 4*k
int value3 = value2 + k; // 5*k
if( Arrays.binarySearch(arr, i+1, arr.length, value2) > 0 && Arrays.binarySearch(arr, i+2, arr.length, value3) > 0 ){
System.out.println( String.format("(%d, %d, %d)", value1, value2, value3) );
}
}
}
}
public static void PythagoreanTriples(int input[], int output[], int inputIndex, int outputIndex)
{
if (outputIndex == 3)
{
if ((output[0]*output[0] == output[1]*output[1] + output[2]*output[2]) ||
(output[1]*output[1] == output[0]*output[0] + output[2]*output[2]) ||
(output[2]*output[2] == output[0]*output[0] + output[1]*output[1]))
{
for (int j = 0; j < output.length; j++)
out.printf("%d ", output[j]);
out.println();
}
return;
}
for (int i = inputIndex; i < input.length; i++)
{
output[outputIndex] = input[i];
outputIndex++;
PythagoreanTriples(input, output, i+1, outputIndex);
outputIndex--;
}
}
int[] testInput = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 10, 11};
int[] testOutput = new int[]{0, 0, 0};
out.println("Pythagorean Triples");
PythagoreanTriples(testInput, testOutput, 0, 0);
Pythagorean Triples
3 4 5
6 8 10
Here is an O(n lg n) approach:
void AllPythagorean(int *a, int n)
{
try
{
if(a==NULL || n<3) throw "\nInvalid Input(s)\n";
}catch(const char *s)
{
puts(s);
return;
}
int i,p,q,tmp;
for(i=0;i<n;i++)
a[i]=a[i]*a[i];
for(i=n-1;i>=2;i--)
{
p=0;
q=i-1;
tmp=a[i];
while(p<q)
{
if(a[p]+a[q]==tmp)
{
printf("%d\t%d\t%d\n",a[p],a[q],tmp);
break;
}
else if(a[p]<=a[q])
p++;
else
q--;
}
}
}
def find_all_pythag_triples(intlist):
retlist=[]
trip_iterator = triple_iterator(intlist)
for triple in trip_iterator:
test_result = test_triple(triple)
if test_result == True:
retlist.append(triple)
return retlist
def triple_iterator(testlist):
triplist=[]
num_items = len(testlist)
for item1 in range(num_items):
for item2 in range(num_items):
for item3 in range(num_items):
if item1!=item2 and item2!=item3 and item3!=item1:
yield (testlist[item1],testlist[item2],testlist[item3])
def test_triple(triple):
if triple[0]*triple[0] + triple[1]*triple[1] == triple[2]*triple[2]:
return True
else:
return False
testlist = [1,3,4,5,6,7,8,10,11]
print find_all_pythag_triples(testlist)
you can do this in O(n^2) time complexty and O(n) space complexity.
Algo:-
1)sort the array
2)fix first position in array and iterate for second and 3rd position.As you know array is sorted then for every pair the next pythagorous triplate lie beyond the previous triplate.
so you can iterate in inner loop atmost n time for outer loop.so the complexity is O(n^2)
code below:---
#include<stdio.h>
int main()
{
int a[]={1,3,4,5,6,7,8,10,11};
int n=sizeof(a)/sizeof(int);
for(int i=0;i<n-2;i++)
{
int k=i+2;
for(int j=i+1;j<n-1;j++)
{
while(k<n && (a[i]*a[i] + a[j]*a[j])>(a[k]*a[k]))
k++;
if(k==n)
break;
if((a[i]*a[i] + a[j]*a[j])==(a[k]*a[k]))
printf("\n%d %d %d",a[i],a[j],a[k]);
}
}
return 0;
}
import java.util.*;
public class HelloWorld{
public static void main(String []args){
int arr[]={1,2,3,4,5,6,7,8,9,10,12,13,11,60,61};
int prim[]={3,5,7,11};
int r,l;
List<Integer> prime=new ArrayList<Integer>();
for(int i=0;i<4;i++){
prime.add(prim[i]);
}
List<Integer> n=new ArrayList<Integer>();
for(int i=0;i<arr.length;i++)
{
n.add(arr[i]);
}
double v1,v2,v3;
// for(int e=0;e<arr.length;e++){
int brr[]=new int[arr.length];
for(int i=0;i<arr.length;i++)
brr[i]=arr[i];
Integer aa=0,bb=0,cc=0;
List<Integer> temp=new ArrayList<Integer>();
for(int i=0;i<arr.length;i++)
{
temp.add(arr[i]);
}
for(int j:n){
if(prime.contains(j)){
//System.out.println("j"+j);
double a,b;
v1=(double)j;
v2=Math.ceil(((j*j)+1)/2);
v3=Math.ceil(((j*j)-1)/2);
l=((int)v1>(int)v2?((int)v1>(int)v3?(int)v1:(int)v3):((int)v2>(int)v3?(int)v2:(int)v3));
if(l==v1){
a=v2;
b=v3;
}
else if(l==v2){
a=v1;
b=v3;
}
else{
a=v1;
b=v2;
}
// System.out.println("low"+l);
r=((int)a*(int)a)+((int)b*(int)b);
l=((int)l*(int)l);
// System.out.println(v3+" "+v2+" " +v1+" "+l+" "+r);
if(n.contains((int)v2) && n.contains((int)v3) && l==r){
// System.out.println(v3+" "+v2+" " +v1+" "+l+" "+r);
System.out.println(v1+" "+v2+" "+v3);
}
}
else
{
// for(int w:temp){
if(j%3==0){
aa=j;
bb=4*(j/3);
cc=5*(j/3);
if(temp.contains(bb) && temp.contains(cc)){
System.out.println(aa+" "+bb+" "+cc);
// System.out.println(temp.indexOf(aa));
brr[temp.indexOf(aa)-1]=0;
brr[temp.indexOf(bb)-1]=0;
brr[temp.indexOf(cc)-1]=0;
}
//}
}
}
}
}
}
import java.util.*;
public class HelloWorld{
public static void main(String []args){
int arr[]={1,2,3,4,5,6,7,8,9,10,12,13,11,60,61};
int prim[]={3,5,7,11};
int r,l;
List<Integer> prime=new ArrayList<Integer>();
for(int i=0;i<4;i++){
prime.add(prim[i]);
}
List<Integer> n=new ArrayList<Integer>();
for(int i=0;i<arr.length;i++)
{
n.add(arr[i]);
}
double v1,v2,v3;
// for(int e=0;e<arr.length;e++){
int brr[]=new int[arr.length];
for(int i=0;i<arr.length;i++)
brr[i]=arr[i];
Integer aa=0,bb=0,cc=0;
List<Integer> temp=new ArrayList<Integer>();
for(int i=0;i<arr.length;i++)
{
temp.add(arr[i]);
}
for(int j:n){
if(prime.contains(j)){
//System.out.println("j"+j);
double a,b;
v1=(double)j;
v2=Math.ceil(((j*j)+1)/2);
v3=Math.ceil(((j*j)-1)/2);
l=((int)v1>(int)v2?((int)v1>(int)v3?(int)v1:(int)v3):((int)v2>(int)v3?(int)v2:(int)v3));
if(l==v1){
a=v2;
b=v3;
}
else if(l==v2){
a=v1;
b=v3;
}
else{
a=v1;
b=v2;
}
// System.out.println("low"+l);
r=((int)a*(int)a)+((int)b*(int)b);
l=((int)l*(int)l);
// System.out.println(v3+" "+v2+" " +v1+" "+l+" "+r);
if(n.contains((int)v2) && n.contains((int)v3) && l==r){
// System.out.println(v3+" "+v2+" " +v1+" "+l+" "+r);
System.out.println(v1+" "+v2+" "+v3);
}
}
else
{
// for(int w:temp){
if(j%3==0){
aa=j;
bb=4*(j/3);
cc=5*(j/3);
if(temp.contains(bb) && temp.contains(cc)){
System.out.println(aa+" "+bb+" "+cc);
// System.out.println(temp.indexOf(aa));
brr[temp.indexOf(aa)-1]=0;
brr[temp.indexOf(bb)-1]=0;
brr[temp.indexOf(cc)-1]=0;
}
//}
}
}
}
}
}
A Pythagorean triple consists of three positive integers a, b, and c, such that a^2 + b^2 = c^2:)
Make a list of squares {1,9,16,25,....} and every square add to a hash table. Then take every two squared elements from a list from previous step and check if their sum is in a hash table. Complexity O(n^2).
- joe kidd August 31, 2013