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

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More