Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
package helloworld;
import java.util.HashMap;
public class TopTrip{
private static int TOTAL_WEEKS = 4 - 1; // start counting from zero
private int getLongestVacationAtWeek(HashMap<Integer, Integer[]> vacations, int startWeek){
int maxVac = -1;
for(Integer currcity : vacations.keySet()){
int currCityVal = getCityVacationAtWeek(vacations, startWeek, currcity);
if(currCityVal > maxVac){
maxVac = currCityVal;
}
}
return maxVac;
}
private int getCityVacationAtWeek(HashMap<Integer, Integer[]> vacations, int startWeek, int city){
Integer[] cityVacs = vacations.get(city);
return cityVacs[startWeek];
}
private int calculateBestPath(HashMap<Integer, Integer[]> vacations, int startWeek, Integer[] visitedCities){
if(startWeek == TOTAL_WEEKS){
Integer city = new Integer(-1);
Integer longest = getLongestVacationAtWeek(vacations, startWeek);
int maxVac = -1;
for(Integer currcity : vacations.keySet()){
int currCityVal = getCityVacationAtWeek(vacations, startWeek, currcity);
if(currCityVal > maxVac){
maxVac = currCityVal;
city = currcity;
}
}
visitedCities[startWeek] = city;
return longest;
}
int longestTripInTotal = 0;
for(int city : vacations.keySet()){
int cityVacationAtWeek = getCityVacationAtWeek(vacations, startWeek, city);
int longestVacationFromCity = cityVacationAtWeek + calculateBestPath(vacations, startWeek+1,visitedCities);
if(longestVacationFromCity > longestTripInTotal){
visitedCities[startWeek] = city;
longestTripInTotal = longestVacationFromCity;
}
}
return longestTripInTotal;
}
public Integer[] getTopTrip(HashMap<Integer, Integer[]> vacations){
Integer[] result = null;
if(vacations == null){
return result;
}
if(vacations.keySet().size() == 0){
return result;
}
result = new Integer[TOTAL_WEEKS+1];
int longestPath = calculateBestPath(vacations, 0, result);
System.out.println("The longest trip is:" + longestPath);
return result;
}
public static void main(String[] args){
TopTrip tv = new TopTrip();
Integer[] city0 = {1,1,2,11};
Integer[] city1 = {5,1,3,7};
Integer[] city2 = {1,1,4,13};
HashMap<Integer, Integer[]> v = new HashMap<Integer, Integer[]>();
v.put(0,city0);
v.put(1,city1);
v.put(2,city2);
Integer[] path = tv.getTopTrip(v);
for(Integer i : path){
System.out.print(i + "->");
}
}
}
Could you explain the problem a bit more please? Is each vacation in the int[48] array a number between 1-7 (vacation days for that week)?
- Killedsteel February 27, 2017We could simply create a 2D matrix with rows = city, columns = weeks (so 48 columns). Go through each column and pick the max from that column. Now just visit the cities at these max-vacation points for all 48 weeks.