## Linkedin Interview Question for SDE1s

• 1
of 1 vote

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

}

}``````

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

This is brute force right?

Comment hidden because of low score. Click to expand.
-2

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.

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

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

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.

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

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

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

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

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

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

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

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

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>();
}
}else{
for (int i = index ; i < triplets.length ;++i ) {
if (count < 3) {
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);``````

}

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

this is basically n^3

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

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

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

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

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.

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.

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.

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

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

}

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

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

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

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

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)

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?

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

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.

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

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

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

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

}

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))
for (int i = start; i < nums.length; i++)
{
if (i != start && nums[i] == nums[i - 1])
continue;
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));
}

}``````

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

}``````

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

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

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

}``````

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

}

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

}``````

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

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

return triples;
}

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

while(i-- > 0)
{
}
}

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

while(i-- > 0)
{
}
}
}``````

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)

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

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

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

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.

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?

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

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.

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?

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

You are correct. My approach is wrong.

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

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

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

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

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

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

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

Where are you sorting or checking for triangle inequality?

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

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

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

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

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

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

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

Can you be more specific?

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

How ? could you elaborate ?

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

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.

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.