## Google Interview Question for Java Developers

• -1
of 1 vote

Country: United States

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

@ajay.raj -> where are you getting all these questions?

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

with no constraints on the pass (e.g.: not using same position more than once), there are infinite number of paths to go from A to B.

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

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.