Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

I would agree that having it sorted is the proper approach, however by calling

arr.sort()

would require loading the array into memory, which the question states cannot be done. You would have to do an external merge sort using small chunks of the entire array. I think you're missing a critical component of the question...

- andrei.hetman July 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming you are on a 64-bit system where practically any file on your hard drive can fit in your virtual address space, you just do an external sort, mmap the resultant file and then do a usual 3sum with 3 pointers. OS will take care of (un)loading pages to/from real memory.

- adr July 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

"given that the array is too big to fit into memory" - was that asked as a followup question? or right from the start?

- assaf.keret1 July 31, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) For sorting, use extenal sorting
2) For finding touples, use modified solution of the problem:
Given an array A[] and a number x, check for pair in A[] with sum as x - ( Fro GeeksforGeeks)

Where it is not a single array but two arrays. The arrays contain partial data one from the begninig and one from the end of the data. Say for example we have the data as follows
1 3 4 5 6 7 8 9 10 11 14 16 ........
....................................
....................................
99999999994 100000000000
And supposed we want sum of 100000000001 and we can read only four elements. We read first two elements A0 = [1,3] and A1 = [99999999994, 100000000000] into the memory.
intialize l = 0 and r = 1
A0[0] + A1[1] = 1+100000000000 = 100000000001, a hit and do l++, r--
A0[1] + A1[0] = 3 + 99999999994 = 99999999999, a miss and 99999999999<100000000001 so increament l++
But l crossed A0 boundary. So read next check form the begining [4,5] and set l=0
Repeat this till we left with only array
If we left with A0 then set r as length(A0)-1 in this case 1. If we left with A1 then set l as 0. Then use the logic l<r

- dadakhalandhar August 05, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I wanted to make function that find any triplet that sum-up is same as given amount... code does not seem to be quite optimized but it works.

def threesum(nums, amount):
    temp=[]
    distance=0
    d={}
    for i in range(len(nums)):
        left = nums[:i]
        right = nums[i+1:]
        current = nums[i]
        rest = left+right
        ret = twocombo(rest)
        for c in ret:
            a = sorted([current]+c)
            if a not in temp and sum(a) == amount:
                temp.append(a)
    return temp
            
def twocombo(rest):
    temp = []
    for i in range(len(rest)):
        for j in range(i, len(rest)):
            if i != j:
                a = sorted([rest[i]]+[rest[j]])
                if not a in temp:
                    temp.append(a)
    return temp

arr=[-1, 0, 1, 2, -1, -4]
amount = 0
print(threesum(arr, amount))

- lee19856 September 05, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n^2) using single hash table
#1: insert all elems into hash table
#2: for each elem in hash table
---- fix elem i as one of the triplets
---- for all other elements j != i :
----- look for sum - (i + j) in hash table
---- if found, output triplet

- shanthikp September 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming the integers are positive, and that we only need unique triplets. Some de-duping is done in the code, but de-duping on the whole triplet should be done to get really unique triplets.

#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <iostream>

using namespace std;

void Triplets(const vector<uint32_t>& a, uint32_t sum_needed)
{
    unordered_set<uint32_t> sums_of_1;
    unordered_map<uint32_t, unordered_set<uint64_t>> sums_of_2;
    for (uint32_t n : a)
    {
        if (n <= sum_needed)
        {
            auto it = sums_of_2.find(sum_needed - n);
            if (it != sums_of_2.end())
            {
                const unordered_set<uint64_t>& s = it->second;
                for (uint64_t key : s)
                {
                    uint32_t n1 = key >> 32;
                    uint32_t n2 = key;
                    cout << n1 << ", " << n2 << ", " << n << "\n";
                }
            }
            for (uint32_t n1 : sums_of_1)
            {
                uint32_t sum_of_2 = n1 + n;
                if (sum_of_2 <= sum_needed)
                {
                    uint64_t key = n1 < n
                       ? (static_cast<uint64_t>(n1) << 32) | n
                       : (static_cast<uint64_t>(n)  << 32) | n1;
                    sums_of_2[sum_of_2].insert(key);
                }
            }
            sums_of_1.insert(n);
        }
    }
}

int main()
{
    Triplets({7, 2, 8, 5, 9, 1, 3}, 15);
    return 0;
}

- Alex October 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6};
		int sum = 22;
		boolean isTripletAvailable = findPossibleTriplets(arr, sum);
		System.out.println("Triplet is " + (isTripletAvailable ? "available." : "not available."));
	}

	
	
	private static boolean findPossibleTriplets(int[] arr, int sum) {
		int size = arr.length - 1; 
		Set<Integer> set = new HashSet<Integer>();
		for(int i=0; i<size-2;i++) {
			set.clear();
			int sumRequired = sum - arr[i];
			if(set.contains(sumRequired)) return true;
			int second =i+1;
			int last = size;
			while(second < last) {
				int s = arr[second] + arr[last];
				if(s == sumRequired) return true;
				set.add(s);
				second++;
				last--;
			}
		}
		return false;

}

- Anonymous July 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6};
		int sum = 22;
		boolean isTripletAvailable = findPossibleTriplets(arr, sum);
		System.out.println("Triplet is " + (isTripletAvailable ? "available." : "not available."));
	}

	
	
	private static boolean findPossibleTriplets(int[] arr, int sum) {
		int size = arr.length - 1; 
		for(int i=0; i<size-2;i++) {
			int sumRequired = sum - arr[i];
			int second =i+1;
			int last = size;
			while(second < last) {
				int s = arr[second] + arr[last];
				if(s == sumRequired) return true;
				second++;
				last--;
			}
		}
		return false;

}

- Anonymous July 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6};
		int sum = 22;
		boolean isTripletAvailable = findPossibleTriplets(arr, sum);
		System.out.println("Triplet is " + (isTripletAvailable ? "available." : "not available."));
	}

	
	
	private static boolean findPossibleTriplets(int[] arr, int sum) {
		int size = arr.length - 1; 
		for(int i=0; i<size-2;i++) {
			int sumRequired = sum - arr[i];
			int second =i+1;
			int last = size;
			while(second < last) {
				int s = arr[second] + arr[last];
				if(s == sumRequired) return true;
				second++;
				last--;
			}
		}
		return false;

}

- Anonymous July 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

function findTriplet(arr,sum){
var result = false;
arr = arr.sort(function(a,b) { return a - b; });
var next;
var last;
for(var i =0; i< arr.length-2;i++){
next = i+1;
last = arr.length - 1;
while(next < last){
if(arr[i] + arr[next] + arr[last] === sum) {
result = true;
break;
} else if (arr[i] + arr[next] + arr[last] < sum){
next++;
} else {
last--;
}
}
}
return result;
}

- Anonymous July 19, 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