## Google Interview Question for Software Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
6
of 8 vote

1. Insert all numbers from one of the list(say List1) to a HashTable/Map/Dictionary
2. 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)

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

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;
}``````

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

Merge sort -in place(in-place Heap sort can be considered too O(nlogn) ) should do with binary search but yes time complexity will increase.
If API usage is allowed, why not use Arrays.sort function followed by binary search? But O(n log n) is not guaranteed as stated in the javadocs.

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

use sort or use hashing.

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

``````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;
}``````

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

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));
}
}``````

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

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));
}
}``````

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

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));
}
}

}

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

``````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));
}
}

}``````

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

``````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));
}
}

}``````

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

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)
{

}

if(divided.Count == 0) return false;

foreach(var m in mA)
{
if(substract.Contains(m))
{
return true;
}
}

return false;
}``````

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

``````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");
}
}``````

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

Easy and clean code:

``````public boolean existsPair(int[] array1, int[] array2){
Hashset<Integer> set = new Hashset<>();

for(int num : array1)

for(int num : array2)
if(set.contains(-num))
return true;

return false;

}``````

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

``````def find_sum(l1, l2, val):
search_dict = set(l2)
for x in l1:
if val - x in search_dict:
return True
return False

a = [1,2,3,4,5,6,7,8,9,10]
b = [11,12,13,14,15,16,17,18,19,20]
print find_sum(a, b, 15)``````

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

3 line Python solution

``````def in_combo(l1, l2, t):
s1 = set([t-l for l in l1])
return len(s1.intersection(set(l2))) == 1``````

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

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;
}``````

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

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);
}

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

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);
}

}

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

Here is the most simple solution....but it takes you to o(n) worst case and best case o(1)

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

trial

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

``int x = 8;``

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

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;
}``````

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

``````#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;
}``````

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

``````private static boolean isTargetsumExists(int[] list1, int[] list2, int target) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();

for (int i : list1) {
map.put(Math.abs(i), i);
}

for (int j : list2) {
if(map.get(Math.abs(target-j)) != null ) {
return true;
}
}
return false;
}``````

Comment hidden because of low score. Click to expand.

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.