Linkedin Interview Question for SDE1s


Country: United States
Interview Type: Phone Interview




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

/*
 Given a array of positive integers, find all possible triangle triplets that can be formed from this array. 
eg: 9 8 10 7 
ans: 9 8 10, 9 8 7, 9 10 7, 7 8 10 
Note : array not sorted
 */
public class TriangleTriplet {

	
	public void triangleTriplet(int a[])
	{
		int n=a.length;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				for(int k=0;j<n;j++)
				{
					if(i!=j && j!=k && i!=k)
					if(a[i]+a[j]>a[k]  && a[j]+a[k]>a[i] && a[i]+a[k]>a[j])
					{
						System.out.println(a[i]+" "+a[j]+" "+a[k]);
					}
				}
			}
		}
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int a[]={9,8,7,10};
		
		new TriangleTriplet().triangleTriplet(a);

	}

}

- atul.it.jss November 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is brute force right?

- Aspire November 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

I don't see any other way then to generate all possible combinations and checking each one.

You could use three lines of any positive length to form a triangle if you're allowed to have sides sticking out beyond the intersections.

- ys April 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

private static void printarri(int str[]) {
        for (int i = 0; i < str.length; i++)
            System.out.print("" + str[i] + " ");
        System.out.println("");
    }

    private static String arrKey(int str[]) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length; i++)
            sb.append(str[i]);
        return sb.toString();
    }
    
//Unique triplets
    private static HashMap memo = new HashMap();
    private static int NO_VALUE = -1;
    public static void findTriplet(int a[], int idx, int k, int r[]) {
        if (memo.containsKey(arrKey(r))) return;

        if (r[2] >= 0) {
            memo.put(arrKey(r), r);
            printarri(r);
            return;
        }

        if (idx > a.length - 1) return;

        if (r[k] == NO_VALUE) {
            r[k] = a[idx];
            findTriplet(a, idx + 1, k + 1, r);
            r[k] = NO_VALUE;
            findTriplet(a, idx + 1, k, r);
        }
    }

- Kamaldeep Singh December 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For Triangle property, the conditions should be changed to

...
        Boolean b = (r[0] + r[1] > r[2] && r[1] + r[2] > r[0] && r[0] + r[2] > r[1]);
        if (b && r[2] != NO_VALUE) {
            memo.put(arrKey(r), r);
            printarri(r);
            return;
        }

        if (k > 2 || idx > a.length - 1) return;
...

Call it like this

public static void main(String[] args) {
//        int a[] = {2,1,3,4,6,3,8,9,10,12,56};
        int a[] = {9, 8, 10, 7};
        int r[] = {NO_VALUE, NO_VALUE, NO_VALUE};
        findTriplet(a, 0, 0, r);
}

This is what I could think of, quick decent code.

- kamalmht2000 December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done using a simple tree traversal

public static ArrayList<int[]> getAllTriangles(int[] arr){
	Worker worker = new Worker(arr);
	worker.execute();
	return worker.result;
}

static class Worker{
	ArrayList<int[]> result = new ArrayList<int[]>();
	int[] arr;
	Worker(int[] arr){
		this.arr = arr;
	}

	void execute(){
		recurse(0);
	}

	void recurse(int depth){
		if(depth == 3){
			int[] tri = Arrays.copyOfRange(arr, arr.length-depth, arr.length);
			result.add(tri);
			return;
		}
		//for each unused position in the array
		int lastIndex = arr.length - 1 - depth;
		int newDepth = depth + 1;
		for(int i = 0; i < arr.length-depth; i++){
			//select the position
			int temp = arr[lastIndex];
			arr[lastIndex] = arr[i];
			arr[i] = temp;
			//recurse for all other possibilities
			recurse(newDepth);
			//unselect the position in the array
			arr[i] = arr[lastIndex];
			arr[lastIndex] = temp;
		}
	}
}

- zortlord November 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please give some explanation for the above code. Its difficult to understand.

- Aspire November 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually, you should ignore this code. Without a clear definition for what a triangle triplet is, I assumed that it was only a subset with 3 elements. The above implementation is simple a really fast back-tracking algorithm that will operate in roughly O(n^3).

- zortlord November 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If it is really fast, how come it runs in o(n^3)?

- Vikram January 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

10 , 9.5 , 9 , 8 , 5 , 2,0.5

int getAllTriangles(int input[])
{
if(input.length<3)
return 0;
int count=0;
sort(input); //assume merge sort
for(int i=0;i<input.length-2;i++)
{
for(j=i+1;j<input.length-1;j++)
{
int index=BinarySearch(input,j,input.length-1); //returns the index of that number
if(index!=-1)
count=count+index-j;
}
}

}

int BinarySearch(int input[],int low,int high)
{
if(low>high)
return -1;
int k=input[low]-input[high];
int mid=(low+high)/2;
if(k<input[mid] && k>=input[mid+1] && mid+1<=high)
return mid;
else if(k<input[mid-1] && k>=input[mid] && mid-1>=low)
return mid-1;
else if(k<input[mid])
return BinarySearch(input,mid+1,high);
else
return BinarySearch(input,low,mid-1);
}

- Aspire November 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

public List<List<Integer>> findAll (int [] triplets ){
		Arrays.sort(triplets);
		List<Integer> list = new ArrayList<Integer> ();
		List<List<Integer>> result = new ArrayList<List<Integer>> ();
		find (triplets,0,0,list,result);
		return result;
	}
	
	private void find (int [] triplets ,int index , int count, List<Integer> list,List<List<Integer>> result){
		if (count == 3) {
			if (isValid (list)) {
				ArrayList<Integer> tmp = new ArrayList<Integer>();
				tmp.addAll(list);
				result.add(tmp);
			}
		}else{
			for (int i = index ; i < triplets.length ;++i ) {
				if (count < 3) {
					list.add(triplets[i]) ;
					find (triplets, i+1 ,count + 1, list,result);
					list.remove(list.size() -1);
				}
			}
		}
	}
	
	private boolean isValid (List<Integer> list){
		return list.get(0) + list.get(1) > list.get(2) &&
				list.get(1) - list.get(0)  < list.get(2);

}

- Anonymous November 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is basically n^3

- chengdujin January 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Sort the array
2. Start with the the highest 3 numbers
3. Picker lower numbers sequentially for the three side until you find a combination that fails the trianglet test

Below is a C++ implementation:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void printTrianglets(vector<int> A) {
    sort(A.begin(), A.end());
	for(auto c = A.size() - 1; c != -1; c--) {
		bool found_b = false;
		for(auto b = c - 1; b != -1; b--) {
			bool found_a = false;
			for(auto a = b - 1; a != -1; a--) {
				if(A[c] >= (A[a] + A[b]))  break;
				found_a = true;
				cout << A[a] << " " << A[b] << " " << A[c] << endl;
			}
			if(!found_a) break;
			found_b = true;
		}
		if(!found_b) break;
	}
}


int main() {
    vector<int> A = {1,2,3,4,5,6};
    printTrianglets(A);
	return 0;
}
Output:
4 5 6
3 5 6
2 5 6
3 4 6
3 4 5
2 4 5
2 3 4

- Mhret November 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I guess this is indeed an optimal way -- O(nlogn) complexity

- Jyoti June 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is O(N^3) algorithm. I don't know how this is O(nlongn) algorithm.
There are three for loops, searching N, N-1, N-2 respectively. Asymptotically, it is O( N^3) algorithm.

- hankm2004 August 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is n^2, not nlogn. Still think it's optimal though.

- emily August 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is n^2, not nlogn. Still think it's optimal though.

- emily August 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Correction to the previous solution. The c loop can't quit early.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void printTrianglets(vector<int> A) {
    sort(A.begin(), A.end());
    for(auto c = A.size() - 1; c != -1; c--) {
    	for(auto b = c - 1; b != -1; b--) {
    		bool found_a = false;
			for(auto a = b - 1; a != -1; a--) {
    			if(A[c] >= (A[a] + A[b]))  break;
				found_a = true;
				cout << A[a] << " " << A[b] << " " << A[c] << endl;
			}
			if(!found_a) break;
		}
	}
}


int main() {
    vector<int> A = {2,2,3,6,9,14};
    printTrianglets(A);
	return 0;
}
Output:
6 9 14
2 2 3

- Mhret November 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void triangletriplets(int tripletArr[4])
{
	for(int i=0;i<4;i++)
	{
		for(int j=i+1;j<4;j++)
		{
			for(int k=j+1;k<4;k++)
			{
				cout << "triangle triplets are" << tripletArr[i] << tripletArr[j] << tripletArr[k] << endl;
			}
		}
	}

}

- sv November 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the question section ,answer is listed out as all possible combination of the three sides that could be formed from the 4 element array..

- Anonymous November 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in O(n^2) time

Sort the array 
for  i = 1 to N 
 for j = i+1 to N
	while (A[k]<A[i] + A[j])  
		insert (i,j,k) to result set.
		k++;

Note that the last iteration runs only once for all i, j pairs..

- Gaurav November 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is k initialized as? And don't you need to make sure a[k] is not the same as a[i] or a[j]?

- purpleshoes November 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is n^3. However, if instead of k doing O(n) comparisons, you can do binary search since the rest of the array is sorted. This becomes O(n^2 logn)

- shic September 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What is a triangle triple? Is it that they should form a right angle triangle?

- puneet.sohi November 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, they should hold the triangle inequality i.e., if there are 3 sides a,b,and c. then a+b > c for any triangles.

- Anon November 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the sum of any 2 sides of a triangle must be greater than the measure of the third side..this is the inequality theorem that should be satisfied for a triangle

- Anonymous November 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

public class TriangleTriplets {

        //note: you don't need to check the other two cases since the array is sorted. 
	public static boolean check(int a, int b, int c) {
		return (a+b>c);
	}
	
	public static void triangleTriples(int[] a) {
		for (int i = 0; i<a.length; i++) {
			for (int j = i+1; j<a.length; j++) {
				for (int k = j+1; k<a.length; k++) {
					if (check(a[i],a[j],a[k])) 
						System.out.println(a[i] + " " + a[j] + " " + a[k]);
				}
			}
		}		
	}

	public static void main(String[] args) {
		int[] a = {7,8,9,10};
		Arrays.sort(a);
		triangleTriples(a);
	}
}

- purpleshoes November 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The Simplest Approach...

public class Solution {
	public static void main(String[] args) {
		int a[]={9,8,7,10};
		int i,j,n,k;
		n=a.length;
		for(i=0;i<n-1;i++){
			for(j=i+1;j<n;j++){
				for(k=j+1;k<n;k++){
					if(a[i]+a[k]>a[j] && a[j]+a[k]>a[i] && a[i]+a[j]>a[k] && a[i]>0 && a[j]>0 && a[k]>0){
						System.out.println(a[i]+" "+a[j]+" "+a[k]);
					}
				}
			}
		}
	}

}

- rockker.fu December 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is it possible to do back tracking?

public class PossibleTriangle {
	public ArrayList<ArrayList<Integer>> possibleTriangle(int[] nums)
	{
		ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
		if (nums == null || nums.length == 0)
			return rst;
		ArrayList<Integer> triplets = new ArrayList<Integer>();
		Arrays.sort(nums);
		getTriangle(rst, triplets, nums, 0);
		return rst;
	}
	private void getTriangle(ArrayList<ArrayList<Integer>> rst, ArrayList<Integer> triplets, 
			int[] nums, int start)
	{
		if (triplets.size() == 3 && triplets.get(0) + triplets.get(1) > triplets.get(2))
			rst.add(new ArrayList<Integer> (triplets));
		for (int i = start; i < nums.length; i++)
		{
			if (i != start && nums[i] == nums[i - 1])
				continue;
			triplets.add(nums[i]);
			getTriangle(rst, triplets, nums, i + 1);
			triplets.remove(triplets.size() - 1);
		}
	}
	public void printList(ArrayList<ArrayList<Integer>> rst)
	{
		for (int i = 0; i < rst.size(); i++)
			System.out.println(rst.get(i));
	}

}

- DoraShine December 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This one is for sorted list

public static void findTrPairs(int[] arr,int origin,int elIndex,int runnerInd){
		if(elIndex>=arr.length-1||origin>=arr.length) return;
		if(elIndex<=arr.length && runnerInd<=arr.length && origin<=arr.length && elIndex!=runnerInd){
			if(arr[origin]+arr[elIndex]>arr[runnerInd]){
				System.out.println("{"+arr[origin]+","+arr[elIndex]+","+arr[runnerInd]+"}");
			}
			if(elIndex+1==runnerInd) runnerInd++;
			if(runnerInd<=arr.length-1){
				findTrPairs(arr,origin,++elIndex,runnerInd);
			}
			else{
				elIndex = origin+2;
				runnerInd = origin+3;
				findTrPairs(arr,++origin,elIndex,runnerInd);
			}

		}
		else if(origin<arr.length && elIndex<arr.length-1){
			elIndex = origin+2;
			runnerInd = origin+3;
			findTrPairs(arr,++origin,elIndex,runnerInd);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] arr = {3,4,6,7};
		findTrPairs(arr, 0, 1, 2);
		System.out.println("second array");
		int[] arr1 = {10, 21, 22, 100, 101, 200, 300};
		findTrPairs(arr1, 0, 1, 2);
		
		System.out.println("third array");
		int[] arr2 = {9, 8 ,10, 7};
		findTrPairs(arr2, 0, 1, 2);
		
	}

- Resh January 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

try this one: {0.5, 2, 5, 8, 9, 9.5, 10}, it's supposed to print

2 8 9
2 8 9.5
2 9 9.5
2 9 10
2 9.5 10
5 8 9
5 8 9.5
5 8 10
5 9 9.5
5 9 10
5 9.5 10
8 9 9.5
8 9 10
8 9.5 10
9 9.5 10

- chengdujin January 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void printTriangleTriplets(float[] A){

		mergeSort(A);

		for(int i = 0; i < A.length - 2; i++){
			
			for(int j = i+1; j < A.length - 1; j++){
				
				//Search for first greater/equal element to the sum of the first two
				int third = binarySearchGreaterElement(A, j + 1, A.length - 1, A[i] + A[j]);
				
				//No element greater/equal to the sum
				if(third == -1){
					//Print until end
					for(int k = j + 1; k < A.length; k++){
						System.out.println(A[i] + " " + A[j] + " " + A[k]);
					} 					
				}
				//Index of the element that is greater or equal
				else {
					//Print until index
					for(int k = j + 1; k < third; k++){
						System.out.println(A[i] + " " + A[j] + " " + A[k]);
					}
				}
			}
		}


	}


	public int binarySearchGreaterElement(float[] A, int low, int high, float sum){

		//No element greater or equal is present
		if(low > high) return -1;
		
		//get middle element
		int mid = low + (high - low) / 2;
		
		//If mid element is greater or equal
		if(A[mid] >= sum){
			
			/*No need to check for out of bound because the first low passed
			 * is 2
			 */
			//If mid - 1 element is lesser
			if(A[mid - 1] < sum){
				return mid;
			}
		}
		
		if(A[mid] >= sum){
			return binarySearchGreaterElement(A, low, mid - 1, sum);
		} else {
			return binarySearchGreaterElement(A, mid + 1, high, sum);
		}
		
	}

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

Similar to Victor solution

void PrintAllTriangles(int A[], int N)
{

	//A[k] < A[i] + A[j]

	//Naturally solution is O(N^3) but we can do little optimization by presorting at O(NlogN)
	sort(A, A+N);
	
	for (int i=0; i<N-2; i++)
	{
		//A[i] < A[j] + A[k] always true for sorted array and j,k>i
		for (int j=i+1; j<N-1; j++)
		{
			//A[j] < A[i] + A[k] always true for sorted array and k>j
			int k=j+1;
			while (A[k] < A[i] + A[j] && k<N)
			{
				cout << A[i] << "," << A[j] << "," << A[k] << endl;
				k++;
			}
		}
	}

}

- pavel.kogan January 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

public class TriangleTriplets {

    public static int countTriangleTriplets(int[] array) {
        int count = 0;

        Arrays.sort(array);

        for (int i = 0; i < array.length - 2; i++) {
            int k = i + 2;
            for (int j = i + 1; j < array.length - 1; j++) {
                int maxAllowed = array[i] + array[j];
                while (k < array.length && array[k] < maxAllowed) {
                    k++;
                }
                count += k - j - 1;
                // DEBUG
                //for (int l = j + 1; l < k; l++) {
                //    System.out.println("" + array[i] + ", " + array[j] + ", " + array[l]);
                //}
            }
        }

        return count;
    }

    public static void main(String[] args) {
        System.out.println("Total trangle triplets : " + countTriangleTriplets(new int[0]));

        System.out.println("Total trangle triplets : " + countTriangleTriplets(new int[] { 1, 1, 10000 }));

        System.out.println("Total trangle triplets : "
                + countTriangleTriplets(new int[] { 10, 21, 22, 100, 101, 200, 300 }));

        System.out.println("Total trangle triplets : " + countTriangleTriplets(new int[] { 9, 8, 10, 7 }));
    }

}

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

def triInequal(list):
    l = len(list)
    for i in range(0,len(list)):
        for j in range(0,len(list)):
            for k in range(0,len(list)):
                if (list[i]!= list[j] and list[j]!= list[k] and list[k]!=list[i]):
                    if (list[i]+list[j]>list[k] and list[i]+list[j]>list[k] and list[i]+list[j]>list[k]):
                        print(list[i],list[j],list[k],sep=' ')

def main():
    testlist = [4,5,6,7,8]
    triInequal(testlist)

if __name__=='__main__':
    main()

A Python3 implementation

- PyMan March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming memory isn't a problem, build up triples from previous ordered pairs. From OP's question, it looks as if order does not matter, hence, adding an integer that has already been "encountered" should require no additional work.

class TripleBuilder
	{
		HashSet<int> complete;
		List<int> values;
		List<Tuple<int, int>> pairs;
		List<Tuple<int,int,int>> triples;

		public TripleBuilder()
		{
			complete = new HashSet<int>();
			values = new List<int>();
			pairs = new List<Tuple<int,int>>();
			triples = new List<Tuple<int,int,int>>();
		}

		public List<Tuple<int,int,int>> Build(int[] arr)
		{
			int i = arr.length;
			int tmp;

			while(i-- > 0)
			{
				if(complete.Contains(arr[i]))
					continue;

				tmp = arr[i];
				CreateTriples(tmp);
				CreatePairs(tmp);
				values.Add(tmp);
				complete.Add(tmp);
			}

			return triples;
		}

		private void CreateTriples(int a)
		{
			int i = pairs.length;

			while(i-- > 0)
			{
				triples.Add(Tuple.Create(pairs[i].Item1, pairs[i].Item2, a));
			}
		}

		private void CreatePairs(int a)
		{
			int i = values.Count;

			while(i-- > 0)
			{
				pairs.Add(Tuple.Create(values[i], a))
			}
		}
	}

- jayflo March 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def maketriangle(a):
a.sort()
N = len(a)
output = []
for i in range(N-1,-1,-1):
print i
for j in range(i-1,-1,-1):
print i,j
if 2*a[j]<=a[i]:
break
for k in range(j-1,-1,-1):
print i,j,k
if a[j]+a[k]>a[i]:
output.append([a[i],a[j],a[k]])
else:
break
return output

a = [1,.5,6,7,]
print maketriangle(a)

- nem July 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the C++ version of solution.

Running time is O(N^3).

#include<vector>
#include<cstdlib>
#include<iostream>
using namespace std;

void dfs(int* input, int* marked, vector<int>& nums, int prev, int len)
{
  if (nums.size() == 3)
  {
    cout << nums[0] << ", " << nums[1] <<", " << nums[2]<<endl;
    return;
  }

  for (int i = prev+1; i < len; i++)
  {
    if (marked[i] != 1)
    {
      if (nums.size() == 2 && (nums[0]+nums[1]) <= input[i])
          continue;
      marked[i] = 1;
      nums.push_back(input[i]);
      dfs(input, marked, nums, i, len);
      marked[i] = 0;
      nums.pop_back();
    }
  }
}

int compare(const void *a, const void *b)
{
  return (*(int*)a - *(int*)b);
}

void find_triangles(int* input, int len)
{
  vector<int>nums;
  qsort(input, len, sizeof(int), compare);
  int *marked = new int[len];
  for (int i = 0; i <len; i++)
  {
    nums.push_back(input[i]);
    marked[i] = 1;
    dfs(input, marked, nums, i, len);
    marked[i] = 0;
    nums.pop_back();
  }
}

- hankm2004 August 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/local/bin/python

def ttrip(nums):
    if len(nums) < 3:
        return None
    if len(nums) == 3:
        #print nums
        if nums[0] >= nums[1] + nums[2]: return 
        if nums[1] >= nums[0] + nums[2]: return 
        if nums[2] >= nums[1] + nums[0]: return 
        result.append(nums)
        return nums 
    for i in nums:
        subl = nums[:]
        subl.remove(i)
        #print subl
        ttrip(subl)
            
result = []       
ttrip([0.5, 2, 5, 8, 9, 9.5, 10])
uniq = [list(x) for x in set(tuple(x) for x in result)]
print uniq

- sofaduck September 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/local/bin/python

def ttrip(nums):
    if len(nums) < 3:
        return None
    if len(nums) == 3:
        #print nums
        if nums[0] >= nums[1] + nums[2]: return 
        if nums[1] >= nums[0] + nums[2]: return 
        if nums[2] >= nums[1] + nums[0]: return 
        result.append(nums)
        return nums 
    for i in nums:
        subl = nums[:]
        subl.remove(i)
        #print subl
        ttrip(subl)
            
result = []       
ttrip([0.5, 2, 5, 8, 9, 9.5, 10])
uniq = [list(x) for x in set(tuple(x) for x in result)]
print uniq, len(uniq)

- sofaduck September 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

i, j, k are indexes. j is always i+1, k starts at i+2 and can increase.

Sort the input array in O(nlogn).

Given that A[i], A[j], A[k] start as A[i], A[i+1], A[i+2]:

First condition: A[i] < A[j] + A[k]. Always true since the array is sorted.

Second condition: A[j] < A[i] + A[k]. Again, always true since A[k] is alone greater than A[j.

Third condition: A[k] < A[i] + A[j]. This is where we need to iterate. We need to increment k until A[k] becomes greater or equal than A[i]+A[j]. This is where we stop the iteration and move on to the next step.

#include <vector>
#include <algorithm>
#include <iostream>

int trianglets(std::vector<int> input)
{
	std::sort(input.begin(), input.end());
	
	int num_trianglets = 0;
	
	int i, j, k;
	int N = input.size();
	
	for (i = 0; i <= N-3; ++i) {
		j = i+1;
		
		num_trianglets += i;
		
		for (k = j+1; k <= N-1; ++k) {
			if (input[k] < input[i] + input[j]) {
				++num_trianglets;
			}
			else {
				break;
			}
		}
	}
	
	return num_trianglets;
}

Complexity: O(n^2) after sorting the array in O(nlogn).

We could maybe transform the inner loop into a binary search. Would it make it logn instead of n in practice? I'm not sure.

- Victor November 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Your algorithm seems partly right. Could you please elaborate in the form of a pseudocode. I believe i,j,k all three can be iterated over the array. So TC is O(n^3) right? My approach was on similar lines but i was doing a binary search to find the 3rd element. The TC I got then was n^2logn. Anyone with a better and simpler approach?

- Aspire November 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My reasoning is that you only need to iterate j and k, because all values of i from j-1 to 0 are valid for trianglets, because of the first condition I stated.

- Victor November 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

but you only check triplets of the form <i,i+1,k> - what about this triplet: <arr[2],arr[7],arr[15]>? When will you check it?

- Patrick November 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are correct. My approach is wrong.

- Victor November 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you think i,i+1 .... need to be always selected as a pair.... why not i, i+k, i+j .... can be selected as a triplet . why this strong dependency.....!!!!!

- Ssl November 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<stdio.h>
main()
{
int a[4] = {9,8,10,7};
int i,j,k;
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
for(k =0;k<4;k++)
{
if(i != j && j != k && k != i)
{
printf("%d%d%d\n",a[i],a[j],a[k]);
}
}
}
}
}

- kshitiz gupta November 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

main()
{
int a[4] = {9,8,10,7};
int i,j,k;
for(i=0;i<2;i++)
{
for(j=1;j<3;j++)
{
for(k =2;k<4;k++)
{
if(i != j && j != k && k != i)
{
printf("%d%d%d\n",a[i],a[j],a[k]);
}
}
}
}
}

- kshitiz gupta November 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

main()
{
int a[4] = {9,8,10,7};
int i,j,k;
for(i=0;i<2;i++)
{
for(j=1;j<3;j++)
{
for(k =2;k<4;k++)
{
if(i != j && j != k && k != i)
{
printf("%d%d%d\n",a[i],a[j],a[k]);
}
}
}
}
}

- kshitiz gupta November 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

void triangletriplets(int tripletArr[4])
{
	for(int i=0;i<4;i++)
	{
		for(int j=i+1;j<4;j++)
		{
			for(int k=j+1;k<4;k++)
			{
				cout << "triangle triplets are" << tripletArr[i] << tripletArr[j] << tripletArr[k] << endl;
			}
		}
	}
}

- Anonymous November 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Where are you sorting or checking for triangle inequality?

- Aspire November 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the question section ,answer is listed out as all possible combination of the three sides that could be formed from the 4 element array..

- Anonymous November 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have added the condition for inequality check..in the below code

void triangletriplets(int tArr[4])
{
	for(int i=0;i<4;i++)
	{
		for(int j=i+1;j<4;j++)
		{
			for(int k=j+1;k<4;k++)
			{
				if((tArr[i]<(tArr[j]+tArr[k])) &&
					(tArr[j]<(tArr[i]+tArr[k])) && 
					(tArr[k]<(tArr[i]+tArr[j])))
				cout << "triangle triplets are" << tArr[i] << tArr[j] << tArr[k] << endl;
			}
		}
	}
}

- Anonymous November 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

This can be done in O(n) time without sorting.

- Pooja November 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you be more specific?

- purpleshoes November 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How ? could you elaborate ?

- John December 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess you are just messing up. The reason why O(n) can't exist, is because there can be more than "n" such triplets. Take this example, say there is an array of all "2"s, the there will be NC3 combinations which will be O(n^3) and you will have to iterate atleast once to list everything out.

- Anonymous January 27, 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