## Google Interview Question for Backend Developers

Country: United States

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

Optimized solution using Bucket sort based approach. The integer includes negative integer as well.

For example, if the array is [3, 5, 2, -4, 8, 11] and the sum is 7, your program should return [[11, -4], [2, 5]] because 11 + -4 = 7 and 2 + 5 = 7.

My approach

/**
* Approach 1: Print all the subset and find the matching sum
* Approach 2: Apply subset sum problem which 0(cnt * a.length)
* Approach 3: 0(n) how is it possible. Bucket sort based logic
*/

Approach 3 implementation is here

public class TwoSumProblem {

private static void findTwoSum(int[] a, int cnt)
{

int[] b = new int[100];
for(int i = 0 ; i < a.length ; i++)
{
b[a[i] + 50] = b[a[i] + 50] + 1;
}
int t1 = 0;
for(int i = 0 ; i < a.length ; i++)
{
if(b[a[i] + 50] == 1 && b[cnt - a[i] + 50] == 1 && cnt - a[i] + 50 != a[i] + 50)
{
b[a[i] + 50] = b[a[i] + 50] - 1;
b[cnt - a[i] + 50] = b[cnt - a[i] + 50] - 1;
t1 = cnt - a[i];
System.out.println("Pair is " + a[i] + " and " + t1);
}

}
}

public static void main(String[] args) {
int[] a = {3, 5, 2, -4, 8, 11} ;
findTwoSum(a, 7);

}

}

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

``````# This solution supports negative integers and elements duplication (e.g. [3, 5, 2, -4, 8, -4, 11, 11]).
# With `n` = number of elements in arr and `m` = number of indices of a certain complement
# Time complexity = O(n * m)
# Space complexity = O(n * m)
def twoSum(arr, sum):
compl = {}
result = []
for i in range(len(arr)):          # O(n)
n = arr[i]
if sum-n in compl:
for j in compl[sum-n]:     # O(m)
result.append([arr[j], n])
if n in compl:
compl[n].append(i)
else:
compl[n] = [i]
return result``````

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

``````// C++ solution:
vector<pair<int,int>> twoSum(const vector<int> & A,int B) {
unordered_map<int> ump;
vector<pair<int,int>> result;
for(auto e:A) {
if(ump.find(e)!=ump.end()) result.emplace({B-e,e});
else	ump.emplace(B-e);
}
return result;
}``````

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.