Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

@tryingtolearn: correct always at least two solutions or no solution. Imagine the mirrored solution, it has the same distances...

- Chris August 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

1. Is the distance, absolute value (always positive) or can we use the sign to tell 2nd it's left or right of first
2. Are distances integers, and can we assume ab+bc=ac without any error?

- Chris August 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Is this in 2D or 1D space?

- Anonymous August 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I am confused, the question mentions the distances are given in random order, lets say
scenario 1) a-0, b-10, c-30
ab =10, ac = 30, bc =20,
scenario 2) a-0, b-20, c-30
ab =20, ac = 30, bc =10,
but 10, 20,30 are common in both scenarios, how can we find correct solution ? can some one help me understand this? thank you

- tryingtolearn August 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Chrisk thank you so much for the clarification , I also appreciate your clear explanations for questions on this site, most of the time, it helps me understand the posted question and understand an approach to solve the question. thanks again.

- tryingtolearn August 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Vijay.B
thanks, that's correct, I didn't check for already used distances. This should work now (code is ugly)

def zero_if_none(a):
    return 0 if a is None else a

def find_gas_station_pos(dist):            
    def aux(i, j, c):        
        # check if gas station at pos x would work
        def verify(x):
            for r in [range(0, i), range(j + 1, station_count)]:
                for t in r:
                    if zero_if_none(distances.get(abs(x - pos[t]))) <= 0:
                        return False
            return True
        
        # add / remove distances based on delta
        def add(x, delta):
            for r in [range(0, i), range(j + 1, station_count)]:
                for t in r:
                    distances[abs(x - pos[t])] += delta

        # base case
        if i > j: return True
        
        # try from right
        x = pos[-1] - dist[-c]
        if zero_if_none(distances.get(x)) > 0:
            if verify(x):
                add(x, -1)
                pos[i] = x
                if aux(i + 1, j, c + 1): return True #found solution
                add(x, 1) #backtrack
        else:
            if aux(i,j,c+1): return True

        # try from left
        x = dist[-c]
        if zero_if_none(distances.get(x)) > 0:
            if verify(x):
                add(x, -1)
                pos[j] = x
                if aux(i, j - 1, c+1): return True #found solution
                add(x, 1) #backtrack
            return False #backtrack
        else:
            return(aux,i,j,c+1)
        
    station_count = int((sqrt(8*len(dist)+1)+1)/2) #len(dist)=(station_count^2-station_count)/2
    pos = [0 for i in range(station_count)]
    distances = defaultdict(int)    
    dist.sort()
    for i in range(0, len(dist)-1):
        distances[dist[i]] += 1

    if station_count <= 1: return pos
    pos[-1] = dist[-1]
    if aux(1, station_count - 2, 2):
        return pos
    else:
        return [] # no solution found

- Chris August 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

@qafqunam2001 return(aux,i,j,c+1) is a typo, it should be return aux(i,j,c+1) that should fix it...

- Chris August 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

@chow: in all cases, if once is available the mirrored one at least is a solution too. As mentioned the solution is improvable :-)

- Chris August 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK
1. Yes the distances are absolute value(always positive)
2. Yes all the distances are integers, and ab + bc = ac

- logan9 August 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class MyClass
{
    // The idea is to mark the first station(gs) as 0
    // last as the max element from the distance array(dist from first to last)
    // Then any duplicate distances are the internal distances, so we remove them 
    // and all the left over places with -1
    // Next we traverse through the distance array
    //      if the distance is at even index that means it's the distance between
    //      consecutive stations, so we add the current distance with prev
    //      else it's the distance from first to prev station
    
    
    public static int[] actualDistance(int n, int[] allPairDist){
        if(allPairDist.length<=1){
            return allPairDist;
        }
        int init=0;
        int result[]=new int[n];
        result[0]=init;
        Arrays.sort(allPairDist);
        int prev=allPairDist[0];
        if(n>1){
            result[1]=allPairDist[0];
        }
        result[result.length-1]=allPairDist[allPairDist.length-1];
        int gs_num=2;   // next gs after result[1]
        removeDuplicates(allPairDist);
        for(int i=0;i<allPairDist.length;++i){
            if(gs_num==n-1)
                break;
            if(allPairDist[i]==-1)
                break;
            if(i%2==1){
                result[gs_num++]=allPairDist[i]+prev;
            }else{
                prev=allPairDist[i];
            }
        }
        return result;
    }
// Main Method
	public static void main (String[] args) throws java.lang.Exception
	{
        int[] dist=new int[]{10,20,70,80,30,20,100,70,50,90}; // Random distances
        // If you want you can also check if size is equal to 5c2
	    int result[] = actualDistance(5,dist);

//        int[] dist=new int[]{10,10}; // Random distances
//	    int result[] = actualDistance(2,dist);

//        int[] dist=new int[]{10,10,20,10}; // Random distances
//	    int result[] = actualDistance(3,dist);
	    for(int i : result){
	        System.out.println(i+" ");
	    }
	}
//  Utility function
	public static void removeDuplicates(int[] dist){
	    int unq_cnt=0;
	    for(int i=1;i<dist.length;++i){
	        if(dist[unq_cnt]!=dist[i]){
	            dist[++unq_cnt]=dist[i];
	        }
	    }
	    for(int i=unq_cnt+1;i<dist.length;++i){
	        dist[i]=-1;
	    }
	    for(int i : dist){
	        System.out.print(i+" ");
	    }
	    System.out.println();
	}
}

- Anwar August 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The example can be solved in this way as well:
A-0
B-20
C-70
D-90
E-100

- Usman August 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

looks like a tough one...

Clearification / Definition:
- the positions of the gas stations are one dimensional (X-Position),
further denoted as pos[i], where i is the gas station, 0 <= i < n-1.
I assume pos[i-1] < pos[i], which will later result from the solution
- the distances given dist[j] are random, the only thing known is all
distances between all pairs are in this vector and the distances are
integers with no error
- dist[i] != 0 for any i

Observations:
- the longest distance is pos[n-1] - pos[0]
- then for all remaining points there is a longest distance between
pos[0] or pos[n-1]

Algorithm (with backtracking)
- sort distance array
- put all distances into a hashtable with distance as key and #times
of occurence as value
- start with:
pos[0] = 0
pos[n-1] = longest distance
i = 1, j = n-2, c = 2
- recursion(i, j, c):
if i > j: return true
d = c-longest distance
assume pos[i] = d, verify if other distances are available, if yes,
pos[1] = d, recurse on (i+1, j, c+1) (if recursion returns true, return true,
if false, try 2nd option
if no, assume pos[i] = pos[n-1] - d, verify, if ditances to defined
gas stations exists, if yes, recurse, if not return False

runtime-analyzis: that's tough, fast explanation O(2^n * n), because
at each recursion level, there are two choices and verification of
a choice takes 2n/2 average. How ever, one can't construct
a sample that will explore as many paths.

i assume a far more elegant solution exists

from math import sqrt
from collections import defaultdict 

def find_gas_station_pos(dist):            
    def aux(i, j, c):        
        # check if gas station at pos x would work
        def verify(x):
            for r in [range(0, i), range(j + 1, station_count)]:
                for t in r:
                    count = distances.get(abs(x - pos[t]))
                    if count is None or count <= 0:
                        return False
            return True
        
        # add / remove distances based on delta
        def add(x, delta):
            for r in [range(0, i), range(j + 1, station_count)]:
                for t in r:
                    distances[abs(x - pos[t])] += delta

        # base case
        if i > j: return True
        
        # try from right
        x = pos[-1] - dist[-c]
        if verify(x):
            add(x, -1)
            pos[i] = x
            if aux(i + 1, j, c + 1): return True #found solution
            add(x, 1) #backtrack

        # try from left
        x = dist[-c]
        if verify(x):
            add(x, -1)
            pos[j] = x
            if aux(i, j-1, c+1): return True #found solution
            add(dist[c], 1) #backtrack
        return False #backtrack
        
    station_count = int((sqrt(8*len(dist)+1)+1)/2) #len(dist)=(station_count^2-station_count)/2
    pos = [0 for i in range(station_count)]
    distances = defaultdict(int)    
    dist.sort()
    for i in range(0, len(dist)-1):
        distances[dist[i]] += 1

    if station_count <= 1: return pos
    pos[-1] = dist[-1]
    if aux(1, station_count - 2, 2):
        return pos
    else:
        return [] # no solution found

print(find_gas_station_pos([10, 20, 70, 80, 30, 20, 100, 70, 50, 90]))

- Chris August 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Anwar: doesn't seem to work in all cases.
input [1, 9, 10, 10, 11, 20], returns [0, 1, 10, 20] which would create distances of [1, 9, 10, 10, 19, 20] (which is similar but not the same)
[0, 10, 11, 20] or [0, 9, 10, 20] would be valid solutions

I checked 'cause I didn't really understand the removal of doublicates and

result[1]=allPairDist[0]

can't work because the first isn't nececcarily nearest point (as the example above shows, distance 1 is between 10-11 somewhere in the middle

anyway I'd like to explore your idea more, it seems interesting, maybe you could explain the ideas

- Chris August 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK you input is invalid, you can't have two stations at one place.... result[1] is for the second station ( minimum) distance

- Anwar August 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm sorry, I'm out of mind...

- Anwar August 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Anwar: never mind, this happens ;-)
@tryingtolearn: thanks, appreciate it

- Chris August 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK, solution doesn't work for below input.

10,10,20,30,70,80,100,190,200,260,270,270,280,290,300

Out put should be
0,20,30,100,290,300

- Vijay.B August 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Reason is , Phase "try from right", we are adding first element ie difference 10 without further checks .

- Vijay.B August 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi @ChrisK, I tried this input: 10,10,20,30,70,80,100,190,200,260,270,270,280,290,300,360,340,330,260,70,60, which is the result of adding a gas station at position 360 to the input proposed by @Chow, the expected result would be: 0, 20, 30, 100, 290, 300, 360, but the result is 0, 20, 30, 0, 290, 300, 360

- qafqunam2001 August 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have still not understood the logic to solve this question, can someone give a clear explaination to this.

- Anonymous August 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK - In some cases has more than one solution, below are two cases.

case1:
Distances: 10, 20, 30, 70, 80, 100, 190, 200, 260, 270, 280, 290, 300 

[0, 10, 200, 270, 280, 300]
[0, 20,  30,  100,  290, 300]

case2:

'10,10,10,10,20,20,20,20,20,20,30,30,30,30,30,30,40,40,40,40,50,50,50,50,50,50,50,50,60,60,70,70,70,70,70,80,80,80,80,90,90,90,100,100,100,100,100,100,100,110,110,120,120,120,130,130,130,130,140,140,140,150,150,150,150,160,160,170,170,170,180,180,180,180,200,200,200,200,210,210,220,220,230,230,230,240,250,250,250,260,270,270,280,280,290,300,300,300,310,310,320,320,330,340,350'



[0, 20, 30,  40, 50, 70, 100, 120, 140, 170, 200, 250, 300, 340, 350]
[0, 10, 50, 100, 150, 180, 210, 230, 250, 280, 300, 310, 320, 330, 350]

- Vijay.B August 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK - Yes, points are always mirrored and two(or no) solutions exists for each of distances.

Thanks for your inputs.

- Vijay.B August 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# The solution to this problem is:
# Sort all the distances
# Max distance = d[ d.length -1]
# numStations = d.length + 1 (including the zero position) / 2
#
# Find in all subsets of length = numStations inside the distances (removing the max) that = maximum distances. THESE ARE THE SOLUTIONS.
#
# How to do it is harder. We need to try all the the possibles subsets of length numStations, we dont want all, or will be brute force. In order to do it generate all the possible subsets, we can create a tree. If the level = numStations and the sum = max distance then is a solution. If sum > maxDistance, we stop.

List < int[] > generateSubset(A[], tuplet[], level, distance, numStations, maxDistance){
    List < int[] > solutions;
    for (int i = level, i < a.length(), i++ ) {
        if (level > numStations) {
            return null;
        }

        if( distance + A[i] > maxDistance){
            return null
        }

        tuplet[i] = 1;
        if(distance + A[i]  == maxDistance && level == numStations){
            List < int[] > solution = tuplet;
            solutions.add(newSolution);
        }else {
            List < int[] > newSolution = generateSubset(A[], tuplet[], level + 1, distance + A[i])
            if (newSolution != null){
                solutions.add(newSolution);
            }
        }
        tuplet[i] = 0;
    }

    return solution;
}

List < int[] >  getSolutions (A[]) {
    int maxDistance = A[A.length - 1]
    int numStations = (A.length + 1) / 2
    a.remove(a.length -1 )
    sort(A);
    int [] tuplet = new int[A.length - 1]; // Not includes the last (max) distance
    for (int i = 0; i < tuplet.length, i++) { tuplut[i] = 0}
    return generateSubset(A[], tuplet, 0, 0, numStations,maxDistance)
}

- David Sanchez August 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My idea is to find the max distance, which is sum of the distance hops in the correct station coordinates. Using dynamic programming, I get a combination of hops, and check if the combination satisfies the rest of the distances. To optimize, memoization can be used (not implemented in the code below.

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

using namespace std;

bool CheckComb(unordered_map<int, int> d, vector<int> const &comb)
{
	if (comb.size() < 2) {
		return false;
	}
	for (int i = 0; i < comb.size(); ++i) {
		int sum = 0;
		for (int j = i; j < comb.size(); ++j) {
			sum += comb[j];
			if (j > i) {
				if (d.find(sum) == d.end()) {
					return false;
				}
				if (--d[sum] == 0) {
					d.erase(sum);
				}
			}
		}
	}
	return d.empty();
}

void Combine(unordered_map<int, int> &d, int total, vector<int> &comb, vector<vector<int>> &out)
{
	if (total < 0) {
		return;
	}
	if (total == 0) {
		if (CheckComb(d, comb)) {
			out.push_back(comb);
		}
		return;
	}

	vector<int> keys;
	for (auto el : d) {
		keys.push_back(el.first);
	}
	for (int k : keys) {
		if (--d[k] == 0) {
			d.erase(k);
		}
		comb.push_back(k);
		Combine(d, total - k, comb, out);
		comb.pop_back();
		++d[k];
	}
}

vector<vector<int>> StationPositions(vector<int> const &d)
{
	int max_idx = 0;
	for (int i = 1; i < d.size(); ++i) {
		if (d[i] > d[max_idx]) {
			max_idx = i;
		}
	}
	int total = d[max_idx];
	unordered_map<int, int> d_map;
	for (int i = 0; i < d.size(); ++i) {
		++d_map[d[i]];
	}

	vector<int> comb;
	vector<vector<int>> out;
	Combine(d_map, total, comb, out);
	return out;
}

int main(int argvc, char const **argv)
{

	vector<int> a = {10, 20, 70, 80, 30, 20, 100, 70, 50, 90};
	vector<vector<int>> out = StationPositions(a);
	for (auto comb : out) {
		int pos = 0;
		cout << pos << ", ";
		for (int d : comb) {
			cout << (pos += d) << ", ";
		}
		cout << "\n";
	}
    return 0;
}

- Alex August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		int[] arr = { 10, 20, 70, 80, 30, 20, 100, 70, 50, 90 };
		int n = 5;

		int[] taken = new int[arr.length];
		int[] pos = new int[n];
		pos(arr, 1, taken, pos, n - 1, false);
	}

	public static boolean pos(int[] arr, int index, int[] taken, int[] pos, int n, boolean found) {

		if (n == 0) {
			found = validate(arr, taken, pos, 1, false);
			if (found) {
				for (int i = 0; i < pos.length; i++)
					System.out.print(pos[i] + " ");
			}
			for (int i = 0; i < taken.length; i++)
				if (taken[i] == 2)
					taken[i] = 0;
			return found;
		}

		int k = taken.length;

		for (int i = 0; i < k; i++) {
			if (taken[i] == 0) {
				pos[index] = arr[i];
				taken[i] = 1;
				if (!found)
					found = pos(arr, index + 1, taken, pos, n - 1, found);
				pos[index] = 0;
				taken[i] = 0;
			}
		}
		return found;
	}

	public static boolean validate(int[] arr, int[] taken, int[] pos, int index, boolean ret) {

		int n = pos.length;
		if(index >= n-1)
			return true;
		for (int i = index; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				boolean found = false;
				for (int k = 0; k < taken.length; k++) {
					if (taken[k] == 0 && Math.abs(pos[i] - pos[j]) == arr[k]) {
						taken[k] = 2;
						found = true;
						break;
					}
				}
				if (!found && !ret)
					return false;
			}
			if(!ret)
				ret = validate(arr, taken, pos, index + 1, ret);
		}
		return ret;
	}

- sudip.innovates November 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

# The solution to this problem is:
# Sort all the distances
# Max distance = d[ d.length -1]
# numStations = d.length + 1 (including the zero position) / 2
#
# Find in all subsets of length = numStations inside the distances (removing the max) that = maximum distances. THESE ARE THE SOLUTIONS.
#
# How to do it is harder. We need to try all the the possibles subsets of length numStations, we dont want all, or will be brute force. In order to do it generate all the possible subsets, we can create a tree. If the level = numStations and the sum = max distance then is a solution. If sum > maxDistance, we stop.
# Sorry for pseudo code

List < int[] > generateSubset(A[], tuplet[], level, distance, numStations, maxDistance){
    List < int[] > solutions;
    for (int i = level, i < a.length(), i++ ) {
        if (level > numStations) {
            return null;
        }

        if( distance + A[i] > maxDistance){
            return null
        }

        tuplet[i] = 1;
        if(distance + A[i]  == maxDistance && level == numStations){
            List < int[] > solution = tuplet;
            solutions.add(newSolution);
        }else {
            List < int[] > newSolution = generateSubset(A[], tuplet[], level + 1, distance + A[i])
            if (newSolution != null){
                solutions.add(newSolution);
            }
        }
        tuplet[i] = 0;
    }

    return solution;
}

List < int[] >  getSolutions (A[]) {
    int maxDistance = A[A.length - 1]
    int numStations = (A.length + 1) / 2
    a.remove(a.length -1 )
    sort(A);
    int [] tuplet = new int[A.length - 1]; // Not includes the last (max) distance
    for (int i = 0; i < tuplet.length, i++) { tuplut[i] = 0}
    return generateSubset(A[], tuplet, 0, 0, numStations,maxDistance)
}

- David Sanchez August 22, 2017 | 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