Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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
@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
/* 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();
}
}
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]))
@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
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
@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]
# 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)
}
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;
}
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;
}
# 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)
}
@tryingtolearn: correct always at least two solutions or no solution. Imagine the mirrored solution, it has the same distances...
- Chris August 09, 2017