Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
Using DP and dealing with blocked cells
def findWaysBottomUp(height, width, blocked=set()):
d = [0] * height
d[-1] = 1
for col in range(width - 2, -1, -1):
nextD = list(d)
for row in range(height):
top = d[row - 1] if row > 0 and (row, col) not in blocked else 0
bottom = d[row + 1] if row < height - 1 and (row, col) not in blocked else 0
right = d[row] if (row, col) not in blocked else 0
nextD[row] = top + right + bottom
d = nextD
return d[-1]
Using DFS of a graph approach with recursion
package main
import(
"fmt"
)
var (
RIGHT = 0
UPPERRIGHT = 1
LOWERRIGHT = 2
)
func getNewCoordsAfterMove(i,j, dir, r, c int) (bool, int,int) {
if dir == RIGHT {
i = i
j = j + 1
if j < c {
return true, i, j
}
return false, i, j
}
if dir == UPPERRIGHT {
i = i - 1
j = j + 1
if j < c && i >= 0 {
return true, i, j
}
return false, i, j
}
if dir == LOWERRIGHT {
i = i + 1
j = j + 1
if j < c && i < r {
return true, i, j
}
return false, i, j
}
return false, -1, -1
}
func findNoOfpaths(i, j int, row, column int) int{
if i == (row -1) && j == (column -1) {
return 1
}
RPaths := 0
validRMove, newI, newJ := getNewCoordsAfterMove(i,j, RIGHT, row, column)
if validRMove {
RPaths = findNoOfpaths(newI, newJ, row, column)
}
URPaths := 0
validURMove, newI, newJ := getNewCoordsAfterMove(i,j, UPPERRIGHT, row, column)
if validURMove {
URPaths = findNoOfpaths(newI, newJ, row, column)
}
LRPaths := 0
validLMove, newI, newJ := getNewCoordsAfterMove(i,j, LOWERRIGHT, row, column)
if validLMove {
LRPaths = findNoOfpaths(newI, newJ, row, column)
}
return RPaths + URPaths + LRPaths
}
func main() {
fmt.Println("No. Of Paths for 2 X 2", findNoOfpaths(1,0, 2,2))
fmt.Println("No. Of Paths for 2 X 3", findNoOfpaths(1,0, 2,3))
fmt.Println("No. Of Paths for 2 X 4", findNoOfpaths(1,0, 2,4))
fmt.Println("No. Of Paths for 3 X 2", findNoOfpaths(2,0, 3,2))
fmt.Println("No. Of Paths for 3 X 4", findNoOfpaths(2,0, 3,4))
}
public static int getPaths(int length, int width, HashSet<String> blocked) {
String bottomLeft = String.valueOf(width-1) + " 0";
String bottomRight = String.valueOf(width-1) + " " + String.valueOf(length-1);
if ((length == 0) || (width == 0) || (blocked.contains(bottomLeft)) || (blocked.contains(bottomRight))) return 0;
int[] dp = new int[width];
dp[0] = 1;
for (int i = 1; i < length; i++) {
int store = 0;
for (int j = 0; j < width; j++) {
int temp = dp[j];
dp[j] = dp[j] + ((j == width-1) ? 0 : dp[j+1]) + store;
String currLocation = String.valueOf(width-1-j) + " " + String.valueOf(i);
if (blocked.contains(currLocation)) dp[j] = 0;
store = temp;
}
}
return dp[0];
}
public class Pair {
int row;
int col;
Pair(int r, int c) {
row = r;
col = c;
}
}
public static int pathCount(int[][] matrix, int i, int j){
if(i <0 || i >= matrix.length || j <0 || j >= matrix[0].length) return 0;
if(matrix[i][j] >=0) return matrix[i][j];
matrix[i][j] = pathCount(matrix, i, j-1) + pathCount(matrix, i+1, j-1) + pathCount(matrix, i-1, j-1);
return matrix[i][j];
}
O(width*height) time, O(height) space
Goes column by column computing number of paths based on the previous column
int countPaths(int grid_width, int grid_height){
vector<int> last_column;
last_column.resize(grid_height, 0);
vector<int> current_column;
current_column.resize(grid_height, 0);
last_column[last_column.size()-1] = 1;
for(int i=1;i<grid_width;++i){
for(int j=0;j<grid_height;++j){
current_column[j] = last_column[j];
if(j>0){
current_column[j] += last_column[j-1];
}
if(j<grid_height-1){
current_column[j] += last_column[j+1];
}
}
for(int j=0;j<grid_height;++j){
last_column[j] = current_column[j];
}
}
return last_column[grid_height-1];
}
Using DFS to aggregate all the paths:
path.h
#ifndef PATH_H
#define PATH_H
#include <vector>
#include <utility>
#include <queue>
#include <map>
namespace MatrixPathProblem {
typedef std::pair<int, int> Node;
typedef std::vector<std::pair<int, int> > Path;
class Matrix
{
public:
Matrix(const std::vector<std::vector<int> >& matrix);
Matrix(const int** matrix, const size_t length, const size_t width);
inline int length() const { return m_matrix.size(); }
inline int width() const { return m_matrix.size() ? m_matrix.at(0).size() : 0; }
inline bool empty() const { return m_matrix.empty(); }
Node moveRight(const Node& node) const;
Node moveUpperRight(const Node& node) const;
Node moveLowerRight(const Node& node) const;
private:
bool isNodeValid(const Node& node) const;
std::vector<std::vector<int> > m_matrix;
};
class Paths
{
public:
void printPaths(const Node& node) const;
void pushPath(const Node& node,
const Path& path);
void pushPaths(const Node& node,
const Node& fromNode);
bool visited(const Node& node) const;
std::vector<Path> getPaths(const Node& node) const;
private:
std::map<Node,
std::vector<Path> > m_pathsMap;
};
} // namespace MatrixPathProblem
#endif // PATH_H
path.cpp
#include "path.h"
#include <iostream>
namespace MatrixPathProblem {
Matrix::Matrix(const std::vector<std::vector<int> >& matrix)
:m_matrix(matrix)
{
}
Node Matrix::moveRight(const Node& node) const
{
Node newNode(node.first+1, node.second);
if(isNodeValid(newNode))
{
return newNode;
}
return Node(-1, -1);
}
Node Matrix::moveUpperRight(const Node& node) const
{
Node newNode(node.first+1, node.second-1);
if(isNodeValid(newNode))
{
return newNode;
}
return Node(-1, -1);
}
Node Matrix::moveLowerRight(const Node& node) const
{
Node newNode(node.first+1, node.second+1);
if(isNodeValid(newNode))
{
return newNode;
}
return Node(-1, -1);
}
bool Matrix::isNodeValid(const Node& node) const
{
if(node.first < 0 || node.first >= length())
return false;
if(node.second <0 || node.second >= width())
return false;
return true;
}
void Paths::printPaths(const Node& node) const
{
std::map<Node, std::vector<Path> >::const_iterator itr = m_pathsMap.find(node);
if(itr == m_pathsMap.end())
{
std::cout << "No path available" << std::endl;
}
for(std::vector<Path>::const_iterator pitr = itr->second.begin();
pitr != itr->second.end();
++pitr)
{
for(Path::const_iterator vitr = pitr->begin();
vitr != pitr->end();
++vitr)
{
std::cout << "(" << vitr->first << "," << vitr->second << ")->";
}
std::cout << "(" << node.first << "," << node.second << ")" << std::endl;
}
}
void Paths::pushPath(const Node& node, const Path& path)
{
auto& paths = m_pathsMap[node];
paths.push_back(path);
}
void Paths::pushPaths(const Node& node, const Node& fromNode)
{
auto pathsItr = m_pathsMap.find(fromNode);
if(pathsItr == m_pathsMap.end())
{
// No path available at the moment
// so we will just push the path including
// fromNode only
Path createdPath;
createdPath.push_back(fromNode);
pushPath(node, createdPath);
return;
}
for(std::vector<Path>::const_iterator pitr = pathsItr->second.begin();
pitr != pathsItr->second.end();
++pitr)
{
Path createdPath(*pitr);
createdPath.push_back(fromNode);
pushPath(node, createdPath);
}
}
bool Paths::visited(const Node& node) const
{
if (m_pathsMap.find(node) != m_pathsMap.end())
return true;
return false;
}
std::vector<Path> Paths::getPaths(const Node& node) const
{
auto pitr = m_pathsMap.find(node);
if(pitr == m_pathsMap.end())
{
return std::vector<Path>();
}
return pitr->second;
}
void findPath(const Matrix& matrix)
{
Paths paths;
std::queue<Node> queue;
Node startNode(0,0);
Node endNode(matrix.length()-1, matrix.width()-1);
if(matrix.empty())
{
return;
}
// Push the first node
queue.push(startNode);
while(!queue.empty())
{
auto node = queue.front();
queue.pop();
auto rightNode = matrix.moveRight(node);
auto upperRightNode = matrix.moveUpperRight(node);
auto lowerRightNode = matrix.moveLowerRight(node);
if(rightNode.first >= 0)
{
if(!paths.visited(rightNode))
{
queue.push(rightNode);
}
// Add all available paths to the right node
paths.pushPaths(rightNode, node);
}
if(upperRightNode.first >= 0)
{
if(!paths.visited(upperRightNode))
{
queue.push(upperRightNode);
}
// Add all available paths to the upperRightNode
paths.pushPaths(upperRightNode, node);
}
if(lowerRightNode.first >= 0)
{
if(!paths.visited(lowerRightNode))
{
queue.push(lowerRightNode);
}
// Add all available paths to the lowerRightNode
paths.pushPaths(lowerRightNode, node);
}
}
paths.printPaths(endNode);
}
} // namespace MatrixPathProblem
int main()
{
std::vector<std::vector<int> > matrix({
{1, 0, 0 ,0},
{0, 1, 1, 0},
{1, 1, 1, 1},
{1, 1, 1, 1},
{1, 1, 1, 1}
});
MatrixPathProblem::Matrix pathMatrix(matrix);
MatrixPathProblem::findPath(pathMatrix);
}
Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONE-TO-ONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
- aonecoding March 10, 2018