Linkedin Interview Question for Software Developers


Team: Not known
Country: India
Interview Type: Phone Interview




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

I propose a slightly better way of doing this. In worst case it will be O(N^2 log n) but in reality it will be better.

Say our original array is A = {10, 5, 3, 7, 4, 1}

Since we have to find all sub-sequences of length 3 in A which satisfy the triangle property, let us first sort the array. Complexity of this step is O(n log n)

A = {1, 3, 4, 5, 7, 10}

Now we can start going through this array and picking triplets. However, since they are already sorted, when picking up the triplets, we can quickly check if the sum of two smaller ones is less than the bigger one

So, if our triplet is a, b & c; in iterating through the above array:
a = 1 b = 3 c = 4, a+b !>(not greater than) c, this triplet does not satisfy the triangle property.
Therefore we donot need to consider any more triplets for a = 1 and b = 3,
(because our next c element will be 5, which again won't satisfy the triangle property! i.e. all the remaining elements are greater than 4)

As you see, using this algo we can skip many of the triplets outright without making necessary comparisons.

- puneet.sohi December 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

it is almost the same.
I generated sorted array [0..511].
The brute force algorithm performs 22.238.720 iterations.
Your algorithm performs 21.978.620 iterations.
260.100 (1.2%) difference. Almost nothing.

- zr.roman December 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I don't know where you get your numbers from, but I tried his solution with the same size input you specify and the number of steps I counted is 11021695. If you want to include the the number of steps taken to sort the array, this amounts to 11021695 + 4608 which is no where close to the numbers you are implying.

This is the code

def triangle_triplets():
	l = range(512)
	steps = 0
	for k in xrange(len(l) - 2):
		stop = False
		for g in xrange(k + 1, len(l) - 1):
			v = g + 1
			while v < len(l) and l[k] + l[g] > l[v]:
				# yield (l[k], l[k + 1], l[v])
				steps += 1
				v += 1
	return steps

Just to make sure, I did the same thing with the brute-force method and lo and behold, I get 44347135 which is larger than what you proposed, making the first one 400% faster than this

def triangle_triplets():
	from random import shuffle
	l = range(512)
	shuffle(l)
	steps = 0
	for k in xrange(len(l) - 2):
		for g in xrange(k + 1, len(l) - 1):
			for j in xrange(k + 2, len(l)):
				steps += 1
				if l[k] + l[g] > l[j] and l[k] + l[j] > l[g] and l[g] + l[j] > l[k]:
					# yield (l[k], l[k + 1], l[v])
					pass
	return steps

- smac89 December 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The brute force algorithm performs 22.238.720 iterations.
I don't know how you got 44 mln.
So, we have 22 mln against 11 mln (let's assume that your algorithm is correct).
It is only 2 times faster, but it is still O(n^3) algorithm, because 1/2 is a constant.

- zr.roman December 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Python solution, yes? Also I'm not certain how you are using this code to get what you want. Any suggestion are appreciated and thanks in advance.

- BillyNewb December 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

c++, brute force, O(n^3)

vector< vector<int> > findTriangles(vector<int> nums) {
    vector< vector<int> > triangles;
    vector<int> triangle;
    int i, j, k;

    for (i = 0; i < nums.size() - 2; i++) {
        for (j = i + 1; j < nums.size() - 1; j++) {
            for (k = j + 1; k < nums.size(); k++) {
                if (nums[i] + nums[j] <= nums[k]) continue;
                if (nums[j] + nums[k] <= nums[i]) continue;
                if (nums[k] + nums[i] <= nums[j]) continue;
                triangle.clear();
                triangle.push_back(nums[i]);
                triangle.push_back(nums[j]);
                triangle.push_back(nums[k]);
                triangles.push_back(triangle);
            }
        }
    }

    return triangles;
}

- kyduke December 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

is it possible to generate triplets in order different than this in array?

- EPavlova December 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

в каком смысле?

- zr.roman December 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementation.
Number of iterations = n*(n+1)*(n+2)/6.
Time complexity: O(n^3).

static private List<int[]> GetAllCombinationsOfTriplets( int[] arr ) {

    List<int[]> res = new List<int[]>();

    for (int i = 0; i < arr.Length - 2; i++) {
        for (int j = i + 1; j < arr.Length - 1; j++) {
            for (int k = j + 1; k < arr.Length; k++) {

                int a = arr[ i ], b = arr[ j ], c = arr[ k ];

                if ( a + b > c && b + c > a && c + a > b ) {
                    res.Add( new [] { a, b, c } );
                }

            }
        }
    }
    return res;
}

- zr.roman December 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void chkTriTriplet(int iArr[n])
{
	cout << endl << "Triangle Triplets are"<< endl ;
	for(int i =0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			if((iArr[i]+iArr[j]) > iArr[j+1] &&(iArr[i]+iArr[j+1]) > iArr[j]
				&& (iArr[j+1]+iArr[j]) > iArr[i])
				cout << endl<< iArr[i]<<','<<iArr[j]<<','<<iArr[j+1];
		}
	}
}

- sv December 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findnumberofTriangles(arr):

    n = len(arr)
    arr.sort()

    for i in range(0,n-2):

        k = i + 2

        for j in range(i+1,n):

            while (k < n and arr[i] + arr[j] > arr[k]):
                if k > j:
                    print "(",arr[i],arr[j],arr[k],")"
                k += 1

- Anonymous December 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var permutate = (function() {
var results = [];
function doPermute(input, output, used, size, level) {
if (size == level) {
console.log(output);
if (doValidation(output)) {
console.log(output);
var word = output.join('-');
results.push(word);
}

return;
}
level++;
for (var i = 0; i < input.length; i++) {
if (used[i]) {
continue;
}
used[i] = true;
output.push(input[i]);
doPermute(input, output, used, size, level);
used[i] = false;
output.pop();
}
}

function doValidation(arrayToValidate) {
return ( (arrayToValidate[0]+arrayToValidate[1]>arrayToValidate[2]) && (arrayToValidate[1]+arrayToValidate[2]>arrayToValidate[0]) && (arrayToValidate[2]+arrayToValidate[0]>arrayToValidate[1]) ) ? true : false;
}

return {
getPermutations: function(values, size) {
var output = [];
var used = new Array(values.length);
doPermute(values, output, used, size, 0);
return results;
}
}
})();


permutate.getPermutations([10,5,3,4,7,1], 3);

- Carlos March 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findTripletsFormingTriangle(int[] inputArray) throws Exception{
		
		if(inputArray.length < 3){
			throw new Exception("Invalid argument exception");
		}
		
		for(int i=0;i<inputArray.length-3;i++){
			for(int j=1;j<inputArray.length-2;j++){
				int a = inputArray[i];
				int b = inputArray[j];
				int c = inputArray[j+1];
				
				if(a+b>c && b+c>a && c+a>b){
					System.out.println("Triplet ["+a+","+b+","+c+"]");
				}
			}
			
		}
	}

- skusuj May 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

An O(n^2 log n) solution:

List<Element> getTriplets(int[] A) {
	Arrays.sort(A);
	int N = A.length;
	for (int i = 0; i < N; ++i) {
		for (int j = i+1; j < N; ++j) {
			int num1 = A[i];
			int num2 = A[j];
			int sum = num1+num2;
			// Returns the first index greater or equal to the sum
			int index = binarySearch(A, sum, j+1, N-1);
			if (index-1 > j) {
				int num3 = A[index-1];
				if (num1+num2 > num3 && num1+num3 > num2 && num2+num3 > num1) {
					Element element = new Element(num1, num2, num3);
					result.add(element);
				}
			}
		}
	}
}

int binarySearch(int[] A, int target, int start, int end) {
	while (start <= end) {
		int mid = start + (end-start)/2;
		if (A[mid] > target) {
			end = mid;
		}
		else if (A[mid] < target) {
			start = mid+1;
		}
		else if (A[mid] == target) {
			end = mid;
		}
	}
	return start;
}

- Srikant Aggarwal May 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public countTriangles(){
int arr[] = {10, 21, 22, 100, 101, 200, 300};
        
        //Sort the arr
        Arrays.sort(arr);
        int count=0; //Number of triangles initialization
        
        for(int i=0;i<arr.length-2;i++){
            int k=i+2; //Initialize the k with i+2.
            for(int j=i+1;j<arr.length;j++){
                while(k<arr.length && (arr[i]+arr[j])>arr[k]) k++; //Find the k such that arr[i]+arr[j] is greater than arr[k]
                count+=k-j-1;
            }
        }        
        System.out.println(count);
}

- Kunal June 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void countTriangles(){
int arr[] = {10, 21, 22, 100, 101, 200, 300};
        
        //Sort the arr
        Arrays.sort(arr);
        int count=0; //Number of triangles initialization
        
        for(int i=0;i<arr.length-2;i++){
            int k=i+2; //Initialize the k with i+2.
            for(int j=i+1;j<arr.length;j++){
                while(k<arr.length && (arr[i]+arr[j])>arr[k]) k++; //Find the k such that arr[i]+arr[j] is greater than arr[k]
                count+=k-j-1;
            }
        }        
        System.out.println(count);

- Anonymous June 12, 2017 | Flag Reply


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