Google Interview Question
Java DevelopersCountry: United States
The idea is to use dynamic programming, solve from the base case (number of ways to get from end to end = 1) and solving backwards column by column to the start.
class Point {
int x, y;
}
int numPaths(Point start, Point end, List<Point> toPass) {
// contains all columns we need to pass through and the corresponding point
Map<Integer, Point> toPassMap = new HashMap<Integer, Point>();
for(Point p : toPass) {
toPassMap.put(p.x, p);
}
// containts num ways to get from a Point to the end
Map<Point, Integer> numWays = new HashMap<Point, Integer>();
numWays.put(end, 1);
// for each column from right to left (backwards)
for(int col = end.x - 1; col >= start.x; col--) {
// cache of previous column numWays
Map<Point, Integer> numWaysTemp = new HashMap<Point, Integer>();
for(Point p : numWays.keyset()) { // p is at col + 1
int x = p.x;
int y = p.y;
int ways = numWays.get(p);
Point prevPoint = new Point(x-1, y-1);
numWaysTemp.put(prevPoint,
numWaysTemp.getOrDefault(prevPoint, 0) + ways);
prevPoint = new Point(x-1, y);
numWaysTemp.put(prevPoint,
numWaysTemp.getOrDefault(prevPoint, 0) + ways);
prevPoint = new Point(x-1, y+1);
numWaysTemp.put(prevPoint,
numWaysTemp.getOrDefault(prevPoint, 0) + ways);
}
// handle case where we had to pass through a point at column col
if(toPassMap.containsKey(col)) {
// make sure numWaysTemp contains that point
Point mustPass = toPassMap.get(col);
if(!numWaysTemp.containsKey(mustPass) {
return 0; // can't complete the traversal
}
numWays = new HashMap<Point, Integer>();
numWays.put(mustPass, numWaysTemp.get(mustPass));
} else { // assign numWaysTemp to numWays
numWays = numWaysTemp;
}
}
return (numWays.containsKey(start) ? numWays.get(start) : 0);
}
@ajay.raj -> where are you getting all these questions?
- onsite February 17, 2018