Facebook Interview Question


Country: United States
Interview Type: Phone Interview




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

The brute force solution is O(n3) time and O(1) space.

This solution is O(n2) and O(n) space. The space is required for the hash table.

*Solution using Hash table*
Step 1: Find all the pairs of numbers and group them by the sum of the two numbers.
Step 2: For each group, store them as a hash table with key = sum and value = list of pairs
Step 3: Go over the original array once again and see if there are any pairs with sum = current number.
Step 4: To avoid duplication, make sure that the current number appears before the other two items (the pair)

public class TripletsWithSumZero {
    public static void main(String[] args) {
        int[] given = new int[] { 0, -1, 2, -3, 1};
        Map<Integer, List<Pair>> map = buildMap(given);
        findTriplets(given, map);
    }

    private static Map<Integer, List<Pair>> buildMap(int[] given) {
        Map<Integer, List<Pair>> map = new HashMap<>();
        for(int i=0; i < given.length; i++) {
            for(int j=i+1; j < given.length; j++) {
                Pair pair = new Pair(i, j);
                int sum = given[i] + given[j];
                List<Pair> pairs = map.get(sum);
                if (pairs == null) {
                    pairs = new ArrayList<>();
                    map.put(sum, pairs);
                }
                pairs.add(pair);
            }
        }
        return map;
    }

    private static void findTriplets(int[] given, Map<Integer, List<Pair>> map) {
        for (int i=0; i < given.length; i++) {
            List<Pair> matchingPairs = map.get(-given[i]);
            if (matchingPairs != null)
                for (Pair pair : matchingPairs)
                    if (i < pair.a)
                        System.out.printf("Found a match (%d, %d, %d)\n", given[i], given[pair.a], given[pair.b]);
        }
    }

    private static class Pair {
        int a, b;
        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
}

- kredible July 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My earlier solution is unnecessarily complicated. Although it is a O(n2) solution, it involves an extra O(n) iteration.

Here is a far more simple solution that is still O(n2) time and O(n) space.

1. Maintain a hash set that contains all the unique values in the given list, but start with an empty set
2. Go over each *pair* of numbers in the given list
3. For each pair, check if the sum of the two numbers has a corresponding value in the set such that (value in the set + sum of the pair = 0)
4. If found, then print out the triplet
5. If not found, the add the first item to the set

public class TripletsWithSumZero {
    public static void main(String[] args) {
        int[] given = new int[] { 0, -1, 2, -3, 1};
        findTriplets(given);
    }

    private static void findTriplets(int[] given) {
        Set<Integer> set = new HashSet<>();
        for(int i=0; i < given.length; i++) {
            for(int j=i+1; j < given.length; j++) {
                if (set.contains(-(given[i]+given[j])))
                    System.out.printf("Found a match (%d, %d, %d)\n", given[i], given[j], -(given[i]+given[j]));
                else
                    set.add(given[i]);
            }
        }
    }
}

2.

- kredible July 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

THE SOLUTION IS WRONG. oNCE CHECK YR Answer for -1,0,1,2,3

- Anonymous July 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public List<Integer> findTriplet(int[] tempChar){
		 List<Integer> tempList = new ArrayList<>();
		  for(int i=0;i<tempChar.length-2;i++){
			  for(int j=1;j<tempChar.length-1;j++){
				  for(int k=2;k<tempChar.length;k++){
					  if(tempChar[i]+tempChar[j]+tempChar[k] == 0 || tempChar.length ==0){
						 tempList.add(tempChar[i]);
						 tempList.add(tempChar[j]);
						 tempList.add(tempChar[k]);
					  } 
				  }
			  }
		  }
		  System.out.println("" +tempList);
		  return tempList;
	}

- java082864 July 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public List<Integer> findTriplet(int[] tempChar){
		 List<Integer> tempList = new ArrayList<>();
		  for(int i=0;i<tempChar.length-2;i++){
			  for(int j=1;j<tempChar.length-1;j++){
				  for(int k=2;k<tempChar.length;k++){
					  if(tempChar[i]+tempChar[j]+tempChar[k] == 0 || tempChar.length ==0){
						 tempList.add(tempChar[i]);
						 tempList.add(tempChar[j]);
						 tempList.add(tempChar[k]);
					  } 
				  }
			  }
		  }
		  System.out.println("" +tempList);
		  return tempList;
	}

- java082864 July 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
from itertools import permutations
arr = {0, -1, 2, -3, 1}
result_list = []
for item in arr:
list1 = [x for x in arr if x != item]
permutation_list = [list(num) for num in permutations(list1, 2)]
sum_three_items_list = []

for two_items_list in permutation_list:
list1 = list(two_items_list)
list1.append(item)
sum_three_items_list.append(list1)

dict_total_three_items = {sum(nums):nums for nums in sum_three_items_list if sum(nums) == 0}
for value_items in dict_total_three_items.values():
sorted_value_items = sorted(value_items)
if sorted_value_items not in result_list:
result_list.append(sorted_value_items)

for result_item in result_list:
result_str_item = [str(i) for i in result_item]
print(",".join(result_str_item))
}}

- Hiuy July 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.java.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Triplet {

private final int x1;

private final int x2;

private final int x3;

public Triplet(int x1, int x2, int x3) {
super();
this.x1 = x1;
this.x2 = x2;
this.x3 = x3;
}

@Override
public String toString() {
return "Triplet [x1=" + x1 + ", x2=" + x2 + ", x3=" + x3 + "]";
}

}

public class Triplets {

public static List<Triplet> zeroSum(int arr[]) {
List<Triplet> triplets = new ArrayList<Triplet>();
Arrays.sort(arr);
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 0) {
break;
}
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] > 0) {
break;
}
for (int k = j + 1; k < arr.length; k++) {
if (arr[i] + arr[j] + arr[k] > 0) {
break;
} else if (arr[i] + arr[j] + arr[k] == 0) {
Triplet triplet = new Triplet(arr[i], arr[j], arr[k]);
triplets.add(triplet);
}
}
}
}
return triplets;
}

public static void main(String[] args) {
int arr[] = { 0, -1, 2, -3, 1,-5,1,4 };
System.out.println(zeroSum(arr));

}

}

- java baby July 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.java.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Triplet {

private final int x1;

private final int x2;

private final int x3;

public Triplet(int x1, int x2, int x3) {
super();
this.x1 = x1;
this.x2 = x2;
this.x3 = x3;
}

@Override
public String toString() {
return "Triplet [x1=" + x1 + ", x2=" + x2 + ", x3=" + x3 + "]";
}

}

public class Triplets {

public static List<Triplet> zeroSum(int arr[]) {
List<Triplet> triplets = new ArrayList<Triplet>();
Arrays.sort(arr);
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 0) {
break;
}
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] > 0) {
break;
}
for (int k = j + 1; k < arr.length; k++) {
if (arr[i] + arr[j] + arr[k] > 0) {
break;
} else if (arr[i] + arr[j] + arr[k] == 0) {
Triplet triplet = new Triplet(arr[i], arr[j], arr[k]);
triplets.add(triplet);
}
}
}
}
return triplets;
}

public static void main(String[] args) {
int arr[] = { 0, -1, 2, -3, 1,-5,1,4 };
System.out.println(zeroSum(arr));

}

}

- java baby July 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public List<int[]> getTriplets(int[] arr){
	//First sort the array O(NlogN)
	List<int[]> result = new ArrayList();
	for(int i=0; i<arr.length; ++i){
		if(i > 0 && arr[i] == arr[i-1]) continue; // Avoid duplicates
		int left = i+1, right = arr.length - 1;
		while(left < right){
			int sum = arr[i] + arr[left] + arr[right];
			if(sum < 0) l++;
			else if(sum > 0) r--;
			else{
				result.add(new int[]{i, left, right});
				while(left < right && arr[left] == arr[left + 1]) left++;
				while(left < right && arr[right] == arr[right - 1]) right++;
				left++;
				right--;
			}	
		}
		return result;
}

- tomahawk August 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please do remember to check the cases [0, 0, 0]

- test case [ 0, 0, 0] September 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findZeroSet(int[] nums){
  String divider = " , ";
  int lastIndex = nums.length - 1;

  int firstIndex = 0;
  int secondIndex = firstIndex + 1;
  int thirdIndex = secondIndex + 1;

  while(firstIndex < lastIndex - 1){
    if(nums[firstIndex] + nums[secondIndex] + nums[thirdIndex] == 0){
      System.out.println(new StringBuilder("zero set : ").append(nums[firstIndex]).append(divider).append(nums[secondIndex]).append(divider).append(nums[thirdIndex]).toString());
    }

    if(thirdIndex == lastIndex){
      if(secondIndex == lastIndex -1){
        firstIndex ++;
        secondIndex = firstIndex + 1;
        thirdIndex = secondIndex + 1;
      }else{
        secondIndex ++;
        thirdIndex = secondIndex + 1;
      }
    }else{
      thirdIndex ++;
    }   
  }
}

- Yuseon Han October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findZeroSet(int[] nums){
  String divider = " , ";
  int lastIndex = nums.length - 1;

  int firstIndex = 0;
  int secondIndex = firstIndex + 1;
  int thirdIndex = secondIndex + 1;

  while(firstIndex < lastIndex - 1){
    if(nums[firstIndex] + nums[secondIndex] + nums[thirdIndex] == 0){
      System.out.println(new StringBuilder("zero set : ").append(nums[firstIndex]).append(divider).append(nums[secondIndex]).append(divider).append(nums[thirdIndex]).toString());
    }

    if(thirdIndex == lastIndex){
      if(secondIndex == lastIndex -1){
        firstIndex ++;
        secondIndex = firstIndex + 1;
        thirdIndex = secondIndex + 1;
      }else{
        secondIndex ++;
        thirdIndex = secondIndex + 1;
      }
    }else{
      thirdIndex ++;
    }   
  }
}

- Yuseon Han October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findZeroSet(int[] nums){
  String divider = " , ";
  int lastIndex = nums.length - 1;

  int firstIndex = 0;
  int secondIndex = firstIndex + 1;
  int thirdIndex = secondIndex + 1;

  while(firstIndex < lastIndex - 1){
    if(nums[firstIndex] + nums[secondIndex] + nums[thirdIndex] == 0){
      System.out.println(new StringBuilder("zero set : ").append(nums[firstIndex]).append(divider).append(nums[secondIndex]).append(divider).append(nums[thirdIndex]).toString());
    }

    if(thirdIndex == lastIndex){
      if(secondIndex == lastIndex -1){
        firstIndex ++;
        secondIndex = firstIndex + 1;
        thirdIndex = secondIndex + 1;
      }else{
        secondIndex ++;
        thirdIndex = secondIndex + 1;
      }
    }else{
      thirdIndex ++;
    }   
  }
}

- Anonymous October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findZeroSet(int[] nums){
  String divider = " , ";
  int lastIndex = nums.length - 1;

  int firstIndex = 0;
  int secondIndex = firstIndex + 1;
  int thirdIndex = secondIndex + 1;

  while(firstIndex < lastIndex - 1){
    if(nums[firstIndex] + nums[secondIndex] + nums[thirdIndex] == 0){
      System.out.println(new StringBuilder("zero set : ").append(nums[firstIndex]).append(divider).append(nums[secondIndex]).append(divider).append(nums[thirdIndex]).toString());
    }

    if(thirdIndex == lastIndex){
      if(secondIndex == lastIndex -1){
        firstIndex ++;
        secondIndex = firstIndex + 1;
        thirdIndex = secondIndex + 1;
      }else{
        secondIndex ++;
        thirdIndex = secondIndex + 1;
      }
    }else{
      thirdIndex ++;
    }   
  }
}

- Yuseon Han October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findZeroSet(int[] nums){
  String divider = " , ";
  int lastIndex = nums.length - 1;

  int firstIndex = 0;
  int secondIndex = firstIndex + 1;
  int thirdIndex = secondIndex + 1;

  while(firstIndex < lastIndex - 1){
    if(nums[firstIndex] + nums[secondIndex] + nums[thirdIndex] == 0){
      System.out.println(new StringBuilder("zero set : ").append(nums[firstIndex]).append(divider).append(nums[secondIndex]).append(divider).append(nums[thirdIndex]).toString());
    }

    if(thirdIndex == lastIndex){
      if(secondIndex == lastIndex -1){
        firstIndex ++;
        secondIndex = firstIndex + 1;
        thirdIndex = secondIndex + 1;
      }else{
        secondIndex ++;
        thirdIndex = secondIndex + 1;
      }
    }else{
      thirdIndex ++;
    }   
  }
}

- Yuseon Han October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findZeroSet(int[] nums){
String divider = " , ";
int lastIndex = nums.length - 1;

int firstIndex = 0;
int secondIndex = firstIndex + 1;
int thirdIndex = secondIndex + 1;

while(firstIndex < lastIndex - 1){
if(nums[firstIndex] + nums[secondIndex] + nums[thirdIndex] == 0){
System.out.println(new StringBuilder("zero set : ").append(nums[firstIndex]).append(divider).append(nums[secondIndex]).append(divider).append(nums[thirdIndex]).toString());
}

if(thirdIndex == lastIndex){
if(secondIndex == lastIndex -1){
firstIndex ++;
secondIndex = firstIndex + 1;
thirdIndex = secondIndex + 1;
}else{
secondIndex ++;
thirdIndex = secondIndex + 1;
}
}else{
thirdIndex ++;
}
}
}

- Yuseon Han October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findZeroSet(int[] nums){
String divider = " , ";
int lastIndex = nums.length - 1;

int firstIndex = 0;
int secondIndex = firstIndex + 1;
int thirdIndex = secondIndex + 1;

while(firstIndex < lastIndex - 1){
if(nums[firstIndex] + nums[secondIndex] + nums[thirdIndex] == 0){
System.out.println(new StringBuilder("zero set : ").append(nums[firstIndex]).append(divider).append(nums[secondIndex]).append(divider).append(nums[thirdIndex]).toString());
}

if(thirdIndex == lastIndex){
if(secondIndex == lastIndex -1){
firstIndex ++;
secondIndex = firstIndex + 1;
thirdIndex = secondIndex + 1;
}else{
secondIndex ++;
thirdIndex = secondIndex + 1;
}
}else{
thirdIndex ++;
}
}
}

- yuseon Han October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findZeroSet(int[] nums){
  String divider = " , ";
  int lastIndex = nums.length - 1;

  int firstIndex = 0;
  int secondIndex = firstIndex + 1;
  int thirdIndex = secondIndex + 1;

  while(firstIndex < lastIndex - 1){
    if(nums[firstIndex] + nums[secondIndex] + nums[thirdIndex] == 0){
      System.out.println(new StringBuilder("zero set : ").append(nums[firstIndex]).append(divider).append(nums[secondIndex]).append(divider).append(nums[thirdIndex]).toString());
    }

    if(thirdIndex == lastIndex){
      if(secondIndex == lastIndex -1){
        firstIndex ++;
        secondIndex = firstIndex + 1;
        thirdIndex = secondIndex + 1;
      }else{
        secondIndex ++;
        thirdIndex = secondIndex + 1;
      }
    }else{
      thirdIndex ++;
    }   
  }
}

- Yuseon Han October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SumZero {
public static void main(String[] args) {
int arr[] = {0, -1, 2, -3, 1};
for(int i=0;i<arr.length-1;i++)
for(int d=1;i+d<arr.length;d++)
for(int o=0;o<arr.length;o++)
if(o!=i && o !=i+d && (arr[i] + arr[i+d] +arr[o])== 0) System.out.println(Integer.toString(arr[i]) +" "+ Integer.toString(arr[i+d]) +" " + Integer.toString(arr[o]));
}
}

- thatfernando@yahoo.com November 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void tripletsZero(int[] a) {
		StringBuilder sb = new StringBuilder();
		Arrays.sort(a);
		for(int i = 0; i < a.length; i++) {
			for(int j = i + 1; j < a.length; j++) {
				for(int x = j + 1; x < a.length; x++) {
					if(a[i] + a[j] + a[x] == 0)
					{
						sb.append(a[i] + "," + a[j] +  "," + a[x]).append("\n");
					}
						
				}
			}
		}
		System.out.print(sb.toString());
	}

- user1994 January 08, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n^2) Solution... with O(1) space...

1. Sort the array.
2. For each element nums[i], perform TwoSum search by calling twoSum(nums,i+1, nums.length, target-nums[i])
3. You might want to use HashMapList to avoid adding duplicate triplets.

TwoSum on sorted array:
1. Take 2 pointers, start and end.
2. if(tar

public void twoSum(int[] nums, int start, int end, int target){
		while(start < end){
			if(target == nums[start]+ nums[end]){
				//Add to the list
				start++;
				end--;
			}
			else{
				if(target is less){
					start++;
				}else{
					end--;
				}
			}
		}
	}

- Somal February 25, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?
/*
For given list of numbers find out triplets with sum 0 
Input : arr[] = {0, -1, 2, -3, 1} 
Output : 0 -1 1 
2 -3 1


*/


function findTriplets($array,$sum) {
  

  foreach($array as $value) {
  	$map[] = $sum-$value;

  }	
  for($i=0;$i< count($array);$i++) {
  	for($j=$i+1;$i<count($array);$j++) {
  		for($k=$j+1;$k<count($array);$k++) {
  			if($array[$i]+$array[$j]+$array[$k] == 0) {
  				return [$array[$i],$array[$j],$array[$k]];
  			}
  		}
  	}
  }


}
$array = [0, -1, 2, -3, 1];
$result = findTriplets($array,0);
print_r($result);

?>

- rahul November 05, 2018 | Flag Reply


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