Facebook Interview Question for SDE1s


Country: United States




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

We could use a hash to remember the sums of the elements we visited so far:

void findTriplet(std::vector<int>& numbers)
{
    std::sort(numbers.begin(), numbers.end()); // O(NlogN)
    std::unordered_map<int, std::pair<int, int>> Sums; // Keep track of the sums we visited so far
    for(size_t i = 0; i < numbers.size(); ++i) {
        if(Sums.count(numbers[i])) {
            // We already found a pair that matches this sum
            std::cout << numbers[i] << "=" << Sums[numbers[i]].first << "+" << Sums[numbers[i]].second << std::endl;
            break;
        } else {
            for(size_t j = 0; j < i; ++j) {
                Sums[numbers[j] + numbers[i]] = { numbers[i], numbers[j] };
            }
        }
    }
}

EDIT: updated the solution to support cases such as [7,4,3]

- PenChief October 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

@PenChief,
Does your solution work with an input say [7, 3, 4]?
i = 0, map doesn't have 7, move on,
i = 1, map doesn't have 3, j = 0, add 10 to map.
i = 2, map doesn't have 4, j = 0, add 11 to map, j = 1, add 7 to map.
terminate.
doesn't seem to return any result.

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

You can first sort the array. There goes O(nlogn). Then have nested for() loop and use
binary search to find the element = sum of first two. Put early exits when sum is > last
element.

int
bin_search (int a[], int s, int e, int v)
{
	int m;
	while (s<e) {
		m = s + (e-s)/2;
		if (a[m] == v) {
			return m;
		} else if (a[m] > v) {
			e = m-1;
		} else {
			s = m+1;
		}
	}
	return -1;
}

void
find_triplet (int a[], int n)
{
	int i, j, k;

	// Sort array first - O(nlogn)

	for (i=0; i<n-2; i++) {
		if ((a[i] + a[i+1]) > a[n-1]) break;
		for (j=i+1; j<n-1; j++) {
			if (a[n-1] < (a[i] + a[j])) break;
			k = bin_search(a, j+1, n-1, a[i] + a[j]);
			if (k != -1) {
				printf("Found the triplet %d + %d = %d\n", a[i], a[j], a[k]);
			}
		}
	}
}

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

There must be a better solution, but it seems I cannot do better than O(n^2)

A = [1, 2, 4, 9, 10]
B = {}
for(int i = 0; i < A.len; i++) {
    for(int j = i+1; j < A.len; j++) {
        B.add(A[i] + A[j])
    }
}
intersection(set(A), B)

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

@Thangaprabhu you don't have the "key", you need to find it as well

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

@Alex, the question is to find a, b and c which satisfies the condition : a+b=c
your solution assumes they are part of the input.

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

Is it possible to solve this in less than O(n^2) time?

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

@PenChief. Thank you! I just didn't understand the task :) Updated solution:

void FindTriplet(vector<int> &array)
{
	sort(array.begin(), array.end());
	unordered_map<int, int> counts;
	for (int n : array) {
		++counts[n];
	}
	for (int i = 0; i < array.size(); ++i) {
		int c = array[i];
		int half = c >> 1;
		for (int j = i - 1; j >= 0 && array[j] <= half; --j) {
			int a = array[j];
			int b = c - a;
			if (counts[b] >= (a == half) ? 2 : 1) {
				cout << a << " + " << b << " = " << c << "\n";
				return;
			}
		}
	}
}

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

public static boolean checkSumInArray(int[] arr){
    int n=arr.length;
     if(n<2){
         return false;
     }
     for(int k=1;k<n;k++){
         for(int i=0; i<=k-1;i++){
             for(int j=i+1;j<=k;j++){
                if(arr[i]+arr[j]==arr[k]){
                     return true;
                 }
             }
         }

     }
       return false;
    }

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

public static boolean checkSumInArray(int[] arr){
    int n=arr.length;
     if(n<2){
         return false;
     }
     for(int k=1;k<n;k++){
         for(int i=0; i<=k-1;i++){
             for(int j=i+1;j<=k;j++){
                if(arr[i]+arr[j]==arr[k]){
                     return true;
                 }
             }
         }

     }
       return false;
    }

- Swati Shaw October 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@PenChief,
Does your solution work with an input for example [7, 3, 4]?

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

O(N^2) time, no additional space.
less than O(N^2) time it is not possible to solve the problem.

public boolean mainFunction(int[] arr) {

        if (arr.length < 2)
            return false;

        Arrays.sort(arr);

        Tuple inds = new Tuple(0, 1);
        int sumInd = 0;

        while (inds != null) {
            int sum = arr[inds.x] + arr[inds.y];
            sumInd = findSumNextInd(arr, sum, sumInd);
            if (sum == arr[sumInd]) {
                return true;
            } else if (sumInd == arr.length - 1) {
                return false;
            }
            inds = getNextLowestSumInds(arr, inds);
        }
        return false;
    }


    // always keep x < y
    public Tuple getNextLowestSumInds(int[] arr, Tuple currIndices) {

        // invalid input
        if (arr == null || currIndices == null)
            return null;

        int currX = currIndices.x;
        int currY = currIndices.y;

        // invalid input
        if (currX >= currY)
            return null;

        // nothing to search
        if (currX >= arr.length - 2 && currY >= arr.length - 1) {
            return null;
        }

        int newX, newY;
        if (currX + 1 == currY) {
            return new Tuple(currX, currY+1);

        } else {
            if (currY == arr.length - 1) {
                return new Tuple(currX+1, currX+2);
            } else {
                // 2 options:
                // 1. (currX, currY+1) or (currX+1, currY)
                int sum1 = arr[currX] + arr[currY+1];
                int sum2 = arr[currX+1] + arr[currY];

                if (sum1 > sum2) {
                    return new Tuple(currX, currY+1);
                } else {
                    return new Tuple(currX+1, currY);
                }
            }
        }
    }

    public int findSumNextInd(int[] arr, int sum, int startIndex) {
        int ind = startIndex;

        if (arr[ind] >= sum) return ind;

        while (ind < arr.length - 1 && arr[ind+1] <= sum) {
            ind++;
        }
        return ind;
    }

    public static class Tuple {
        public int x;
        public int y;

        public Tuple(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

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

javascript
var arr = [1,2,4,6,9];
arr.some ( function ( val, ind ) {
if ( typeof ( ind + 2 ) !== 'undefined' ) {
return ( val + b[ind + 1] === b[ind + 2] )
}

});

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

javascript

var arr = [1,2,4,6,9];
arr.some(function(val, ind){
if(typeof (ind + 2) !== 'undefined'){
return (val + b[ind + 1] === b[ind + 2])
}

})

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

I don't think we can do better then O(N^2).
First sort the array, and iterate c from len(arr)-1 to 2. Look for a and b with starting idx as 0, and b-1.

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

xzc

- sgchris January 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static boolean findSum(Integer a[], Integer key) {
		Set<Integer> set = new HashSet<>();
		for(int i=0; i<a.length; i++) {
			if(set.contains(key-a[i])) {
				return true;
			} else {
				set.add(a[i]);
			}
		}
		return false;
	}

- thangaprabhu2004 October 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Understand the question properly first.

- sri November 25, 2017 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

O(N) time, O(N) space.

bool TripletExists(vector<int> const &array, int a, int b, int c)
{
	unordered_map<int, int> seen;
	int needed_ab_count = (a == b) ? 2 : 1;
	int needed_c_count = 1;
	if (a == b && b == c) {
		needed_ab_count = needed_c_count = 3;
	}
	for (int n : array) {
		++seen[n];
		if (n == a ||
			n == b)
		{
			if (seen[c - n] >= needed_ab_count &&
				seen[c] >= needed_c_count)
			{
				return true;
			}
		}
		if (n == c) {
			if (seen[a] >= needed_ab_count &&
				seen[b] >= needed_ab_count)
			{
				return true;
			}
		}
	}
	return false;
}

- Alex October 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

<?php 

function getVariants($arr, $path = [], &$list = []) {
    if (empty($arr)) return $list;
    
    if (count($path) == 3) {
        if ($path[0] < $path[1] && $path[1] < $path[2]) {
            if (!isset( $list[implode('+', $path)] )) {
                $list[implode('+', $path)] = $path;
            }
        }
        return $list;
    }
    
    foreach ($arr as $num) {
        if (!in_array($num, $path)) {
            getVariants($arr, array_merge($path, [$num]), $list);
        }
    }
    
    return $list;
}

// check that the array has a + b = c 
function checkABC($arr) {
    $path = [];
    $list = [];
    $variants = getVariants($arr, $path, $list);
    foreach ($variants as $vKey => $variant) {
        if ($variant[0] + $variant[1] == $variant[2]) {
            echo "the case is ", $vKey, "\n";
            return true;
        }
    }
}



$arr = [1, 15, 6, 2, 9, 12];
checkABC($arr);

- sgchris January 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 4 vote

public static boolean findSum(Integer a[], Integer key) {
		Set<Integer> set = new HashSet<>();
		for(int i=0; i<a.length; i++) {
			if(set.contains(key-a[i])) {
				return true;
			} else {
				set.add(a[i]);
			}
		}
		return false;
	}

- Thangaprabhu Chandrasekhar October 05, 2017 | 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