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.

- Skor April 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SK April 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- steep April 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Skor April 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

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.

- sakshisharma April 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good point.

- Skor April 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- steep April 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- SK April 04, 2015 | Flag
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.

- amaykataria April 05, 2015 | Flag
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].

- ninhnnsoc April 05, 2015 | Flag
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.

- Skor April 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

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

- nikolay.dimitrov April 06, 2015 | Flag
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.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;
	}

- saumya.wipro April 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 )

- X June 08, 2015 | Flag
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

- blah blah May 29, 2015 | Flag Reply
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;

}

- steep April 06, 2015 | Flag Reply
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);
                    vector.add(elements[i]);
                    vector.add(elements[i+1]);
                    vector.add(elements[i+2]);
                    triplet.add(vector);
                }
            }
            return triplet;
        }
    }

- Jydas April 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about below algorithm?

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

- Joseph Wang May 02, 2015 | Flag Reply
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;
}

- hpkancha May 10, 2015 | Flag Reply
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;
}

- hpkancha May 10, 2015 | Flag Reply
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;
}

- hankm2004 August 06, 2015 | Flag Reply
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.

- Ravi August 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vf November 01, 2015 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More