Facebook Interview Question for Software Engineer Interns

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
5
of 7 vote

All the solutions here involving sorting which is not good. there is much better one without sorting:
1. insert the numbers in to hashmap - O(n)
2. got over the list second time with 12 - arr[i] = res
and look for res in the hashmap if res is in the hashmap return true. O(n)
so to sum up: first walk and insert into hash map is O(n) second walk over the list and check if the 12 minus the number is in the hashmap is O(n) cause it's O(1) for each check. so O(n) + O(n) = O(n)

Enjoy!

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

Sweet!

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

Great.
You got it right. I liked it.

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

Great solution, though if the numbers in the array that sum to 12 must be distinct (which I assume they do), you need a special case if an element is equal to 6. If the array = , your algorithm will return true even though there aren't technically two numbers that sum to 12.

To fix this, you can just add if (arr[i] == 6) { // then walk the array to see if 6 shows up at least one more time }. The solution still runs in linear time.

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

Almost perfect, but it doesn't work with [1, 6, 2].
Don't insert 6 into the hashmap. Count the occurrences instead. If 6 appears twice or more, return true. If not, look for 12 - arr[i] in the hashmap.

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

Nice idea!

Comment hidden because of low score. Click to expand.
2

a map isn't necessary you can do this with a set and save space. its also not efficient to add all these values into the map then look through the whole map when you already know, based on each value, what is required to create a valid pairing. Instead of focusing on creating a matching and seeing if it fits, create a set of valid answer values for each value you encounter, if that value isn't already found in the answer set.

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

@hideki.ikeda to deal with that case and also for the case of duplicates there is this solution: instead of saving only the number in the Map, save the number and the index of it in the array, use some sort of class like:
class NumIndex {
int num;
int index;
}

then the map would be a map of Map<Integer, NumIndex> then you can put an if condition when you find a value that matches,
12 - arr[i] = res --> NumIndex nIndex = Map.get(res)
is it a valid combination ? If (nIndex.index != currentNumber.index) -> true;

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

This is just a data structures application problem. If you use a O(1) lookup structure like a set in python, you can solve this in O(n) time.

In python, the solution would be:

def find_if_sum(total, vals):
val_set = set()
for x in vals:
if x in val_set:
return True
else:
return False

The logic is simple: as you traverse the array, you will see, for each number, its required sibling value such that the two sum to the given total. By the time you reach the last value, if it isn't already in the set, none of the preceding values will have worked for it. If you reached the last value and that is the case, none of the preceding values had a valid sibling within the set.

Sorting and whatnot is unnecessary. If the question were asking us to return the actual pair which equals that total, that would be a solution. But all it wants us to do is confirm it has a valid pairing.

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

public static void main(String[] args) {
}

public static boolean has2IntegersSumTo12(int[] a) {
if(a==null || a.length < 2) return false;

Set<Integer> s = new HashSet<Integer>();
for(int i=0; i< a.length; i++) {
if(s.contains(12-a[i])) return true;
}
return false;
}
}

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

If the range of number is not known then:
1 > Sort the array in non descending order
2 > Pick the first(lower index) and last(higher index) elements and add
3 > Now compare with '12' if less, then increment lower index and if greater, then decrement the higher index. Do it until lower index is less than higher index or pair
is found.

If the range of number is known:
1) Create and initialize a binary "Hash Map" M[] = {0, 0, …} of size equals to range
2) Do following for each element in array
(a) If M[x - Array[i]] is set(i.e. 1) then print the pair (A[i], x – A[i])
(b) Set M[A[i]]

Note:
If range of numbers include negative numbers then also it works. All we have to do for negative numbers is to make everything positive by adding the absolute value of smallest negative integer to all numbers.
Suppose the elements of array are : { -4, 1, 2, -8 } and x = -6
Then add '8' to each element of the array and '8+8' to x.
So, now your array becomes: {4, 9, 10, 0} and x becomes 10.

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

Thanks,

I used your hints and wrote my code. With some modifications like used regular boolean array rather than hash map.

class Question {

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < input.length; i++) {
if (input[i] > max) {
max = input[i];
}
if (input[i] < min) {
min = input[i];
}
}
int offset = min;
int length = max - min + 1;
//If the range of number are too wide use simple sort
//I used 4 times of input length as too wide. You can change it.
if (length > 4 * input.length) {
}
boolean[] matches = new boolean[length];
for (int i = 0; i < input.length; i++) {
if (matches[(12 - input[i]) - offset]) {
return true;
} else {
matches[input[i] - offset] = true;
}
}
return false;
}

Arrays.sort(input);
int large = input.length - 1;
int small = 0;
while (small < large) {
if (input[small] + input[large] == 12) {
return true;
}
if (input[small] + input[large] > 12) {
large--;
}
if (input[small] + input[large] < 12) {
small++;
}
}
return false;
}
}

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

def sum(arr,sum)
len = arr.length
if len == 1
if arr == sum
return true
else
return false
end
end

arr.sort!
i = 0
j = len-1
while i < j do
if arr[i]+arr[j] < sum
i += 1
elsif arr[i]+arr[j] > sum
j -= 1
else
return true
end
end
return false
end

arr = [1,4,6,3,9,10]
puts sum(arr,12)

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

public static boolean isSumEquals8(int[] arr) {
boolean result = false;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] == 8) {
System.out.println("Sum of " + arr[i] + " " + arr[j]
+ " coming out to be 8");
result = true;
break;

}
}
if(result==true){
break;
}
}
return result;
}

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

this is O(n^2), usually not good solution to provide in any interview, unless there is no better one

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

bool has_a_sum_to_12(std::vector<int> arr)
{
std::map<int, int> numbers;

// Keep a map of every value in the array
for (auto i : arr)
numbers[i]++;

for (auto p : numbers)
{
// for each value p in the array, we have a sum to 12 if there exist
// another value x such as p + x = 12
// so: x = 12 - p
if (numbers.find(12 - p.first) != numbers.end())
return true;
}
return false;
}

This runs in O(n) time and O(n) space.

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

Yes, not bad. You just have to consider that if 6 is there, your solution always returns true

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

there is an O(n) solution with inserting into a hashmap first walk over the list and second walk checking if the difference of the numbers and 12 are in the hashmap.

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

class Solution:
def two_sum(self, a, sum):
dict = {}
for elem in a:
dict[elem] = elem
for elem in a:
if dict.__contains__(sum-elem):
return True
return False

if __name__ == '__main__':
a = Solution()
print a.two_sum([9,2,1,4,6,5,3,7], 15)

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

public static void main(String[] args) {
int[] nums = {1,2,3,4,5,6,4};
}

public static boolean has2IntegersSumTo12(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < nums.length; i++) {
if(set.contains(12-nums[i])) {
return true;
}
}
return false;
}

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

public class HashMap1 {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

int numbertosearched = 12;

HashMap <Integer,Integer> hm = new HashMap<Integer,Integer>();
hm.put(1, 10);
hm.put(2, 11);
hm.put(3, 30);
hm.put(4, 1);
hm.put(5, 12);

Set<Integer> key = hm.keySet();

for(Integer i:key) {
//System.out.println("Key is " + i + "Value is " + hm.get(i));
System.out.println("Key is " + i + "Value is " + hm.containsValue((numbertosearched-hm.get(i))));

}

}

}

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

HashSet<Integer> set = new HashSet<>(a.length);
for (int x : a) {
if (set.contains(12 - x)) {
return true;
} else {
}
}
return false;
}

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

public class CheckNumbers {

static int array[] = {1, 3, 4, 6, 7};

public static boolean useMap(int sum) {
HashMap s = new HashMap();
for (int i=0; i<array.length; i++) {
s.put(array[i],i);
}

boolean found = false;

for (int i=0; i<array.length; i++) {
int num = array[i];
int numRequired = sum - array[i];
if (s.containsKey(numRequired) && ((Integer) s.get(numRequired)).intValue()!=i) {
found = true;
break;
}
}

return found;
}

public static void main(String argv[]) {
System.out.println(useMap(12));
System.out.println(useMap(13));
}

}

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

Here is my C++ version of answer using hashtable. Running time will be O(N)

#include<map>
#include<iostream>
using namespace std;

bool has_sum(int* input, int len, int target)
{
map<int, int> hashtable;
map<int, int>::iterator iter;
int i = 0;
for (i = 0; i< len; i++)
hashtable[input[i]] = input[i];

for (i = 0; i <len; i++)
{
int left = target - input[i];
iter = hashtable.find(left);
if (iter != hashtable.end())
return true;
}
return false;
}

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

the java version for this problem alternatively be written as

import java.util.ArrayList;

public class SumCheck {

public static void main(String args[]){

ArrayList<Integer> al = new ArrayList<Integer>();

for(int i=0;i<al.size();i++){
int a = al.get(i);
for(int j = i+1;j<al.size();j++){
int b = al.get(j);
int sum = a+b;
if(sum==12) System.out.println(true);
}
}
}
}

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

Solution in javascript:

function hasCS(arr, res) {
var i = 0,
j = 0,
sum = 0;

while(i <= arr.length && j <= arr.length) {

if(sum < res) {
sum = sum + arr[j];
j++;

} else if(sum > res) {
sum = sum - arr[i];
i++;

} else {
return true;
}
}

return false;;
}

var res1 = hasCS([23, 5, 4, 7, 2, 11], 20);
console.log(res1); // should return true

var res2 = hasCS([1, 3, 5, 23, 2], 7);
console.log(res2); // should return false

var res3 = hasCS([1, 3, 5, 23, 2], 8);
console.log(res3);

}

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

function hasCS(arr, res) {
var i = 0,
j = 0,
sum = 0;

while(i <= arr.length && j <= arr.length) {

if(sum < res) {
sum = sum + arr[j];
j++;

} else if(sum > res) {
sum = sum - arr[i];
i++;

} else {
return true;
}
}

return false;;
}

var res1 = hasCS([23, 5, 4, 7, 2, 11], 20);
console.log(res1); // should return true

var res2 = hasCS([1, 3, 5, 23, 2], 7);
console.log(res2); // should return false

var res3 = hasCS([1, 3, 5, 23, 2], 8);
console.log(res3);

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

javascript solution

function hasCS(arr, res) {
var i = 0,
j = 0,
sum = 0;

while(i <= arr.length && j <= arr.length) {

if(sum < res) {
sum = sum + arr[j];
j++;

} else if(sum > res) {
sum = sum - arr[i];
i++;

} else {
return true;
}
}

return false;;
}

var res1 = hasCS([23, 5, 4, 7, 2, 11], 20);
console.log(res1); // should return true

var res2 = hasCS([1, 3, 5, 23, 2], 7);
console.log(res2); // should return false

var res3 = hasCS([1, 3, 5, 23, 2], 8);
console.log(res3);

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

/* Function to check if sum exist
* Time Complexity: O(n)
* Space Complexity: O(n) -> using HashMap of size of array size n
* */
private static boolean checkSum(int[] a, int sum) {
if(a == null)
return false;

// Add all the int values to HashMap
Map<Integer, Integer> arrayMap = new HashMap<Integer, Integer>();
for(int i = 0; i< a.length; i++){
int currVal = a[i];
if(arrayMap.containsKey(currVal)){
arrayMap.put(currVal, arrayMap.get(currVal) + 1);
}else{
arrayMap.put(currVal, 1);
}
}

// Run again to check if sum exist
for(int i = 0; i< a.length; i++){
int currVal = a[i];
int remainSum = sum - a[i];
// If number like 6 exist and only one occurance then skip it
if(remainSum == currVal && arrayMap.get(currVal) < 2){
continue;
}
// Check if value found
if(arrayMap.containsKey(remainSum)){
return true;
}
}

return false;
}

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

public static boolean checkSum(ArrayList<Integer> al){
HashSet<Integer> hs = new HashSet<Integer>(al);

boolean result = false;
for(int i: al){
if(hs.contains((Integer)(12-i)))
result = true;
}
return result;
}

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

public static boolean checkSum(ArrayList<Integer> al){
HashSet<Integer> hs = new HashSet<Integer>(al);

boolean result = false;
for(int i: al){
if(hs.contains((Integer)(12-i)))
result = true;
}
return result;
}

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

public static boolean checkSum(ArrayList<Integer> al){
HashSet<Integer> hs = new HashSet<Integer>(al);

boolean result = false;
for(int i: al){
if(hs.contains((Integer)(12-i)))
result = true;
}
return result;
}

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

Here is my O(n) solution,no hashmap or set, using only one extra array of boolean values. The idea is to create a boolean array with a length of 12 + 1, iterate the first array and check if in the position [12 - value] if true, if it is return true, if not set position [value] as true and continue.

public static boolean checkIfHasSum(int[] array, int sum){
boolean[] hasValue = new boolean[sum + 1];
for(int value : array){
if(value <= sum){
if(hasValue[sum - value]){
return true;
}
hasValue[value] = true;
}

}
return false;
}

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

private static boolean checkInternal(int[] in, int offset, int dist) {

if(in[offset] + in[offset+dist] == 12) return true;

if(offset == in.length - 2 && dist == 1) return false;

if(offset + dist == in.lenght) {
dist++;
offset=1;
} else offset++;

return checkInternal(in,offset,dist);
}

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

private static boolean checkInternal(int[] in, int offset, int dist) {

if(in[offset] + in[offset+dist] == 12) return true;

if(offset == in.length - 2 && dist == 1) return false;

if(offset + dist == in.lenght) {
dist++;
offset=1;
} else offset++;

return checkInternal(in,offset,dist);
}

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

The solution is to sort the array which will take nLog(n). Then take each element X in the sorted array subtract it from 12 such as int V = 12 - X then since the array is sorted you can binary search for V in Log(n). To do so for the n elements it will take nLog(n).
So the final complexity will be O(nLog(n))

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

there is an O(n) solution with inserting into a hashmap first walk over the list and second walk checking if the difference of the numbers and 12 are in the hashmap. boom!

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.

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.