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);
//if this is a solution, record it
if(x == this.m.length && y == this.m[0].length){
}
//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;
}
}``````

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

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);
//if this is a solution, record it
if(x == this.m.length && y == this.m[0].length){
}
//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;
}
}``````

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.

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

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

Comment hidden because of low score. Click to expand.
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];
}``````

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

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

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

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

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";
//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.

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)

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)``````

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
// 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.
// 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;

}

}``````

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

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

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

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

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";
}``````

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

}``````

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.

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.

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.

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.