Bloomberg LP Interview Question
Financial Software DevelopersCountry: United States
Interview Type: Phone Interview
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;
}
}
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.
#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;
}
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];
}
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;
}
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;
}
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()];
}
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()];
}
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.
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)
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)
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;
}
}
#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;
}
#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;
}
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;
}
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;
}
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";
}
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 } });
}
}
Since all directions are possible and you have exclusionary positions, a search approach would be necessary. Backtracking is probably easiest.
- zortlord July 14, 2015