CareerCup

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

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