Linkedin Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
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);
}
}
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.
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;
}
}
}
Could you please give some explanation for the above code. Its difficult to understand.
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).
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);
}
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);
}
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
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.
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
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..
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]?
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.
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);
}
}
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]);
}
}
}
}
}
}
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));
}
}
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);
}
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);
}
}
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++;
}
}
}
}
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 }));
}
}
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
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))
}
}
}
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)
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();
}
}
#!/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
#!/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)
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.
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?
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.
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?
#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]);
}
}
}
}
}
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;
}
}
}
}
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..
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;
}
}
}
}
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.
- atul.it.jss November 25, 2014