Yahoo Interview Question
Computer ScientistsCountry: United States
Interview Type: In-Person
public class MatrixPaths {
public static void printpaths(int[][] matrix) {
int[] path = new int[matrix.length];
for (int i = 0; i < matrix[0].length; i++)
printpaths(matrix, path, 0, 0, i);
}
private static void printpaths(int[][] matrix, int[] path, int index, int row, int column) {
path[index++] = matrix[row][column];
row++;
if (row == matrix.length)
print(path);
else if (row < matrix.length) {
for (int i = column - 1; i <= column + 1; i++)
if (i > -1 && i < matrix[0].length)
printpaths(matrix, path, index, row, i);
}
}
private static void print(int[] path) {
for (int i = 0; i < path.length; i++)
System.out.print(path[i] + " ");
System.out.println();
}
public static void main(String args[]) {
int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
printpaths(matrix);
}
}
public class PossiblePaths {
private static List<String> getPath(int[][] a,int row, int col, int sum){
if(row <0 || row > 2)
return new ArrayList<String>();
if(col < 0 || col > 2)
return new ArrayList<String>();
List<String> paths = new ArrayList<String>();
//sum = sum + a[row][col];
paths.addAll(getPath(a,row+1,col-1,0));
paths.addAll(getPath(a,row+1,col,0));
paths.addAll(getPath(a,row+1,col+1,0));
for(int i =0;i<paths.size();i++){
paths.set(i,String.valueOf(a[row][col]) + "-->"+paths.get(i));
}
if(paths.isEmpty()){
paths.add(String.valueOf(a[row][col]));
}
return paths;
}
public static void main(String[] argv){
int a[][] = {{1,2,3},{4,5,6},{7,8,9}};
List<String> paths = getPath(a,0,0,0);
for(String path: paths){
System.out.println(path.toString());
}
}
}
#include<iostream>
#include<string>
using namespace std;
#define ROW 3
#define COL 3
void print_path(char mat[ROW][COL], int i, int j, string path) {
if(i==ROW-1) {
cout<<path<<mat[i][j]<<endl;
return;
}
// move row-wise down-left
if(i+1<ROW) {
//
if(j-1>=0)
print_path(mat, i+1, j-1,path+mat[i][j]);
// move down
print_path(mat, i+1, j,path+mat[i][j]);
// move down-right
if(j+1<COL)
print_path(mat,i+1, j+1,path+mat[i][j]);
}
}
int main() {
char mat[ROW][COL] = {{'1','2','3'},{'4','5','6'},{'7','8','9'}};
print_path(mat, 0, 0, "");
//print_path(mat, 0, 1, "");
//for(int i=0;i<ROW; i++){
// for(int j=0; j<COL; j++) {
// print_path(mat, i, j, "");
// }
//}
return 0;
}
Solution prints all possible paths allowed and returns the path with the max sum.
final int MAX_SIZE = 10;
int matrix[MAX_SIZE][MAX_SIZE];
class Foo{
String sting;
int data;
}
String printPaths(int row, int col){
Foo foo = printPathsRecursive(int row, int col, "");
return(foo.string);
}
Foo printPathsRecursive(int row, int col, Sting prevPath){
if(row < 0 || col < 0 || row >= MAX_SIZE || col >= MAX_SIZE)
return(null);
if(row == MAX_SIZE){
Foo foo= new Foo();
foo.string = prePath + matrix[row][col];
foo.data = matrix[row][col];
System.out.println(foo.string);
return(foo);
}
String path = new String(prevPath);
path += matrix[row][col] + "-";
Foo path1 = printPaths(row+1, col, path);
Foo path2 = printPaths(row+1, col+1, path);
Foo path3 = printPaths(row+1, col-1, path);
if(path1 != null && (path2 == null || path1.data >= path2.data) && (path3 == null || path1.data >= path3.data)){
path1.data += matrix[row][col];
return(path1);
}
if(path2 != null && (path1 == null || path2.data >= path1.data) && (path3 == null || path2.data >= path3.data)){
path2.data += matrix[row][col];
return(path2);
}
if(path3 != null && (path2 == null || path3.data >= path2.data) && (path1 == null || path3.data >= path1.data)){
path3.data += matrix[row][col];
return(path3);
}
}
∑<sub>0</sub><sup>n</sup> 3<sup>n</sup>
sum of 3 to the power k from k equals 0 to n.
downStep function which recurses on one step down in the matrix and returns the maxsum of the paths
public static int downStep(int row, int col, int[][] mat, int[] arr){
if(row>=mat.length || col<0 || col>=mat[0].length){
return -1;
}
arr[row] = mat[row][col];
if(row==mat.length-1){
int sum=0;
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+"-");
sum+=arr[i];
}
System.out.println();
return sum;
}
int sum1 = downStep(row+1,col-1,mat,arr);
int sum2 = downStep(row+1,col,mat,arr);
int sum3 = downStep(row+1,col+1,mat,arr);
return maxOfThree(sum1,sum2,sum3);
}
This function can be called this way:
int sum = 0;
int maxSum = 0;
for(int i=0;i<mat[0].length;i++){
int arr[] = new int[mat.length];
arr[0] = mat[0][i];
sum = downStep(0,i,mat,arr);
if(sum>maxSum)
maxSum = sum;
}
System.out.println("Maxsum ="+ maxSum);
Other helper function:
public static int maxOfThree(int sum1,int sum2, int sum3){
if(sum1>=sum2 && sum1>=sum3)
return sum1;
if(sum2>=sum3)
return sum2;
else return sum3;
}
void AllPossiblePaths(int **a, int m, int n, int currrow, int currcol, int i)
{
if(currrow < 0 && currrow >= m)
return;
else
{
printf("%d", a[i]);
AllPossiblePaths(a, m, n, currrow -1, currcol +1, i);
AllPossiblePaths(a, m, n, currrow +1, currcol, i);
AllPossiblePaths(a, m,n, currrow +1, currcol+1, i);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[][] = {{1,2,3},{4,5,6},{7,8,9}};
for(int i=0; i< 3, i++)
{
AllPossiblePaths(a, 3, 3, 0, i, i);
}
return 0;
}
The path with the maximum sum can to found in O(N*M) time using the following algorithm.
1) Create an auxiliary matrix B to store the maximum sum of a path from a starting node (0,0...N-1) to node x,y
2) Working from top to bottom, set the value of every other node in B to the maximum of value of its 1-3 parents ({x-1,y-1}, {x-1,y}, and {x-1,y+1}). This can be considered to be a breadth first traversal of a DAG and thus this algorithm resembles Dijkstra's shortest path algorithm.
3) Working from bottom to top, follow the path in B with the maximum value (greedy search).
Code follows. I have also included a brute force algorithm and use it to verify the correctness of the faster algorithm. The brute force algorithm could be easily modified to print all possible paths.
public class YahooMaximumPath {
public static void main(String[] args) {
// 1x1
{
int a[][] = new int[][] {{4}};
dumpGraph(a);
Path maxPath1 = maximumPath(a);
System.out.println(maxPath1 + " = " + maxPath1.sum(a));
Path maxPath2 = naiveMaximumPath(a);
System.out.println(maxPath2 + " = " + maxPath2.sum(a));
assertEquals(maxPath1.sum(a), maxPath2.sum(a));
}
// 2x2
{
int a[][] = new int[][] {{-4,3},{-9,1}};
dumpGraph(a);
Path maxPath1 = maximumPath(a);
System.out.println(maxPath1 + " = " + maxPath1.sum(a));
Path maxPath2 = naiveMaximumPath(a);
System.out.println(maxPath2 + " = " + maxPath2.sum(a));
assertEquals(maxPath1.sum(a), maxPath2.sum(a));
}
// 2x2 all negative
{
int a[][] = new int[][] {{-4,-3},{-9,-1}};
dumpGraph(a);
Path maxPath1 = maximumPath(a);
System.out.println(maxPath1 + " = " + maxPath1.sum(a));
Path maxPath2 = naiveMaximumPath(a);
System.out.println(maxPath2 + " = " + maxPath2.sum(a));
assertEquals(maxPath1.sum(a), maxPath2.sum(a));
}
// 3x3
{
int a[][] = new int[][] {{5,-2,5},{1,5,3},{-8,2,9}};
dumpGraph(a);
Path maxPath1 = maximumPath(a);
System.out.println(maxPath1 + " = " + maxPath1.sum(a));
Path maxPath2 = naiveMaximumPath(a);
System.out.println(maxPath2 + " = " + maxPath2.sum(a));
assertEquals(maxPath1.sum(a), maxPath2.sum(a));
}
// 4x4
{
int a[][] = new int[][] {{1,8,-3,1},{8,6,-5,1},{1,4,8,9},{-9,-3,4,6}};
dumpGraph(a);
Path maxPath1 = maximumPath(a);
System.out.println(maxPath1 + " = " + maxPath1.sum(a));
Path maxPath2 = naiveMaximumPath(a);
System.out.println(maxPath2 + " = " + maxPath2.sum(a));
assertEquals(maxPath1.sum(a), maxPath2.sum(a));
}
// Random
{
Random random = new Random();
int a[][] = new int[2 + Math.abs(random.nextInt()) % 10][2 + Math.abs(random.nextInt()) % 10];
//int a[][] = new int[3][3];
for (int i = 0; i < a.length; ++i) {
for (int j = 0; j < a[0].length; ++j) {
a[i][j] = random.nextInt() % 100;
}
}
dumpGraph(a);
Path maxPath1 = maximumPath(a);
System.out.println(maxPath1 + " = " + maxPath1.sum(a));
Path maxPath2 = naiveMaximumPath(a);
System.out.println(maxPath2 + " = " + maxPath2.sum(a));
assertEquals(maxPath1.sum(a), maxPath2.sum(a));
}
}
static void dumpGraph(int a[][]) {
for (int b[] : a) {
System.out.println(Arrays.toString(b));
}
}
static void assertEquals(int i1, int i2) {
if (i1 != i2) {
throw new RuntimeException(i1 + " != " + i2);
}
}
static class Path extends ArrayList<int[]> {
private static final long serialVersionUID = 1L;
public Path() {
}
public Path(int capacity) {
super(capacity);
}
public int sum(int a[][]) {
int sum = 0;
for (int p[] : this) {
sum += a[p[0]][p[1]];
}
return sum;
}
@Override
public String toString() {
StringBuffer buffer = new StringBuffer();
for (int a[] : this) {
buffer.append(Arrays.toString(a) + ", ");
}
return buffer.toString();
}
}
// Create an auxiliary matrix B to store the maximum sum of a path from a starting node (0,0...N-1) to node x,y
// Working from top to bottom, set the value of every other node in B to the maximum of value of its 0-3 parents ({x-1,y-1}, {x-1,y}, and {x-1,y+1}).
// Working from bottom to top, follow the path in B with the maximum value (greedy search).
//
// O(N*M)
static Path maximumPath(int a[][]) {
int N = a.length;
int M = a[0].length;
// Create an auxiliary array to hold sum of path from 0,0...M-1 to x,y.
int b[][] = new int[N][M];
// The parents of x,y are {x-1,y-1}, {x-1,y}, and {x-1,y+1}.
// Iterate over the graph in an order such that a vertex's parents are visited first.
// It turns out that the most obvious pair of nested loops satisfies this requirement.
for (int x = 0; x < N; ++x) {
for (int y = 0; y < M; ++y) {
int leftParentSum = Integer.MIN_VALUE;
int middleParentSum = Integer.MIN_VALUE;
int rightParentSum = Integer.MIN_VALUE;
if (x > 0) {
if (y > 0) {
leftParentSum = b[x-1][y-1];
}
middleParentSum = b[x-1][y];
if (y < M - 1) {
rightParentSum = b[x-1][y+1];
}
}
// The maximum sum of a path from 0,0...M-1 to x,y is the sum at x,y plus the max sum of the paths to the parents of x,y.
int max = Math.max(Math.max(leftParentSum, middleParentSum), rightParentSum);
if (max == Integer.MIN_VALUE) {
max = 0;
}
b[x][y] = a[x][y] + max;
}
}
//dumpGraph(b);
Path result = new Path();
int x = N-1;
int y = 0;
// First find the bottom node with the max sum.
int max = Integer.MIN_VALUE;
for (int i = 0; i < M; ++i) {
if (b[N-1][i] > max) {
max = b[N-1][i];
y = i;
}
}
// Now find the path with the max sum by walking the graph backwards choosing the parent with the max sum.
while (x > 0) {
result.add(new int[] {x,y});
int leftParentSum = Integer.MIN_VALUE;
int middleParentSum = Integer.MIN_VALUE;
int rightParentSum = Integer.MIN_VALUE;
if (y > 0) {
leftParentSum = b[x-1][y-1];
}
middleParentSum = b[x-1][y];
if (y < M - 1) {
rightParentSum = b[x-1][y+1];
}
if (leftParentSum > middleParentSum && leftParentSum > rightParentSum) {
y--;
}
else if (rightParentSum > middleParentSum) {
y++;
}
x--;
}
result.add(new int[] {0,y});
Collections.reverse(result);
return result;
}
// Consider the matrix to be a weighted DAG where all edges leading to a vertex have the same weight.
// Iterate through all possible paths and pick the one with the maximum sum.
//
// O(bad)
//
// Complexity can be analyzed by calculating the sum of the number of visitations of each node.
// This visitations of each node can be represented as a NxM matrix where the value at each node is the sum of values of its 1-3 parents.
// The first row is initialized with the value 1.
//
// For 2x2
// 01 01
// 02 02
// iterations = 1+1+2+2 = 7
//
// For 3x3
// 01 01 01
// 02 03 02
// 05 07 05
// iterations = 1+1+1+2+3+2+5+7+5=27
//
// For 4x4
// 01 01 01 01
// 02 03 03 02
// 05 08 08 05
// 13 21 21 13
// iterations = 1+1+1+1+2+3+3+2+5+8+8+8+5+13+21+21+13=108
//
// This is a finite sequence. I don't know if it's possible to calculate the sum of the sequence in O(1) time.
// That is perhaps a problem of its own right.
static Path naiveMaximumPath(int a[][]) {
Path path = new Path();
Path maxPath = new Path();
int maxSum[] = new int[] {Integer.MIN_VALUE};
int iterations = 0;
for (int y = 0; y < a[0].length; ++y) {
iterations += naiveMaximumPath(a, path, 0, maxPath, maxSum, 0, y);
}
System.out.println("iterations=" + iterations);
return maxPath;
}
static int naiveMaximumPath(int a[][], Path path, int sum, Path maxPath, int[] maxSum, int x, int y) {
int N = a.length;
int M = a[0].length;
sum += a[x][y];
int iterations = 1;
path.add(new int[] {x,y});
if (x == N-1) {
if (sum > maxSum[0]) {
maxSum[0] = sum;
maxPath.clear();
maxPath.addAll(path);
}
}
else {
if (y > 0) {
iterations += naiveMaximumPath(a, path, sum, maxPath, maxSum, x+1, y-1);
}
iterations += naiveMaximumPath(a, path, sum, maxPath, maxSum, x+1, y);
if (y < M - 1) {
iterations += naiveMaximumPath(a, path, sum, maxPath, maxSum, x+1, y+1);
}
}
path.remove(path.size()-1);
return iterations;
}
}
It is very simple to just print out the path but it is a bit more complicated to find the max sum and print out the path.
As there were no solution has done so I'll posted mine which provides the path with the max sum.
I used a list to track the path as recreating it is less expensive operations rather than recreating a string for every call.
/// To simplify the parameters I'm encapsulating some of them into a context object
class PrinAllPathsContext
{
public int[][] Matrix { get; set; }
public int M { get; set; }
public int N { get; set; }
public string CurrentMaxSumPath { get; set; }
public int CurrentMaxSum { get; set; }
public List<int> CurrentPath { get; set; }
}
public PrintAllPaths(int[][] matrix, int m, int n)
{
PrinAllPathsContext context = new PrinAllPathsContext()
{
Matrix = matrix,
M = m,
N = n,
CurrentMaxSum = int.MinValue,
CurrentMaxSumPath = null,
CurrentPath = new List<int>()
}
// Calling the core method for each of the top elements of the matrix
for(int i = 0; i < m; i++)
{
PrintAllPathsCore(context, i, 0, "");
}
// Printing both the Max Sum and the Path
if(context.CurrentPath != null)
{
Console.WriteLine(string.Format(
"The max Sum Path was: {0}\nPath: {1}",
context.CurrentMaxSum,
PathToString(context.CurrentMaxSumPath));
}
}
private PrintAllPathsCore(
context,
int currentM,
int currentN,
currentSum)
{
int currentVal = conext.Matrix[currentM][currentN];
context.CurrentPath.Add(currentVal);
currentSum += currentVal;
// Moving N another level
currentN++;
if(currentN == n)
{
// This means with just worked the last in the path
Console.WriteLine(PathToString(context.CurrentPath));
if(currentSum > context.CurrentSumMax)
{
context.CurrentSumMax = currentSum;
context.CurrentSumMaxPath = new List<int>(currentPath);
}
}
else
{
// This means that there is another row to go
if(currentM > 0)
{
PrintAllPathsCore(context, currentM -1, currentN, currentSum);
}
PrintAllPathsCore(context, currentM, currentN, currentSum);
if(currentM < (context.M - 1))
{
PrinAllPathsCore(context, currentM + 1, currentN, currentSum);
}
}
context.CurrentPath.RemoveAt(context.CurrentPath.Length -1);
}
/// Returns string representation of the path
string PathToString(List<int> currentPath)
{
StrinbBuilder sb = new stringBuilder();
foreach(int val in currentPath)
{
sb.Add(val.ToString() + "-");
}
// Removing the extra "-" at the end
sb.SetLength(currentPath.Length*2 -1);
return sb.ToString();
}
*/
public class MatrixTraversal {
static int m = 3;
static int n = 3;
static int maxSum =0;
public static void main(String args[]){
int[][] mat= {{1,2,3},{4,5,6},{7,8,9}};
for(int i=0;i<m;i++){
traverse(mat,0,i,new ArrayList<Integer>());
}
System.out.println(maxSum);
}
private static void traverse(int[][] mat,int i,int j,ArrayList<Integer>path){
if(i>m-1 || i<0 || j>n-1 || j<0)
{
System.out.println(path);
int sum = 0;
for(int k = 0;k< path.size();k++){
sum+=path.get(k);
}if(maxSum < sum) maxSum = sum;
return;
}
// System.out.println();
path.add(mat[i][j]);
traverse(mat,i+1,j+1,new ArrayList<Integer>(path));
traverse(mat,i+1,j,new ArrayList<Integer>(path));
traverse(mat,i+1,j-1,new ArrayList<Integer>(path));
//System.out.print(mat[i][j]);
}
}
include<iostream>
using namespace std ;
int matrix1[10][10] ;
int n ;
int temp_array[10];
void print_top_to_down(int , int );
int count=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>matrix1[i][j];
int i=1 ;
for(int j=1;j<=n;j++)
{
print_top_to_down(i,j);
}
return 0 ;
}
void print_top_to_down(int x1 , int y1)
{
if(y1==0 || x1>n || y1>n)
{
return ;
}
if(x1<=n)
{
count=x1-1;
temp_array[count] = matrix1[x1][y1];
include<iostream>
using namespace std ;
int matrix1[10][10] ;
int n ;
int temp_array[10];
void print_top_to_down(int , int );
int count=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>matrix1[i][j];
int i=1 ;
for(int j=1;j<=n;j++)
{
print_top_to_down(i,j);
}
return 0 ;
}
void print_top_to_down(int x1 , int y1)
{
if(y1==0 || x1>n || y1>n)
{
return ;
}
if(x1<=n)
{
count=x1-1;
tinclude<iostream>
using namespace std ;
int matrix1[10][10] ;
int n ;
int temp_array[10];
void print_top_to_down(int , int );
int count=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>matrix1[i][j];
int i=1 ;
for(int j=1;j<=n;j++)
{
print_top_to_down(i,j);
}
return 0 ;
}
void print_top_to_down(int x1 , int y1)
{
if(y1==0 || x1>n || y1>n)
{
return ;
}
if(x1<=n)
{
count=x1-1;
temp_array[count] = matrix1[x1][y1];
count++;
}
if(x1==n)
{
cout<<"\n";
for(int i=0;i<count;i++)
cout<<temp_array[i]<<"\t";
}
print_top_to_down(x1+1,y1-1);
print_top_to_down(x1+1,y1);
print_top_to_down(x1+1,y1+1);
}
http://ideone.com/MV0Sd
- loveCoding October 17, 2012