Google Interview Question
Software DevelopersCountry: United States
Interview Type: Phone Interview
Sort both arrays, now get 2 pointers l2 and l1, one at the beginning of the second array and one at the end of the first array. For each iteration if l1+l2 > target then decrease l1, else increase l2, if l1+l2=target return l1 and l2, return false if l1 reaches the beginning of the first array and l2 reaches the end of the second array.
pulic int[] getSum(int[] list1 int[] list2, int target){
Arrays.sort(list1);
Arrays.sort(list2);
int l1 = list1.length-1;
int l2 = 0;
whiile(l1 >= 0 && l2 < list2.length){
if(list1[l1] + list2[l2] == target){
return [l1,l2];
}else if(list1[l1] + list2[l2] > target){
l1--;
}else{
l2++;
}
}
return null;
}
public static boolean istergetfound(int target ,ArrayList<Integer> list1,ArrayList<Integer> list2)
{
for(int i=0;i<list1.size();i++)
{
if(list1.get(i)>target)
continue;
int l1=list1.get(i);
for(int j=0;j<list2.size();j++)
{
int l2=list2.get(j);
if(l2+l1==target)
{
System.out.println("result found"+l1+"+"+l2+"="+target);
return true; }
}
}
return false;
}
The question can be solved with constant space and O(a+b) runtime, where a is the length of array1 and b is the length of array2, if the arrays are sorted
public class TwoArrSum {
public static boolean sumExists(int target, int[] arr1, int[] arr2) {
int pointer1 = 0;
int pointer2 = arr2.length - 1;
while (pointer1 <= arr1.length - 1 && pointer2 >= 0) {
int sum = arr1[pointer1] + arr2[pointer2];
if (sum < target) {
pointer1++;
if (pointer1 == arr1.length) {
pointer1 = arr1.length - 1;
}
} else if (sum > target) {
pointer2--;
if (pointer2 == -1) {
pointer2 = 0;
}
} else {
return true;
}
}
return false;
}
public static void main(String[] args) {
int[] arr1 = {1, 3, 4, 7};
int[] arr2 = {2, 4, 6, 8};
int arg = Integer.parseInt(args[0]);
System.out.println(sumExists(arg, arr1, arr2));
}
}
The question can be solved with constant space and O(a+b) runtime, given that the arrays are sorted (a is the length of array1 and b is the length of array2). The idea is the start one pointer at the beginning of array1 and another at the end of array2. You increment pointer1 when the current sum is less than the target (thus increasing the sum) and decrement pointer2 if current sum is greater than the target (thus decreasing the sum). This method also ensures no pairs are missed
public class TwoArrSum {
public static boolean sumExists(int target, int[] arr1, int[] arr2) {
int pointer1 = 0;
int pointer2 = arr2.length - 1;
while (pointer1 <= arr1.length - 1 && pointer2 >= 0) {
int sum = arr1[pointer1] + arr2[pointer2];
if (sum < target) {
pointer1++;
if (pointer1 == arr1.length) {
pointer1 = arr1.length - 1;
}
} else if (sum > target) {
pointer2--;
if (pointer2 == -1) {
pointer2 = 0;
}
} else {
return true;
}
}
return false;
}
public static void main(String[] args) {
int[] arr1 = {1, 3, 4, 7};
int[] arr2 = {2, 4, 6, 8};
int arg = Integer.parseInt(args[0]);
System.out.println(sumExists(arg, arr1, arr2));
}
}
package javapgrms;
import java.util.HashMap;
public class targetvaluefrom2list {
public static void main(String[] args) {
int[] list1={2,3,4,5,6,7,8};
int[] list2={3,4,1,2,0,5,7};
int target =7;
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
int count=0;
for(int i=0;i<list1.length;i++){
for(int j=0;j<list2.length;j++){
int sum = list1[i]+list2[j];
if(sum == target){
hm.put(list1[i], list2[j]);
count++;
}
}
}
System.out.println("no of target sum values are :" +count);
for(int c : hm.keySet()){
System.out.println(c + ":" + hm.get(c));
}
}
}
package javapgrms;
import java.util.HashMap;
public class targetvaluefrom2list {
public static void main(String[] args) {
int[] list1={2,3,4,5,6,7,8};
int[] list2={3,4,1,2,0,5,7};
int target =7;
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
int count=0;
for(int i=0;i<list1.length;i++){
for(int j=0;j<list2.length;j++){
int sum = list1[i]+list2[j];
if(sum == target){
hm.put(list1[i], list2[j]);
count++;
}
}
}
System.out.println("no of target sum values are :" +count);
for(int c : hm.keySet()){
System.out.println(c + ":" + hm.get(c));
}
}
}
public class targetvaluefrom2list {
public static void main(String[] args) {
int[] list1={2,3,4,5,6,7,8};
int[] list2={3,4,1,2,0,5,7};
int target =7;
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
int count=0;
for(int i=0;i<list1.length;i++){
for(int j=0;j<list2.length;j++){
int sum = list1[i]+list2[j];
if(sum == target){
hm.put(list1[i], list2[j]);
count++;
}
}
}
System.out.println("no of target sum values are :" +count);
for(int c : hm.keySet()){
System.out.println(c + ":" + hm.get(c));
}
}
}
Of course there is the obvious n*m solution but we can do a n + m solution if we substract the values out of the total and store the values in a hash set and then look up the value of the other list.
Here is a solution in C#:
public bool IsSumPossibe(int[] nA, int[] mA, int total)
{
var substract = new HashSet<int>();
foreach(var n in nA)
{
substract.Add(total - n);
}
if(divided.Count == 0) return false;
foreach(var m in mA)
{
if(substract.Contains(m))
{
return true;
}
}
return false;
}
import java.util.Scanner;
class G_Target{
public static void main(String s[]){
Scanner sc = new Scanner(System.in);
System.out.print("enter the size of lists\n");
int i = sc.nextInt();
System.out.print("enter the target value: ");
int h = sc.nextInt();
int list1[] = new int[i];
int list2[] = new int[i];
int list3[] = new int[i];
int j,k,l=0;
System.out.print("enter the element of list1 \n");
for(k=0;k<i;k++){
list1[k] = sc.nextInt();
}
System.out.print("enter the element of list2 \n");
for(k =0;k<i;k++){
list2[k] = sc.nextInt();
}
for(k=0;k<i;k++){
list3[k] = list1[k]+list2[k];
System.out.print(" "+list3[k]+"\n");
}
for(k=0;k<i;k++){
if(list3[k] == h){
System.out.print(" Target Find");
break;}
else{
System.out.print("Target not there");
break;}
}
System.out.print("\n");
}
}
A C++ solution
This strategy builds a list of values needed to reach the sum. The second loop searches the sum list for each value. The trick is to take advantage of hash maps (unordered_set), although if space concerns exist, a binary search tree can be used instead (set).
Using std::unordered_set
Time: O(n) to O(n^2)
Space: O(n)
Using std::set
Time: O(nlogn)
Space: O(n)
bool check(int list1[], int list2[], int sum,
int count1, int count2)
{
// Corner/Edge cases
if (sum <= 0 || count1 < 1 || count2 < 0) return false;
// Create a list of sum values needed for the second list
std::unordered_set<int> sums;
// Add the needed sum values to a hash map
for (int i = 0; i < count1; ++i)
if (list1[i] <= sum)
sums.insert(sum - list1[i]);
// Check each value in list2 if it exists in the hash map
for (int i = 0; i < count2; ++i)
if (sums.find(list2[i]) != sums.end())
return true;
return false;
}
public boolean isTargetFound(){
List<Integer> list1=Arrays.asList(10,02,73,46,5,16,7,8,29);
List<Integer> list2=Arrays.asList(11,2,31,4,5,56,7,88,29);
Scanner scan=new Scanner(System.in);
int targetValue=scan.nextInt();
System.out.println("targetValue>>>>>>>>>"+targetValue);
for(int i=1;i<list1.size();i++){
if(list2.contains(targetValue-list1.get(i))){
System.out.println("here u go>>targetValue>>"+targetValue);
System.out.println("here u go>>list1.get(i))>>"+list1.get(i));
System.out.println("here u go>>>>"+(targetValue-list1.get(i)));
return true;
}
}
return false;
}
public static void main(String args[]){
WAPSumbetweentwoLists w=new WAPSumbetweentwoLists();
boolean isfound=w.isTargetFound();
//sysout();
System.out.println("isfound>>>>>>"+isfound);
}
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class WAPSumbetweentwoLists {
public boolean isTargetFound(){
List<Integer> list1=Arrays.asList(10,02,73,46,5,16,7,8,29);
List<Integer> list2=Arrays.asList(11,2,31,4,5,56,7,88,29);
Scanner scan=new Scanner(System.in);
int targetValue=scan.nextInt();
System.out.println("targetValue>>>>>>>>>"+targetValue);
for(int i=1;i<list1.size();i++){
if(list2.contains(targetValue-list1.get(i))){
System.out.println("here u go>>targetValue>>"+targetValue);
System.out.println("here u go>>list1.get(i))>>"+list1.get(i));
System.out.println("here u go>>>>"+(targetValue-list1.get(i)));
return true;
}
}
return false;
}
public static void main(String args[]){
WAPSumbetweentwoLists w=new WAPSumbetweentwoLists();
boolean isfound=w.isTargetFound();
//sysout();
System.out.println("isfound>>>>>>"+isfound);
}
}
In your code, you don't have to sort both the arrays, sorting one array is sufficient, like the code I have written.
#include "stdafx.h"
#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;
class Solution {
public:
int target=35;
int search(int num,vector<int> v2) {
int low = 0;
int high = v2.size()-1;
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (v2[mid] == num)
return 1;
if (num > v2[mid])
low = mid + 1;
else
high = mid - 1;
}
return 0;
}
bool exists(vector<int> v1, vector<int> v2) {
std::sort(v2.begin(), v2.end());
for (int i = 0; i < v2.size(); i++) {
if (search(target - i,v2))
return 1;
}
return 0;
}
};
int main()
{
Solution s;
cout<<s.exists({ 10,20,2,1,3,4,42,23,24 }, { 4,5,2,0,22,32,-1 });
return 0;
}
#include "stdafx.h"
#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;
class Solution {
public:
int target=35;
int search(int num,vector<int> v2) {
int low = 0;
int high = v2.size()-1;
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (v2[mid] == num)
return 1;
if (num > v2[mid])
low = mid + 1;
else
high = mid - 1;
}
return 0;
}
bool exists(vector<int> v1, vector<int> v2) {
std::sort(v2.begin(), v2.end());
for (int i = 0; i < v2.size(); i++) {
if (search(target - i,v2))
return 1;
}
return 0;
}
};
int main()
{
Solution s;
cout<<s.exists({ 10,20,2,1,3,4,42,23,24 }, { 4,5,2,0,22,32,-1 });
return 0;
}
1. Insert all numbers from one of the list(say List1) to a HashTable/Map/Dictionary
- CodeBuster September 02, 20162. Iterate through other List
a. n= target - list(i)
b. if hashTable.ContainsKey(n), then you found that pair
Complexity:
Space: O(n)
Time : since HashTable has constant time complexity in look up, it O(1)
If extra space is not allowed, then probably time complexity would be )(n2)