Linkedin Interview Question
Software DevelopersCountry: United States
Interview Type: Phone Interview
Sure- here you go
public boolean triangleTripletExists(int[] arr) {
mergeSort(arr);
int i, j, k;
i = 0;
j = 1;
k = 2;
for (k = 2; k < arr.length; k++) {
if (isTriplet(arr[i++], arr[j++], arr[k])) {
return true;
}
}
return false;
}
public boolean isTriplet(int a, int b, int c) {
boolean first, second, third;
first = ((a + b) > c);
second = ((a + c) > b);
third = ((c + b) > a);
return (first && second && third);
}
If you have already sorted the array, you don't really need to verify that all the three conditions hold true.
Lets say a and b are the smallest of the three sides. If a+b>c is true, then obviously b+c>a and c+a>b will follow.
So it is not listing exclusively all possible triangles triplets from a given list of segments. For example, if you get 3,4,5 as a list of segments, it will not list 3,3,4 as a triangle triplet. If it is allowed duplicate triangle triplets O(N^2) is available otherwise it will end up in O(N^3) since it is a 3 dimensional problem!!!
In this case, it will return whether such a triplet exists- Now the problem asks to return the segments, so this would simply be returning the elements arr[i], arr[j], and arr[k] if they are triplets.
for example: [2,3,4,5]
the possible triplets are <2,3,4> <2,4,5> and <3,4,5>
Your solution will miss 2,4,5 as you increment i with incrementing k.
One way to solve it is to increment i when you have exhausted the possibilities with j. However, after 2,3,4 - only 2,4,5 is possible.
Should prove that:
In sorted array A: if exist 3 indices i <=j<=k such that A[i], A[j], A[k] form a triangle, so do A[j-1],A[j],A[j+1].
The question is not asking to return all possible triplets. It is asking to return at most one.
public int[] getTriangleSides(int[] segments)
{
int []output={};
List<Integer> out = new ArrayList<Integer>();
for(int i=0;i<segments.length;i++)
{
out.add(segments[i]);
}
out.sort(null);
//the tripplet will come in order if exists after sorting
int i=0,j=1;
for(int k=2;k<segments.length;i++,j++,k++)
{
//assume segments[i],segments[j],segments[k] are three sides of a triangle
if( segments[i]+segments[j]>segments[k] &&
segments[j]+segments[k]>segments[i] &&
segments[k]+segments[i]>segments[j])
{
output[0]=segments[i];
output[1]=segments[j];
output[2]=segments[k];
break;
}
}
return output;
}
This solution works.
But, in checking, you dont need to compare all sums. Simply compare if highest segment is longer than sum of smaller ones. Remaining two conditions will hold.
Ex: if A1 > A2 > A3.
Then if A1 > A2 + A3, remaining two will be true automatically. (since A1 > A2 & A1 > A3).
So total complexity = O(nLogn) + O(n) ( Sorting + comparision )
#include<vector>
#include<iostream>
struct Triplet
{
const int first;
const int second;
const int third;
};
std::vector<Triplet> findTriangleTriplets( const std::vector<int>& vec_input )
{
std::vector<Triplet> triplets;
const unsigned int size = vec_input.size();
for( unsigned int i=0; i < size; ++i )
{
for( unsigned int j = i; j < size; ++j )
{
for( unsigned int k = j; k < size; ++k)
{
const int first ( vec_input.at( i ) );
const int second ( vec_input.at( j ) );
const int third ( vec_input.at( k ) );
if( [ &first, &second, &third ] {
return ( ( second + third ) > first )&&
( ( first + third ) > second )&&
( ( first + second ) > third );
}())
{
triplets.emplace_back( Triplet{ first, second, third } );
}
}
}
}
return triplets;
}
int main()
{
const std::vector<int> vec_input { 2, 4, 5, };
std::vector<Triplet> triplets = findTriangleTriplets( vec_input );
for ( auto &x : triplets )
{
std::cout<<x.first<<" "<<x.second<<" "<<x.third<<"\n";
}
return 0;
}
public static ArrayList<Vector> getTriangleSides(int[]segments)
{
int[]elements=segments;
ArrayList<Vector> triplet=new ArrayList<Vector>();
if(elements.length<3)
return triplet;
else
{
quickSort(0, elements.length-1, elements);
for(int i=0;i<elements.length-2;i++)
{
if(elements[i]+elements[i+1]>elements[i+2])
{
Vector vector=new Vector(3);
vector.add(elements[i]);
vector.add(elements[i+1]);
vector.add(elements[i+2]);
triplet.add(vector);
}
}
return triplet;
}
}
This solution would be O(n^2) and it covers all possible segments. If you need to return all segments, you can change logic accordingly.
public int[] getTriangleSides(int[] segments) {
int len = segments.length;
if (len < 3)
return null;
int[] sides = new int[3];
Arrays.sort(segments);
int i = 0;
while (i < len - 2) {
int j = i + 1;
for (int k = j + 1; k < len; k++) {
if (segments[i] + segments[j] > segments[k]) {
sides[0] = segments[i];
sides[1] = segments[j];
sides[2] = segments[k];
return sides;
} else {
j++;
}
}
i++;
}
return null;
}
public int[] getTriangleSides(int[] segments) {
int len = segments.length;
if (len < 3)
return null;
int[] sides = new int[3];
Arrays.sort(segments);
int i = 0;
while (i < len - 2) {
int j = i + 1;
for (int k = j + 1; k < len; k++) {
if (segments[i] + segments[j] > segments[k]) {
sides[0] = segments[i];
sides[1] = segments[j];
sides[2] = segments[k];
return sides;
} else {
j++;
}
}
i++;
}
return null;
}
Here is the C++ version of solution using quicksort.
Running time is O(n log n)
#include <vector>
#include <iostream>
using namespace std;
vector<int> getTriangleSides(int* inputs, int len)
{
vector<int> result;
quick_sort(inputs, 0, len-1);
for (int i = 0; i<len; i++)
{
if (i+2 <len)
{
if ((inputs[i]+inputs[i+1]) > inputs[i+2])
{
result.push_back(inputs[i]);
result.push_back(inputs[i+1]);
result.push_back(inputs[i+2]);
break;
}
}
}
return result;
}
If you sort the lengths in increasing order, say a1, a2, a3, ....., a_{n-1}, a_{n}, then wouldnt a simple check of whether a1 + a_{n-1} > a_{n} tell if atleast one triplet exists which forms a triangle.
if a1 + a_{n-1} < a_{n}, then no triplet exists.
Obviously, the bad way of doing this would be to try all triplet combinations and see if there is one triplet that works.
- Skor April 04, 2015A better way of doing it focuses on the fact that triangles are more likely to occur when the 3 lengths are close to each other. Example: 3,4,5 are closer numbers than 3,4,6, so they are more likely to be a triangle than 3,4,6.
With this in mind, we sort the list of segments- presumably in O(nlogn) with merge sort. Then in O(n) time, we traverse the sorted list. Set i = 0, j = 1, k = 2.
Check if array[i], array[j], array[k] are a triangle. If not, increment i, j, k then repeat the process.