Interview Question Front-end Software Engineers
0of 0 votesWrite a function
int triangle(int A[], int n);
which given a zero-indexed array A of n integers returns 1 if there exists triple i,j,k ($i\not=j\not=k$, $0\le i,j,k <n$) such that:
A[i] + A[j] > A[k]
A[i] + A[k] > A[j]
A[j] + A[k] > A[i]
or returns 0 otherwise.
Examples:
For:
A[0]=10, A[1]=2, A[2]=5, A[3]=1, A[4]=8, A[5]=20
your function should return 1, since for i=0,j=2,k=4 all conditions are fullfiled (i.e. A[2]+A[4]>A[0]).
For:
A[0]=10, A[1]=50, A[2]=5, A[3]=1
your function should return 0.
@kiran lets say the elements are a1 a2 a3 a4 a5 and they are in sorted order.
let us look at a2 a3 a4 case.
if(a2 + a3 <= a4) then a4 cannot be the greatest element in the i,j,k triples as the maximum sum of two elements less than a4 is a2+a3.
Similarly we will check for every element if it can be the greatest element in the list(i.e iterating over the list). If there is no such element then there is no possible maximum element in a triplet and consequently no required triplet exists.
I feel the answer is O(n square)...first sort the array, then if the sum of any two smaller numbers is greater than a larger number, return true;
for(i=0 to n-2)
{ for(j=i+1 to n-1)
{ if(a[i]+a[j] > a[j+1])
return true;
}
}
return false;
correct me if I am wrong.. :)
@Kiran
Kiran.. you are totally wrong...
This was not the solution for that question...
There might be shortcuts, but the following is the simple way to solve the problem
<?php
function test($a)
{
$arrk=$a;
$arri=$a;
$arrj=$a;
$n=count($arrk);
foreach($arrk as $keyk=>$k)
{
foreach($arri as $keyi=>$i)
{
if($keyi!=$keyk)
{
foreach($arrj as $keyj=>$j)
{
$cond1=false; $cond2=false; $cond3=false;
if($keyj!=$keyk and $keyj!=$keyi)
{
if(($i+$j)>$k) $cond1=true;
if(($i+$k)>$j) $cond2=true;
if(($k+$j)>$i) $cond3=true;
if($cond1 and $cond2 and $cond3) {
return true;
}
}
}
}
}
}
return false;
}
$a=array(10,2,5,1,8,20); // Should return true
//$a=array(10,50,5,1); // should return false
if(test($a)) echo "Yes"; else echo "No";
?>
The problem can be solved in O(n) time . Find the first 2 maximum's. Then for every element check if that value is smaller than the sum of the above 2 values. If its true for atleast one such value return 1 otherwise return 0.
Sort the list.
- Anon on February 23, 2011 Edit | Flag ReplyIterate through the list comparing each three adjacent integers.
Return true on the first match.