chamillionaire
BAN USER
Comments (2)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
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(x1, y1);
numWaysTemp.put(prevPoint,
numWaysTemp.getOrDefault(prevPoint, 0) + ways);
prevPoint = new Point(x1, y);
numWaysTemp.put(prevPoint,
numWaysTemp.getOrDefault(prevPoint, 0) + ways);
prevPoint = new Point(x1, 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);
}

chamillionaire
February 19, 2018 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Could you clarify the output of the function? Do you mean that the function should return a list of all the appointments that overlap with at least 1 other appointment? Thanks.
 chamillionaire February 22, 2018