Facebook Interview Question: Given a sorted array, write a... | Glassdoor

Interview Question

Software Engineering Intern Interview(Student Candidate) Menlo Park, CA

Given a sorted array, write a program to decide if two

  elements sum up to a third.

Interview Answer

9 Answers


Did you coded a solution < O(n^2 + logn) ?

Anon on Mar 15, 2012

Assuming each number only appears once:

//Java code
public static void targetsum(int[] arr, int target)
    if(arr == null)

    int start = 0;
    int end = arr.length -1;

    while(start target

OtherAnon on Apr 2, 2012

typedef vector vint;
bool check_element_sum(vint &array)
   // n^2 algorithm
   sort(array.begin(),array.end()); //general case : nlogn

   copy(array.begin(),array.end(),ostream_iterator(cout," "));
   cout=0;--i) //n^2
      //note a<=b<=c for the tuples formed here hence check for c=a+b only

light on Apr 8, 2012

the algorithm for 3 elements sum up to a given number is also the same; the only change one needs to make is replace line

is there an algorithm with a lower order? says O( nlogn ); I am not able to think of anything!

light on Apr 8, 2012

we can modify the 3sum algorithm for this.

Hesh on Nov 12, 2012

It is possible to do it in O(n)
create a binary tree from the sorted array in O(n)
subtract each value in array from target and find if its there in the tree,
if found push to hash map, with the array item as key and the subtracted value as key
 next time before subtracting value in the array from target check if it is in the hash map

Pal on Feb 13, 2013

@Pal the hash map gives a lower constan because /2 elements need to be checked but the lookup is still n*logn

kungi on Oct 16, 2014

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;

public class SumOfTwoElements {

    public static void main(String[] args) {
        final Scanner in = new Scanner(System.in);
        final Random random = new Random();
        while (true) {
            System.out.println("Enter array size : ");
            int size = in.nextInt();

            int[] array = new int[size];
            for (int i = 0; i > findSummingTriplets2(int[] array) {
        final Set> summingTriplets = new HashSet>();

        for (int k = 2; k array[k]) {
                } else if (sum > findSummingTriplets(int[] array) {
        final Set> summingTriplets = new HashSet>();

        for (int i = 0; i end) {
            return false;
        int mid = start + (end - start) / 2;

        if (array[mid] > value) {
            return contains(array, start, mid - 1, value);
        } else if (array[mid] < value) {
            return contains(array, mid + 1, end, value);
        } else {
            return true;


Ker on Feb 25, 2015

bool sumExists(vector nums, int target) {
auto front = nums.begin();
auto back = nums.end() - 1;

while (front != back) {
if (*front + *back == target) return true;
else if (*front + *back < target) front++;
else back--;

return false;

O(n) time, O(1) space, C++ on Feb 10, 2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.