## Linkedin Interview Question for Software Developers

• 0

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.

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.
260.100 (1.2%) difference. Almost nothing.

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

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

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.

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

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.

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

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?

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

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

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

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

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

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

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+"]");
}
}

}
}``````

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

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

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

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

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.