## Google Interview Question for SDE1s

• 1
of 1 vote

Country: United States
Interview Type: In-Person

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

This should be possible in O(n^2) time and space complexity.

First, you can rewrite the equation as x + y = w - z. Then create a nested loop where you calculate every possible value of x + y (ensuring the y-index always exceeds the x-index), and insert those values into a dictionary with the xy sum as the key. The dictionary value in this case would be an array containing the index of y. If you get xy sums that match existing keys, just add the new y index of those sums to the array returned by the dictionary.

Next, create an integer counter, and then create a second nested loop over the array, in which you'll compute every possible value of w - z (ensuring the w-index always exceeds the z-index). For each computed value, check the dictionary for a match. If you get one, loop over the returned array, and for each value that is less than your current z-index, increment the counter by 1.

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

It seems to me that time complexity of O(n^2) can be achieved by using hash map with keys as values of the array and values as indexes of the array (i.e. map[arr[i]] = i note that the array's elements are unique )
This map let us find z in O(1) by: z = W-arr[x]-arr[y], therefore we need to check: for each x and y in the array such that x<y if there is a z such that x+y+z = w.

code is Swift:

``````func comb(arr:[Int],W: Int) -> [(Int,Int,Int)]? {
guard arr.count >= 3 else {
return nil
}
var ia:[Int:Int] = [Int:Int]()
var ret = [(Int,Int,Int)]()
for i in 0..<arr.count {
ia[arr[i]] = i
}

for x in 0..<arr.count-3 {
for y in x+1..<arr.count-1 {
let miss = W-arr[x]-arr[y]
if let z = ia[miss] {
if arr[x] + arr[y] + arr[z] == W && z > y {
ret.append((arr[x],arr[y],arr[z]))
}
}
}
}
return ret
}``````

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

sorting might not help, there is a condition that idx(x)<idx(y).. as well.

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

``````public class SumArray1 {

public int numOfSum(Integer[] arr) {
if (null == arr || arr.length < 4) return -1;

int count = 0;
for (int x = 0; x < (arr.length - 3); x++) {
for (int y = x+1; y < (arr.length - 2); y++) {
for (int z = y+1; z < (arr.length - 1); z++) {
int tmpSum = arr[x] + arr[y] + arr[z];
// We can store the elements from w till end of the array into another array
// and then do the binary search in that array such that we get tmpSum
// This can reduce the complexity from O(n4) to O(n3 logn)
for (int w = z+1; w < arr.length; w++) {
if (tmpSum == arr[w]) {
count++;
break;
}
}
}
}
}

return count;
}
}``````

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

``````public class SumArray1 {

public int numOfSum(Integer[] arr) {
if (null == arr || arr.length < 4) return -1;

int count = 0;
for (int x = 0; x < (arr.length - 3); x++) {
for (int y = x+1; y < (arr.length - 2); y++) {
for (int z = y+1; z < (arr.length - 1); z++) {
int tmpSum = arr[x] + arr[y] + arr[z];
// We can store the elements from w till end of the array into another array
// and then do the binary search in that array such that we get tmpSum
// This can reduce the complexity from O(n4) to O(n3 logn)
for (int w = z+1; w < arr.length; w++) {
if (tmpSum == arr[w]) {
count++;
break;
}
}
}
}
}

return count;
}
}``````

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

``````public class SumArray1 {

public int numOfSum(Integer[] arr) {
if (null == arr || arr.length < 4) return -1;

int count = 0;
for (int x = 0; x < (arr.length - 3); x++) {
for (int y = x+1; y < (arr.length - 2); y++) {
for (int z = y+1; z < (arr.length - 1); z++) {
int tmpSum = arr[x] + arr[y] + arr[z];
// We can store the elements from w till end of the array into another array
// and then do the binary search in that array such that we get tmpSum
// This can reduce the complexity from O(n4) to O(n3 logn)
for (int w = z+1; w < arr.length; w++) {
if (tmpSum == arr[w]) {
count++;
break;
}
}
}
}
}

return count;
}``````

}

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

Tried w/ Python....

``````def find(nums):
temp=[]
for i in range(len(nums)):
current = nums[i]
right = nums[i+1:]
for c in helper(right):
a = sorted([current] + c)
for amount in nums:
if a not in temp and sum(a) == amount and a < a < a < amount:
temp.append(a)
print(temp)
return len(temp)

def helper(a):
temp = []
for i in range(len(a)-1):
for j in range(i+1, len(a)):
if not [a[i], a[j]] in temp:
temp.append([a[i], a[j]])
return temp

""" all unique num, not sorted input, negative num included """
print("Solution-1: ",find([-1,0,1,2,3,-2,5]))
print("Solution-1: ",find([10,2,3,7,8,6,4,5,9,1]))``````

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

another one i tried...

``````def find2(x):
temp = []
for i in range(len(x)-2):
for j in range(i+1, len(x)-1):
for k in range(j+1, len(x)):
a = sorted([x[i], x[j], x[k]])
for w in x:
if a<a<a<w and a+a+a==w:
temp.append((a, a, a))
print(temp)
return len(temp)

print("Solution-2: ",find2([10,2,3,7,8,6,4,5,9,1]))``````

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

We are matching a 4-place predicate so the bruteforce is O(n^4). If anything, this resembles a 4-sum problem, definetely not a 3-sum as some have claimed.

The important thing to note from the description is that 3 elements matching the value of the 4th element must lie to the left of the 4th element. This lends itself to this straightforward approach:

``````def count(arr):
ans = 0
sums = defaultdict(int)
for i,x in enumerate(arr[3:], 3):
c = arr[i-1]
for j,a in enumerate(arr[:i-2]):
for b in arr[j+1:i-1]:
sums[a+b+c] += 1
ans += sums[x]
return ans``````

O(N^3) runtime.

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

You did not check whether w is in the array or not. It can be done in O(N^3) but that would require hashing.

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

O(n^3) time.

``````#include <unordered_set>
#include <vector>
#include <iostream>

using namespace std;

int64_t Count(const vector<int>& a)
{
vector<unordered_set<int>> right;
right.resize(a.size());
for (int i = 2; i < a.size(); ++i)
{
for (int j = i + 1; j < a.size(); ++j)
{
right[i].insert(a[j]);
}
}

int64_t count = 0;
for (int i = 0; i < a.size(); ++i)
{
int sum1 = a[i];
for (int j = i + 1; j < a.size(); ++j)
{
int sum2 = sum1 + a[j];
for (int k = j + 1; k < a.size(); ++k)
{
int sum3 = sum2 + a[k];
const unordered_set<int>& r = right[k];
if (r.find(sum3) != r.end())
{
++count;
}
}
}
}

return count;
}

int main()
{
cout << Count({4, 1, 3, 8, 7, 12}) << "\n";
return 0;
}``````

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

Brute force O(n^4), using a hash with a triple for loop O(n^3), but there is an O(n^2 log n) too.
Generate all sums x[j] - x[i] with i<j, takes O(n^2), put it in a hashmap with key as the sum, value a list where you append 'i'. This list is sorted, so finding how many values of 'i' are bigger than some index 'b' takes logN. Generate, all sums x[a]+x[b] with a<b, look up the sum in the hashmap, binary search to find how many of those sums are after index b.

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

We need to find solution in nlogn

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.