Facebook Interview Question Software Engineer Interns
Country: United States
Interview Type: Phone Interview
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 = [6], 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.
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.
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.
@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;
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:
val_set.add(total-x)
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.
public class HasTwoIntegersSumtTo12 {
public static void main(String[] args) {
System.out.println(has2IntegersSumTo12(new int[] {2,6,2,7,8,2,1,2,93,5,9}));
}
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;
s.add(new Integer(a[i]));
}
return false;
}
}
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.
Thanks,
I used your hints and wrote my code. With some modifications like used regular boolean array rather than hash map.
class Question {
public boolean does2Add12(int[] input) {
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) {
return does2Add12ScatteredNumbers(input);
}
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;
}
private boolean does2Add12ScatteredNumbers(int[] input) {
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;
}
}
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;
}
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.
public static void main(String[] args) {
int[] nums = {1,2,3,4,5,6,4};
System.out.println(has2IntegersSumTo12(nums));
}
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;
}
set.add(nums[i]);
}
return false;
}
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))));
}
}
}
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));
}
}
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;
}
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>();
al.add(2);
al.add(7);
al.add(10);
al.add(5);
al.add(1);
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);
}
}
}
}
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);
}
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);
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);
/* 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;
}
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;
}
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))
All the solutions here involving sorting which is not good. there is much better one without sorting:
- Ilya April 15, 20151. 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!