## Google Interview Question for Software Engineers

• 2

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...

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?

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

Is this in 2D or 1D space?

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

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.

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
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):
pos[i] = x
if aux(i + 1, j, c + 1): return True #found solution
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):
pos[j] = x
if aux(i, j - 1, c+1): return True #found solution
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``````

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...

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 :-)

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

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=init;
Arrays.sort(allPairDist);
int prev=allPairDist;
if(n>1){
result=allPairDist;
}
result[result.length-1]=allPairDist[allPairDist.length-1];
int gs_num=2;   // next gs after result
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();
}
}``````

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

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
- then for all remaining points there is a longest distance between
pos 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
pos = 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 = 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
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):
pos[i] = x
if aux(i + 1, j, c + 1): return True #found solution

# try from left
x = dist[-c]
if verify(x):
pos[j] = x
if aux(i, j-1, c+1): return True #found solution
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]))``````

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=allPairDist``

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

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 is for the second station ( minimum) distance

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

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

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

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

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

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 .

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

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.

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]``````

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.

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;
}else {
List < int[] > newSolution = generateSubset(A[], tuplet[], level + 1, distance + A[i])
if (newSolution != null){
}
}
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)
}``````

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;
}``````

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;
}``````

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;
}else {
List < int[] > newSolution = generateSubset(A[], tuplet[], level + 1, distance + A[i])
if (newSolution != null){
}
}
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)
}``````

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.