Google Interview Question for SDE1s


Country: United States
Interview Type: In-Person




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.

- kieth October 08, 2018 | Flag Reply
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;
    }
}

- Ashok Ramchandani October 08, 2018 | Flag Reply
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;
    }
}

- Ashok Ramchandani October 08, 2018 | Flag Reply
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;
    }

}

- Ashok Ramchandani October 08, 2018 | Flag Reply
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[0] < a[1] < a[2] < 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]))

- lee19856 October 09, 2018 | Flag Reply
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[0]<a[1]<a[2]<w and a[0]+a[1]+a[2]==w:
                        temp.append((a[0], a[1], a[2]))
    print(temp)
    return len(temp)

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

- lee19856 October 09, 2018 | Flag Reply
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.

- adr October 11, 2018 | Flag Reply
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;
}

- Alex October 17, 2018 | Flag Reply
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.

- Anonymous October 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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.

- LionelSeidman1 November 01, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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
}

- inspector_60 November 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

3 sum problem [sorting nlogn + iteration n^2]
--> n^2 time complexity
--> O(1) Space Complexity

- Popeye October 08, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More