Linkedin Interview Question
Software DevelopersTeam: Not known
Country: India
Interview Type: Phone Interview
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.
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
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.
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;
}
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;
}
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];
}
}
}
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);
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+"]");
}
}
}
}
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;
}
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);
}
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);
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.
- puneet.sohi December 08, 2015Say 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.