## Linkedin Interview Question for Software Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
5
of 5 vote

Obviously, the bad way of doing this would be to try all triplet combinations and see if there is one triplet that works.

A 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.

Comment hidden because of low score. Click to expand.
0

Total run time = O(nlogn + n) => O(nlogn)

Comment hidden because of low score. Click to expand.
0

Can you please post a code snippet for this, I am iffy on this argument.

Comment hidden because of low score. Click to expand.
0

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);
}``````

Comment hidden because of low score. Click to expand.
3

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.

Comment hidden because of low score. Click to expand.
0

Good point.

Comment hidden because of low score. Click to expand.
0

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!!!

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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].

Comment hidden because of low score. Click to expand.
1
of 1 vote

The question is not asking to return all possible triplets. It is asking to return at most one.

Comment hidden because of low score. Click to expand.
3

Obviously you don't need 3 indexes, as it's same as k-2, k-1 and k.
Good solution!

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````public int[] getTriangleSides(int[] segments)
{
int []output={};
List<Integer> out = new ArrayList<Integer>();

for(int i=0;i<segments.length;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;
}``````

Comment hidden because of low score. Click to expand.
0

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 )

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````def get_triangle_sides(segments):
segments.sort()
n = len(segments)
for i in xrange(n - 1, 1, -1):
if (segments[i] - segments[i - 1]) < segments[i - 2]:
return (segments[i - 2], segments[i - 1], segments[i])
return None``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}
return triplet;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Sort the list. O(n lg n)
2) Do "modified" binary search.
a) set a=the smallest number
b) set c=the biggest number
c) search b between a and c s.t. a+b >= c using binary search
d) advance a pointer or decrement c

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

This simply is not true.
Consider {1,2,3,4,5,100}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.