## Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

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!

``````public class MatrixPuzzle {

int column;
int row;

public MatrixPuzzle(int length, int width) {
this.column = length;
this.row = width;
}

//The dp formula will be M[i,j] = M[i - 1, j - 1] + M[i - 1, j] + M[i - 1, j + 1]
//Because one could only land on current cell from the 3 cells in the upper-left, left and lower-left.
//To make the space consumption 1d, cache the numbers in one column of the matrix at a time.
//Follow-up 2: Just reset path-counts for blocked cells to 0
public int numberOfPaths() {
int[] paths = new int[row];
paths[row - 1] = 1; //start from bottom-left corner
for(int col = 1; col < column; col++) {
int upper_left_value = 0;
for(int r = 0; r < row; r++) {
int left_value = paths[r];
paths[r] += upper_left_value + (r == row - 1 ? 0 : paths[r + 1]);
upper_left_value = left_value;
}
}

return paths[row - 1]; //exit from bottom-right
}
}``````

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

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]``````

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

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

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

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

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

``````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];

}``````

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

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];
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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.