Interview Question Front-end Software Engineers
@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 February 23, 2011Iterate through the list comparing each three adjacent integers.
Return true on the first match.