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.
Answer

Interview Answer

9 Answers

0

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

Anon on Mar 15, 2012
2

Assuming each number only appears once:

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

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

    while(start target
        end--;
    }
  }

OtherAnon on Apr 2, 2012
0

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
   {
      start=0;
      end=i-1;
      target=array[i];
      //note a<=b<=c for the tuples formed here hence check for c=a+b only
      while(start

light on Apr 8, 2012
1

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
target=array[i];
with
target=total-array[i];

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

light on Apr 8, 2012
1

we can modify the 3sum algorithm for this.

Hesh on Nov 12, 2012
1

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
0

@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
0

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]) {
                    j--;
                } 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
0

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.