Facebook Interview Question
Country: United States
Interview Type: Phone Interview
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.
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;
}
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;
}
{{
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))
}}
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));
}
}
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));
}
}
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;
}
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 ++;
}
}
}
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 ++;
}
}
}
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 ++;
}
}
}
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 ++;
}
}
}
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 ++;
}
}
}
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 ++;
}
}
}
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 ++;
}
}
}
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 ++;
}
}
}
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]));
}
}
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());
}
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--;
}
}
}
}
<?
/*
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);
?>
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)
- kredible July 15, 2017