Bloomberg LP Interview Question for Financial Software Developers


Country: United States
Interview Type: Phone Interview




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

Since all directions are possible and you have exclusionary positions, a search approach would be necessary. Backtracking is probably easiest.

public static List<List<Move>> getValidPaths(int[][] m){
    if(m == null){
        throw new NullPointerException();
    }
    if(m.length == 0 || m[0].length == 0){
        throw new IllegalArgumentException();
    }

    Worker worker = new Worker(m);
    worker.execute();
    return worker.results();
}

public static class Move{
    int x, y;
}

public static class Worker{
    int[][] m;
    boolean[][] visited;
    ArrayList<Move> currentPos;
    ArrayList<ArrayList<Move>> results;

    private Worker(int[][] m){
        this.m = m;
        this.visited = new boolean[this.m.length][this.m[0].length];
        this.currentPos = new ArrayList<Move>();
        this.results = new ArrayList<ArrayList<Move>>();
    }

    private void execute(){
        executeRecur(0, 0);
    }

    private void executeRecur(int x, int y){
        //disregard invalid positions, illegal moves, and places already visited
        if(x < 0 || x > this.m.length || y < 0 || y > this.m[0].length || this.m[x][y] == 0 || this.visited[x][y]){
            return;
        }

        //set visited and add to path
        this.visited[x][y] = true;
        Move move = new Move(x, y);
        this.currentPos.add(move);
        //if this is a solution, record it
        if(x == this.m.length && y == this.m[0].length){
            this.results.add(this.currentPos.clone());
        }
        //otherwise keep searching
        else{
            for(int newX = x -1; newX <= x + 1; newX ++){
                for(int newY = y - 1; new Y <= y + 1; newY++){
                    executeRecur(newX, newY);
                }
            }
        }
        //remove this position from the path
        this.currentPos.remove(currentPos.size() -1);
        this.visited[x][y] = false;
    }

    private ArrayList<ArrayList<Move>> results(){
        return this.results;
    }
}

- zortlord July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

And now with formatting...

Since all directions are possible and you have exclusionary positions, a search approach would be necessary. Backtracking is probably easiest.

public static List<List<Move>> getValidPaths(int[][] m){
    if(m == null){
        throw new NullPointerException();
    }
    if(m.length == 0 || m[0].length == 0){
        throw new IllegalArgumentException();
    }

    Worker worker = new Worker(m);
    worker.execute();
    return worker.results();
}

public static class Move{
    int x, y;
}

public static class Worker{
    int[][] m;
    boolean[][] visited;
    ArrayList<Move> currentPos;
    ArrayList<ArrayList<Move>> results;

    private Worker(int[][] m){
        this.m = m;
        this.visited = new boolean[this.m.length][this.m[0].length];
        this.currentPos = new ArrayList<Move>();
        this.results = new ArrayList<ArrayList<Move>>();
    }

    private void execute(){
        executeRecur(0, 0);
    }

    private void executeRecur(int x, int y){
        //disregard invalid positions, illegal moves, and places already visited
        if(x < 0 || x > this.m.length || y < 0 || y > this.m[0].length || this.m[x][y] == 0 || this.visited[x][y]){
            return;
        }

        //set visited and add to path
        this.visited[x][y] = true;
        Move move = new Move(x, y);
        this.currentPos.add(move);
        //if this is a solution, record it
        if(x == this.m.length && y == this.m[0].length){
            this.results.add(this.currentPos.clone());
        }
        //otherwise keep searching
        else{
            for(int newX = x -1; newX <= x + 1; newX ++){
                for(int newY = y - 1; new Y <= y + 1; newY++){
                    executeRecur(newX, newY);
                }
            }
        }
        //remove this position from the path
        this.currentPos.remove(currentPos.size() -1);
        this.visited[x][y] = false;
    }

    private ArrayList<ArrayList<Move>> results(){
        return this.results;
    }
}

- zortlord July 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry, my bad. The actual question was just to count the total paths available. And the moves are restricted to 3 directions only: right, down and right-down.

- rv July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include <vector>
#include <iostream>

using namespace std;

void findNeigh(int a[][3], pair<int,int> &S, vector < pair<int, int> > &Neigh, int N, int M ){
	if(S.first + 1 < N )if(a[S.first+1][S.second] == 1) Neigh.push_back(make_pair(S.first+1,S.second));
	if(S.first + 1 < N  && S.second + 1 < M)if(a[S.first+1][S.second+1] == 1) Neigh.push_back(make_pair(S.first+1,S.second+1));
	if(S.second + 1 < M )if(a[S.first][S.second+1] == 1) Neigh.push_back(make_pair(S.first,S.second+1));
}

int countPaths(int a[][3],pair<int,int> &S, pair<int,int> &D, int N, int M){
	if(S.first==N-1 && S.second == M-1 ) return 1;

	vector < pair<int, int> > Neigh;
	
	findNeigh(a,S,Neigh, N, M);
	
	if(Neigh.size()==1 ){
		pair<int, int> S1 = Neigh.back();
		return(countPaths(a,S1,D,N,M));
	}else if(Neigh.size() ==2){
		pair<int, int> S1 = Neigh[0], S2=Neigh[1];
		return(countPaths(a,S1,D,N,M) + countPaths(a,S2,D,N,M) );
	}else if(Neigh.size() ==3){
		pair<int, int> S1 = Neigh[0], S2=Neigh[1], S3=Neigh[2];
		return(countPaths(a,S1,D,N,M) + countPaths(a,S2,D,N,M) +  countPaths(a,S3,D,N,M) );
	}else{
		return 0;
	}
}

int main(){

	// int a[3][3] = {
	// 				{1,1,1},
	// 				{1,1,1},
	// 				{1,1,1}
	// 			};
	int a[3][3] = {
					{1,1,1},
					{0,0,1},
					{0,0,1}
				};
	
	int N=3,M=3;
	pair <int,int>S = make_pair(0,0),D=make_pair(N-1,M-1);
	cout<<countPaths(a,S,D,N,M)<<endl;
	
	return 0;
}

- rv July 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Then use DP to compute the solution in O(nm) complexity with O(nm) memory:

public static int countPaths(int[][] m){
    if(m == null){
        throw new NullPointerException();
    }
    int xDim = m.length;
    int yDim = m[0].length;
    if(xDim == 0 || yDim == 0){
        throw new IllegalArgumentException();
    }

    int[][] track = new int[xDim][yDim];
    
    //setup the base cases
    track[xDim-1][yDim-1] = m[xDim-1][yDim-1];
    for(int x = xDim-2; x > -1; x--){
        if(m[x][yDim-1] == 1){
            track[x][yDim-1] = track[x+1][yDim-1];
        }
        else{
            track[x][yDim-1] = 0;
        }
    }
    for(int y = yDim-2; y > -1; y--){
        if(m[xDim-1][y] == 1){
            track[xDim-1][y] = track[xDim-1][y+1];
        }
        else{
            track[xDim-1][y] = 0;
        }
    }

    //now compute the remaining scores
    for(int x = xDim-2; x > -1; x--){
        for(int y = yDim-2; y > -1; y--){
            if(m[x][y] == 1){
                track[x][y] = track[x+1][y] + track[x][y+1] + track[x+1][y+1];
            }
            else{
                track[x][y] = 0;
            }
        }
    }
    return track[0][0];
}

- zortlord July 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<string> getAllpossiblePaths(const& vector<vector<bool>> grid){
	
	vector<string> paths;
	checkPaths(0, 0, grid, "", paths);
	return paths;
}

void checkPaths(int x, int y, string curr_path, const& vector<vector<bool>> grid, vector<string>& paths){

	int M = grid.size();
	int N = grid[0].size();
	
	// Check if we've reached the last destination
	if( x == N-1 && y == M-1){
		paths.push(path);
		return;
	}

	if ( (x + 1) < N &&  grid(x +1, y)) checkPaths(x +1, y, curr_path + "R", paths);
        else if ( (y + 1) < M &&  grid(x, y + 1)) checkPaths(x, y+1, curr_path + "D", paths);
        else if ( (x + 1) <  N && (y+1) < M && grid(x+1, y+1)) checkPaths(x+1, y+1, curr_path + "DD", paths);

	return;
}

- Solution July 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I liked the last C++ solution. It is short and elegant. But it has a few minor bugs which I have corrected as shown below. For the 3x3 all ones matrix the answer is 13 and for the 3x3 matrix with 2x2 zeros in the lower left the answer is 2.

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

void checkPaths(int x, int y,string curr_path, const vector<vector<bool>>& grid, vector<string>& paths) {
  int M = grid.size();
  int N = grid[0].size();

  if( x == M-1 && y == N-1 ) {
    paths.push_back(curr_path);
    return;
  }

/**  R: right movement
     D: down  movement
     I: diagonal movement
**/
  if( (x+1) < M && grid[x+1][y] )
    checkPaths(x+1, y, curr_path+"R", grid, paths);
  if( (y+1) < N && grid[x][y+1] )
    checkPaths(x, y+1, curr_path+"D", grid, paths);
  if( (x+1) < M && (y+1) < N && grid[x+1][y+1] )
    checkPaths(x+1, y+1, curr_path+"I", grid, paths);

}

vector<string> getAllPossiblePaths(const vector<vector<bool>>& grid) {
  vector<string> paths;
  checkPaths(0,0,"",grid,paths);
  return paths;
}

int main()
{
  vector<vector<bool>> grid = {   {1,1,1},
                                  {0,0,1},
                                  {0,0,1}
                              };
/**  vector<vector<bool>> grid = {   {1,1,1},
                                  {1,1,1},
                                  {1,1,1}
                              };  **/
  vector<string> result = getAllPossiblePaths(grid);
  cout << "Number of paths: " << result.size() << "\n";
  cout << "The paths are:\n";
  for( string s : result ) {
    reverse(s.begin(), s.end());
    cout << s << "\n";
  }
  return 0;
}

- dm10023 August 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int GetPossiblePaths(const std::vector<std::vector<int> >& v)
{
    if(v.empty())
        return 0;
    std::vector<std::vector<int> > counts(v.size(),std::vector<int>(v[0].size()));
    
    counts[0][0]=1;
    for(size_t i=0; i<v.size();++i) // on line
    {
        for(size_t j=0; j<v[0].size();++j) // on col
        {
            if(i==0 && j==0)
                continue;
            if (v[i][j]==0)
                counts[i][j]=0;
            else
            {
                bool fromLeft = (j==0 ? false : v[i][j-1] == 1);
                bool fromUp = (i==0? false : v[i-1][j] == 1);
                bool fromUpLeft = (i==0 || j==0 ? false : v[i-1][j-1] ==1);
                counts[i][j]= fromLeft + fromUp + fromUpLeft;    
            }
        }
    }    
    return counts[v.size()][v[0].size()];
}

- zebullon September 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int GetPossiblePaths(const std::vector<std::vector<int> >& v)
{
    if(v.empty())
        return 0;
    std::vector<std::vector<int> > counts(v.size(),std::vector<int>(v[0].size()));
    
    counts[0][0]=1;
    for(size_t i=0; i<v.size();++i) // on line
    {
        for(size_t j=0; j<v[0].size();++j) // on col
        {
            if(i==0 && j==0)
                continue;
            if (v[i][j]==0)
                counts[i][j]=0;
            else
            {
                bool fromLeft = (j==0 ? false : v[i][j-1] == 1);
                bool fromUp = (i==0? false : v[i-1][j] == 1);
                bool fromUpLeft = (i==0 || j==0 ? false : v[i-1][j-1] ==1);
                counts[i][j]= fromLeft + fromUp + fromUpLeft;    
            }
        }
    }    
    return counts[v.size()][v[0].size()];
}

- zebullon September 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am a super coding noob, been coding for a few weeks, but I would tackle this like so...

public static ArrayList<String> getPaths( int[][] a) {

	//Create list container for new paths
	ArrayList<String> paths = new ArrayList<String>();

	//Start checking for paths
	check(0,0,a,paths);

	//return paths if they have values
	if ( paths.size() == 0 ) {
		//throw exception stating that no paths available
		throw new Exception("No paths available for grid");
	} else {
		//resize data structure to elements
		paths.trimToSize();
		//return paths to user
		return paths;
	}
}

public static void check( int x, int y, int[][] grid, ArrayList<String> paths, String currPath) {
	//check if index is in bounds 
	if ( x < grid[0].length && y < grid.length ) {
		//check for success path
		if ( x == grid[0].length -1 && y == grid.length -1 && grid[y][x] == 1) {
			//include final points and end path
			currPath += "(" + x + ", " + y + "), END";
			paths.add(currPath);
		//check for possible move
		} else if ( grid[y][x] == 1 ) {
			currPath += "(" + x + ", " + y + "),";
			check(x+1,y,grid,paths,currPath); //right
			check(x, y+1, grid, paths, currPath); //down
			check(x+1, y+1, grid, paths, currPath); //diag
		} else {
			//do nothing, not a possible move
		}
	}
}

public static void check(int x, int y, int[][] grid, ArrayList<String> paths) {
	String currPath = "";
	check(x,y,grid,paths,currPath);
}

This is kind of a pseudo java code write up. I also skipped a few checks.

- CodingNoob October 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done via bottom-up recursion too.

def numpaths(grid):
m = len(grid[0])-1
n = len(grid)-1
print(numpathsrec(grid, m, n))


def numpathsrec(grid, m, n):
if m < 0 or n < 0 or grid[m][n] == 0:
return 0
if m == 0 and n == 0:
return 1
return 1 + numpathsrec(grid, m - 1, n) + numpathsrec(grid, m, n - 1) + numpathsrec(grid, m - 1, n - 1)

- Nikhil Joshi October 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def numpaths(grid):
    m = len(grid[0])-1
    n = len(grid)-1
    print(numpathsrec(grid, m, n))


def numpathsrec(grid, m, n):
    if m < 0 or n < 0 or grid[m][n] == 0:
        return 0
    if m == 0 and n == 0:
        return 1
    return 1 + numpathsrec(grid, m - 1, n) + numpathsrec(grid, m, n - 1) + numpathsrec(grid, m - 1, n - 1)

- Nikhil Joshi October 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another Java version, that prints the actual paths visited for each valid traversal.

import java.util.ArrayList;
import java.util.List;

/**
 * Recursive traversal of 2 dim array
 * @author bill p
 *
 */
public class Traverse {
	public static void main(String[] args) {
		int[][] arr = {
						{1,1,1},
						{1,1,1},
						{1,0,1},
						{1,1,1},
		};
		
		// This is a List of coordinate paths.  The inner List<Integer[]>
		//   holds the row and column for each array element that you visit on
		//   a valid path.
		List<List<Integer[]>> list = new ArrayList<List<Integer[]>>();
		
		// Launch numPaths here, and start the at row 0, column 0;
		int paths = numPaths(arr,0,0,list,new ArrayList<Integer[]>());
		System.out.println("num of paths = " +paths);
		System.out.println("actual paths for each possible traversal");
		for(List<Integer[]> innerList:list){
			for(Integer[] coordinates : innerList){
				System.out.print("["+coordinates[0]+","+coordinates[1]+"]");	
			}
			System.out.println();
			
		}
	}
	
	/**
	 * This method calls itself recursively, exiting each recursion when
	 *   you have completed a traversal.
	 * 
	 * @param arr - 2 dim array
	 * @param m - current row index
	 * @param n - current column index
	 * @param list - the list of List<Integer[]> that holds each traversal
	 * @param currentStack - the current stack of Integer[] pairs during a traversal
	 * @return
	 */
	static int numPaths(int[][]arr,int m,int n,List<List<Integer[]>> list,List<Integer[]> currentStack){
		// add the current coordinates to stack
		currentStack.add(new Integer[]{m,n});
		// initialize path count
		//  At each cell that you visit, you 2 general conditions:
		//   1.  You are at a cell that is at the last row or last column of the grid:
		//             In this case, you can only go down or to the right.  The path count can only
		//               be incremented 1 time.
		//   2.  You are at a cell where you can go right, down or diagonal.  Therefore,
		//          from this cell, you can accumulate up to 3 paths (this updating the path count above 3 times.
		int npaths=0;
		
		//  See if you have reached the final destination
		if(m==arr.length-1 && n==arr[0].length-1){
			// You have reached the final destination.  Write out the currentStack.
			list.add(new ArrayList<Integer[]>(currentStack));
			// set number of paths for this call to numPaths = 1.
			npaths = 1;
		}else if(m>=arr.length-1){
			// can only go right
			if(arr[m][n+1]==1){
				// set npaths to either 0 or 1, depending if you can get
				//  to the final destination from here.
				npaths =  numPaths(arr,m,n+1,list,currentStack);
			}	
		}else if(n>=arr[m].length-1){
			// can only go down
			if(arr[m+1][n]==1){
				// set npaths to either 0 or 1, depending if you can get
				//  to the final destination from here.
				npaths = numPaths(arr,m+1,n,list,currentStack);
			}
			
		}else{
			// look right
			if(n<arr[m].length-1 && arr[m][n+1]==1){
				// set npaths to the number of paths that
				//   lead to the final destination from here.
				npaths += numPaths(arr,m,n+1,list,currentStack);
				
			}
			
			// look down
			if(m< arr.length-1 && arr[m+1][n]==1){
				// set npaths to the number of paths that
				//   lead to the final destination from here.
				npaths += numPaths(arr,m+1,n,list,currentStack);
			}
			
			// look diagonal
			if(n<arr[m].length-1 && m< arr.length-1 && arr[m+1][n+1]==1){
				// set npaths to the number of paths that
				//   lead to the final destination from here.
				npaths += numPaths(arr,m+1,n+1,list,currentStack);
			}
			
		}
		
		// remove the current coordinate pair from the stack
		currentStack.remove(currentStack.size()-1);
		// return the total number of paths visited from row m and column n
		return npaths;
		
	}
	
	
}

- Bill P. November 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include "stdafx.h"

int rowmove[] = { 1, 1, 0 };
int colmove[] = { 1, 0, 1 };

int countpaths(int arr[][3], int row, int col,int m, int n )
{
	int paths = 0;
	if ((row == m - 1) && (col == n - 1))
		return 1;
	else
	{
		for (int dir = 0; dir < 3; dir++)
		{
			int newrow = rowmove[dir] + row;
			int newcol = colmove[dir] + col;
			if ((newrow <m) && (newcol< n))
			{
				if (arr[newrow][newcol] == 1)
					paths += countpaths(arr, newrow, newcol, m, n);
			}
		}
	}
	return paths;
}

/*
1 1 1
1 0 1
1 1 1
*/

int _tmain(int argc, _TCHAR* argv[])
{
	int arr[3][3] = { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } };
	int val =countpaths(arr, 0, 0, 3, 3);
	return 0;
}

- Hema December 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include "stdafx.h"

int rowmove[] = { 1, 1, 0 };
int colmove[] = { 1, 0, 1 };

int countpaths(int arr[][3], int row, int col,int m, int n )
{
	int paths = 0;
	if ((row == m - 1) && (col == n - 1))
		return 1;
	else
	{
		for (int dir = 0; dir < 3; dir++)
		{
			int newrow = rowmove[dir] + row;
			int newcol = colmove[dir] + col;
			if ((newrow <m) && (newcol< n))
			{
				if (arr[newrow][newcol] == 1)
					paths += countpaths(arr, newrow, newcol, m, n);
			}
		}
	}
	return paths;
}

/*
1 1 1
1 0 1
1 1 1
*/

int _tmain(int argc, _TCHAR* argv[])
{
	int arr[3][3] = { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } };
	int val =countpaths(arr, 0, 0, 3, 3);
	return 0;
}

- Hema December 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done with simple recursion. My simple version is as follows:

int rowmove[] = { 1, 1, 0 };
int colmove[] = { 1, 0, 1 };

int countpaths(int arr[][3], int row, int col,int m, int n )
{
int paths = 0;
if ((row == m - 1) && (col == n - 1))
return 1;
else
{
for (int dir = 0; dir < 3; dir++)
{
int newrow = rowmove[dir] + row;
int newcol = colmove[dir] + col;
if ((newrow <m) && (newcol< n))
{
if (arr[newrow][newcol] == 1)
paths += countpaths(arr, newrow, newcol, m, n);
}
}
}
return paths;
}

/*
1 1 1
1 0 1
1 1 1
*/

int _tmain(int argc, _TCHAR* argv[])
{
int arr[3][3] = { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } };
int val =countpaths(arr, 0, 0, 3, 3);
return 0;
}

- Hema December 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple c++ solution

int rowmove[] = { 1, 1, 0 };
int colmove[] = { 1, 0, 1 };

int countpaths(int arr[][3], int row, int col,int m, int n )
{
	int paths = 0;
	if ((row == m - 1) && (col == n - 1))
		return 1;
	else
	{
		for (int dir = 0; dir < 3; dir++)
		{
			int newrow = rowmove[dir] + row;
			int newcol = colmove[dir] + col;
			if ((newrow <m) && (newcol< n))
			{
				if (arr[newrow][newcol] == 1)
					paths += countpaths(arr, newrow, newcol, m, n);
			}
		}
	}
	return paths;
}

/*
1 1 1
1 0 1
1 1 1
*/

int _tmain(int argc, _TCHAR* argv[])
{
	int arr[3][3] = { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } };
	int val =countpaths(arr, 0, 0, 3, 3);
	return 0;
}

- Hema December 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c++ solution of get_all_possible_paths function

#include <iostream>
#include <string>
#include <list>

// use '-', '\', and '|' chars to indicate direction.
std::list<std::string> get_all_possible_paths(const int *data, int W, int H);

using namespace std;

void get_all_possible_paths_aux(const int *data, int W, int H, list<string> &ret, int x, int y, char *path)
{
	if (y > 0 && data[y*W+x-W])
		path[-1] = '|', get_all_possible_paths_aux(data, W, H, ret, x, y-1, path-1);
	if (y > 0 && x > 0 && data[y*W+x-W-1])
		path[-1] = '\\', get_all_possible_paths_aux(data, W, H, ret, x-1, y-1, path-1);
	if (x > 0 && data[y*W+x-1])
		path[-1] = '-', get_all_possible_paths_aux(data, W, H, ret, x-1, y, path-1);
	if (x==y && x==0)
		ret.push_back(path);
}

list<string> get_all_possible_paths(const int *data, int W, int H)
{
	int max_path_len = W+H-2;
	char *tmp = new char[max_path_len+1];
	char *path = tmp+max_path_len;
	*path = '\0';
	list<string> ret;
	get_all_possible_paths_aux(data, W, H, ret, W-1, H-1, path);
	delete[] tmp;
	return ret;
}

void main()
{
	int m0[] = {1,1,1, 1,1,1, 1,1,1};
	int m1[] = {1,1,1, 0,0,1, 0,0,1};

	list<string> p0 = get_all_possible_paths(m0, 3, 3);
	list<string> p1 = get_all_possible_paths(m1, 3, 3);
	cout << "available paths: " << p0.size() << endl;
	for (auto it=p0.begin(); it!=p0.end(); ++it)
		cout << "\t" << *it << "\n";
	cout << "\navailable paths: " << p1.size() << endl;
	for (auto it=p1.begin(); it!=p1.end(); ++it)
		cout << "\t" << *it << "\n";
}

- pavelp May 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;
import java.util.Queue;

public class PrintAllPathsInMatrixToEnd {

	public void DFS(boolean[][] visited, int[][] matrix, int x, int y, String cpath) {
		cpath += matrix[x][y];
		if (x == matrix.length - 1 && y == matrix[0].length - 1) {
			System.out.println(cpath);
			return;
		}
		
		// visited[x][y] = true;
		int[] row = new int[] { 0, 1, 1 };
		int[] col = new int[] { 1, 1, 0 };
		for (int i = 0; i < row.length; i++) {
			if (row[i] + x < matrix.length && col[i] + y < matrix[0].length) {
				DFS(visited, matrix, row[i] + x, col[i] + y, cpath);
			}
		}

	}

	public void printAllPaths(int[][] matrix) {
		boolean[][] visited = new boolean[matrix.length][matrix[0].length];
		DFS(visited, matrix, 0, 0, "");
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		PrintAllPathsInMatrixToEnd p = new PrintAllPathsInMatrixToEnd();
		p.printAllPaths(new int[][] { { 1, 1, 1 }, { 0, 0, 1 }, { 0, 0, 1 } });
	}

}

- Siddhi October 15, 2017 | 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