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

- aonecoding March 10, 2018 | Flag Reply
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]

- pipedpiper March 10, 2018 | Flag Reply
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))
}

- saurabh.ag82 March 29, 2018 | Flag Reply
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;
        }
    }

- Aim_Google March 29, 2018 | Flag Reply
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);
}

- Max May 17, 2018 | Flag Reply


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