Google Interview Question
Backend DevelopersTeam: Load Balancer
Country: United States
# 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
Optimized solution using Bucket sort based approach. The integer includes negative integer as well.
- anshuman101 February 22, 2020For 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);
}
}