Amazon Interview Question
Developer Program EngineersCountry: United States
This would be depend on the good hash function. But average it would be good if we provide Kn space, k>1.
Space Complexity will grow high for using hash table. Inefficient and not feasible solution. C^2 for each number has to be stored thus is not possible for large triplets.
We need to sort the array to be able to achieve O(n^2) performance.
void findTriplets(int *input, int size)
{
int a, b, c, i;
for (c = 0; c < size; c++)
{
int result = input[c] * input[c];
a = 0;
b = size - 1;
while (a <= b)
{
if ((input[a] * input[a]) + input[b] * input[b]) < result) /* a^2 + b^2 < c^2 */
a++;
else if (input[a] * input[a]) + input[b] * input[b]) > result) /* a^2 + b^2 > c^2 */
b--;
else
printf("triplet found: %d %d %d \n", input[a], input[b], input[c]);
}
}
}
}}}
Time: O(n^2) Space: O(1)
small correction needed..
here
b=c-1; and c has to start from size-1 to 0;
since a^2+b^2=c^2 ... only when c>a &c>b;
Since If we will square any negative number then it will become positive number. So we can change all negative number to +ve it will take O(n) time complexity. After that sort array which will take nlogn. Now in end hold first number and start iteration from i = 0 to i = n-1 and j =n-1 to j= 0 where i must be less than j. In this way we can find triplets.
Note :- It will give solution in O(n*n) time complexity and O(1) space complexity if interviewer is allowing you to change array other wise you can modify quick sort code and instead of sorting it on the basis of a[i] we can use abs(a[i]).
1) First square all the numbers.
2) Sort the Array
3) Store this array element in a Hashset.
4)Open a for loop , which loops from starting element of the array.
5) open another for loop, which loops from next to starting element of array.
6) Add these two elements and check whether the sum is present in HashSet, if true break else continue.
7) By using HastSet we can reduce the time complexity for searching the result.
More formally: given a positive integer n, the triple can be generated by the following two procedures: (see mcs.surrey.ac.uk/Personal/R.Knott/Pythag/pythag.html )
a = 2n+1, b = 2n(n+1), c = 2n(n+1)+1
Example: When n = 2, the triple produced is 5, 12, and 13. (This formula is actually the same as method I, substituting m with 2n + 1.)
Alternatively, one can generate triples from even integers using the following formulas. Given that m is a positive even number,
a = 2m, b = m^2-1, c = m^2+1
Example: When m = 4, the triple produced is 8, 15, and 17 (this formula is another specific case of method I, substituting n with 1).
Can do it in O(nLogn) [sort]+n Logn[find corresponding numbers] after sorting and using above formula.
actually, we can achieve o(n*n) at least for time complexity and O(1) for space complexity without HASH. We first need to change the value to its square one with its original sign, for example, 3=>9, -3=>-9. Then sort them using the fast sort according to the absolute value of the element, abs(9)=9, abs(-9)=9 in nlogn time complexity. then we are going to find the triple, using A+B=C, A=abs(a), B=abs(b), C=abs(c), a,b,c is the element of the square value. For each fixed C value, we know can search the pair A+B =C in O(n) time, so overall we can have O(n*n) time complexity for the case. if we choose the in place quick sort algorithm, the space complexity is O(1).
In-place quicksort has logarithmic space complexity.
If you replace each integer by its square, it could overflow. For k-bit integers, you could need up to 2k bits to store the square of that number. Basically, if you were given an array of ints, in the worst case, you'd have to make an array of longs to hold the squares.
To find the pythagorean triplet.
A^2 + B^2 = C^2
You can simplify both the equation for using two variables.
A = n^2 - m^2;
B = 2nm;
C = n^2 + m^2;
for all n> m.
Now in the for loop print (A,B,C) for every pair of numbers by using above function.
Time Complexity O(n) Space O(1);
Hash the square of all elements.
- kill -9 March 29, 2013Simply Use two loops to get all possible a^2 + b^2 combinations and check if c^2 is in hash. T
Time: O(n^2). Space: O(n)