Amazon Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




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

You can scan all rows, scan all columns, and scan diagonals, but instead of multiplying 4 numbers everytime, you can just do a kind of rolling multiplication - I think this is what the interviewer is looking for as far as optimization.

Say you have a row:

3,4,1,2,5,4,3

calculate x = 3*4*1*2
then when you roll, divide the first number and multiply the next number, so

x /=3
x *= 5

Of course, you can't divide by 0, so when the first number is a 0 and the new number isn't, you need to re-multiply

That way you only do 2 operations rather than 4 operations every step

- Skor February 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

that was what I had in my mind before. But the re-multiply logic will definitely slow you down in the interview session.

- hiuhchan February 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Division is much slower than multiplications, so it's unclear if it would perform better.

- C.C. February 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

You can also check if the first number is grater then the next number before you do any calculation. If true then skip the entire sequence as the result will be smaller then the previous sequence.

- Karan February 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Seems to work. It avoids scanning the same row or column more than once too.

package com.foo;

public class MatrixFinder {
    
    private int find(int[][] array,  int x, int y) {
        int max = Integer.MIN_VALUE;
    
        if (y >= array.length || x >= array[y].length) {
            return max;
        }
    
        boolean checkDiagonal = true;
        if (array.length - y >= 4) {
            max = array[y][x] * array[y+1][x] * array[y+2][x] * array[y+3][x];  
        } else {
            checkDiagonal = false;
        }

        if (array[y].length - x >= 4) {
            int val = array[y][x] * array[y][x+1] * array[y][x+2] * array[y][x+3];  
            max = Math.max(max, val);
        } else {
            checkDiagonal = false;
        }
        
        if (checkDiagonal) {
            int val = array[y][x] * array[y+1][x+1] * array[y+2][x+2] * array[y+3][x+3];  
            if (val > max) {
                max = val;
            }
        }
        
// move the x position
        max = Math.max(max, find(array, x+1, y));

        return max;
    }
    
    public void doit(int[][] array) {
        int max = Integer.MIN_VALUE;

// move the y position
        for (int y = 0; y < array.length; y++) {
            max = Math.max(max, find(array, 0, y));
        }
        
        System.out.println(max);
   }

    public static void main(String[] args) {
        int[][] array = {
            {1, 2, 0, -1 ,4},
            {3, 1, 2, 4, 6},
            {0, 6, 3, 1, 4},
            {1, 3, 2, 0, 7},
            {2, 0, 3, 2, 9}};
            
        MatrixFinder cl = new MatrixFinder();
        cl.doit(array);
    }
    
}

- Mikeo February 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

May not be the best implementation. but it works. Sorry that I am not good at 2D array algorithms.

The idea is basically use a smaller matrix to mask inside a bigger matrix and then get all the products

int getMax(int *input, int k)
{
  int product = -999999;

  for(int p=0; p<k; ++p){
    int prod = 1;
    for (int q=0; q<k; ++q){
      prod *= *(input+(p*k)+q);
    }
    product = (prod > product) ? prod : product;
  }

  for(int p=0; p<k; ++p){
    int prod = 1;
    for (int q=0; q<k; ++q){
      prod *= *(input+(q*k)+p);
    }
    product = (prod > product) ? prod : product;
  }

  int prod = 1;
  for(int p=0; p<k; ++p){
    prod *= *(input+(p*k)+p);
  }
  product = (prod > product) ? prod : product;

  prod = 1;
  for(int p=0; p<k; ++p){
    prod *= *(input+(p*k)+(k-1-p));
  }
  product = (prod > product) ? prod : product;
}

int GetbiggestProduct(int *input, int length, int width, int k)
{
  int max = -999999;
  int product = 1;
  int *test =  new int[k*k];

  for(int i=0; i<length-k+1; ++i){
    for(int j=0; j<width-k+1; ++j){

      for(int s=0; s<k*k; ++s)
        *(test+s) = 1;

      for(int p=0; p<k; ++p){
        for (int q=0; q<k; ++q){
          *(test+p*k+q) *= *(input+length*(i+p)+j+q);
        }
      }

      int tmp = getMax(test, k);
      max = (tmp>max) ? tmp : max;
    }
  }
  return max;
}

int main()
{
  int matrix[] = {1, 2, 0, -1, 4,
          3, 1, 2, 4, 6,
          0, 2, 3, 1, 4,
          1, 3, 2, 0, 7,
          2, 1, 3, 2, 9};

  cout<<GetbiggestProduct(matrix, 5, 5, 4)<<endl;
}

- hiuhchan February 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What I did is find max for each row and column per iteration so I don't need to come back for that particular row or column again, complexity for iteration will be O(row+col)

Then in

getMax()

method I have used one treeSet to store row/column data in sorted manner. complexity for this function is O(n) for iteration and complexity of treesort.

Here is my code:

package ramesh.solutions;

import java.util.Set;
import java.util.TreeSet;

public class MaxMultiplicationFinderr {

	public static int findMax(int[][] arr, int k) {
		int max = Integer.MIN_VALUE;
		System.out.println("Max at begining: " + max);
		
		max = Math.max(max, getMax(arr, 0, 0, k));
		for (int i = 0; i < arr.length; i++) {
			max = Math.max(max, Math.max(getMax(arr, 1, i, k), getMax(arr, 2, i, k)));
		}
		return max;
	}

	public static int getMax(int[][] arr, int isRow, int rowNum, int k) {
		int maxMul = Integer.MIN_VALUE;
		Set<Integer> sortedSet = new TreeSet<Integer>();

		for (int i = 0; i < arr.length; i++) {
			switch (isRow) {
			case 0:
				sortedSet.add(arr[i][i]);
				break;
			case 1:
				sortedSet.add(arr[rowNum][i]);
				break;
			case 2:
				sortedSet.add(arr[i][rowNum]);
				break;
			default:
				break;
			}
		}

		if (sortedSet.size() < k)
			return maxMul;

		Integer[] a = sortedSet.toArray(new Integer[0]);
		int arrLent = a.length;
		maxMul = a[arrLent - 1] * a[arrLent - 2] * a[arrLent - 3] * a[arrLent - 4];
		return maxMul;
	}

	public static void main(String[] args) {
		
		int[][] array = {
	            {1, 2, 0, -1 ,4},
	            {3, 1, 2, 4, 6},
	            {0, 6, 3, 1, 4},
	            {1, 3, 2, 0, 7},
	            {2, 0, 3, 2, 9}};
		System.out.println("Final Max: "+findMax(array, 4));
		
	}
}

- rk.karn32 February 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correct me if I am wrong, but I think there are some problems:
* You only check one of the major diagonals.
* You don't check any of the minor diagonals.
* The algorithm doesn't work (but it does in this case). The numbers must be contiguous in the martrix, which sorting overlooks. So, the algorithm would fail if for instance the 4 and 6 in (4, 0), (4, 1) were swapped.

- Tyson February 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import math
import random
import sys
import time
import numpy as np

arr = [[random.random() for _ in xrange(1000)] for _ in xrange(50)]


def create_tuple_array(rows, cols):
    result = [list() for _ in xrange(rows)]
    for i in xrange(rows):
        result[i] = [tuple() for _ in xrange(cols)]
    return result

def row_reduce(arr, starter):
    num_rows = len(arr)
    num_cols = len(arr[0])
    row_prod_array = np.zeros(shape=(num_rows, num_cols))

    for i in xrange(num_rows):
        for j in xrange(num_cols):
            try:
                if starter[i][j+1] == 0:
                    row_prod = None
                else:
                    row_prod = (arr[i][j] * arr[i][j+1])/starter[i][j+1]
            except Exception as e:
                row_prod = None
            row_prod_array[i][j] = row_prod
    return row_prod_array, arr


def col_reduce(arr, starter):
    num_rows = len(arr)
    num_cols = len(arr[0])
    col_prod_array = np.zeros(shape=(num_rows, num_cols))

    for i in xrange(num_rows):
        for j in xrange(num_cols):
            try:
                if starter[i+1][j] == 0:
                    col_prod = None
                else:
                    col_prod = (arr[i][j] * arr[i+1][j])/starter[i+1][j]
            except Exception as e:
                col_prod = None
            col_prod_array[i][j] = col_prod
    return col_prod_array, arr

def diag_reduce(arr, starter):
    num_rows = len(arr)
    num_cols = len(arr[0])
    diag_prod_array = np.zeros(shape=(num_rows, num_cols))

    for i in xrange(num_rows):
        for j in xrange(num_cols):
            try:
                if starter[i+1][j+1] == 0:
                    diag_prod = None
                else:
                    diag_prod = (arr[i][j] * arr[i+1][j+1])/starter[i+1][j+1]
            except Exception as e:
                diag_prod = None
            diag_prod_array[i][j] = diag_prod
    return diag_prod_array, arr

def reload_starter(num_rows, num_cols):
    return np.ones(shape=(num_rows, num_cols))

def find_max_multiply2(arr, k):
    start = time.time()
    num_rows = len(arr)
    num_cols = len(arr[0])

    starter = reload_starter(num_rows, num_cols)
    max_multiply = - sys.maxint - 1

    if k > math.sqrt(num_rows* num_rows + num_cols * num_cols):
        raise Exception("k has to be less than atleast the diagonal size")

    # We find the products along the rows
    row_prod_array = list(arr)
    for m in xrange(k-1):
        row_prod_array, starter = row_reduce(row_prod_array, starter)

    # we find the product along the columns
    starter = reload_starter(num_rows, num_cols)
    col_prod_array = list(arr)
    for m in xrange(k-1):
        col_prod_array, starter = col_reduce(col_prod_array, starter)

    # we find the product along the diagonals
    starter = reload_starter(num_rows, num_cols)
    diag_prod_array = list(arr)
    for m in xrange(k-1):
        diag_prod_array, starter = diag_reduce(diag_prod_array, starter)

    for i in xrange(num_rows):
        for j in xrange(num_cols):
            if row_prod_array[i][j] > max_multiply:
                max_multiply = row_prod_array[i][j]

    for i in xrange(num_rows):
        for j in xrange(num_cols):
            if col_prod_array[i][j] > max_multiply:
                max_multiply = col_prod_array[i][j]

    for i in xrange(num_rows):
        for j in xrange(num_cols):
            if diag_prod_array[i][j] > max_multiply:
                max_multiply = diag_prod_array[i][j]

    print int(max_multiply)
    print "Time elapsed: " + str(time.time() - start)


# find_max_multiply2(arr2, 3)
find_max_multiply2(arr, 4)

- whalesharky February 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is there any proper solution to the problem other than getting all products?

- Victor February 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes of course, for example, greedy algorithms. you find the maximum value in the matrix, then search for the maximum possible products that contains that maximum value you just found. But since it is greedy algorithms, the answer may not be the best.
another solution, if you know there are at least one row, or column that contains at least k continuous positive number, you can just skip calculate the cell that contains 0 or negative one.

- hiuhchan February 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//
// main.cpp
// Interview
//
//

#include <iostream>

int main(int argc, const char * argv[]) {

// business logic here
int matrix[5][5] = {{1, 2, 0, -1, 4}, {3, 1, 2, 4, 6}, {0, 2, 3, 1, 4}, {1, 3, 2, 0, 7}, {2, 1, 3, 2, 9}};

int input = 2, result = 0;

// print array
std::cout<<"Print array ..."<<std::endl;
for (int i=0; i<sizeof(matrix)/sizeof(matrix[0]); i++) {
for (int j=0; j<sizeof(matrix[i])/sizeof(int); j++) {
std::cout<<matrix[i][j];
std::cout<<"|";
}
std::cout<<std::endl;
}

// search horizontally
std::cout<<"Searching horizontally ..."<<std::endl;
for (int i=0; i<sizeof(matrix)/sizeof(matrix[0]); i++) {
for (int j=0; j+input<=sizeof(matrix[i])/sizeof(int); j++) {
int product = 1;
for (int k=0; k<input; k++) {
std::cout<<matrix[i][j+k];
product = product * matrix[i][j+k];
}
if (product > result) {
result = product;
}
std::cout<<"|";
}
std::cout<<std::endl;
}

// search vertically
std::cout<<"Searching vertically ..."<<std::endl;
for (int i=0; i<sizeof(matrix)/sizeof(matrix[0]); i++) {
for (int j=0; j+input<=sizeof(matrix[i])/sizeof(int); j++) {
int product = 1;
for (int k=0; k<input; k++) {
std::cout<<matrix[j+k][i];
product = product * matrix[j+k][i];
}
if (product > result) {
result = product;
}
std::cout<<"|";
}
std::cout<<std::endl;
}

// search diagonally
std::cout<<"Searching diagonally ..."<<std::endl;
for (int i=0; i<2; i++) {
switch (i) {
case 0:
for (int j=0; j+input<=sizeof(matrix[i])/sizeof(int); j++) {
int product = 1;
for (int k=0; k<input; k++) {
std::cout<<matrix[j+k][j+k];
product = product * matrix[j+k][j+k];
}
if (product > result) {
result = product;
}
std::cout<<"|";
}
break;
case 1:
for (int j=0; j+input<=sizeof(matrix[i])/sizeof(int); j++) {
int product = 1;
for (int k=0; k<input; k++) {
std::cout<<matrix[j+k][sizeof(matrix[j])/sizeof(int)-1-k-j];
product = product * matrix[j+k][sizeof(matrix[j])/sizeof(int)-1-k-j];
}
if (product > result) {
result = product;
}
std::cout<<"|";
}
break;
default:
break;
}

std::cout<<std::endl;
}

std::cout<<"Result: "<<result<<std::endl;
// exit
return 0;
}

- Wahab February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//
//  main.cpp
//  Interview
//
//  Created by Wahab Akhtar on 2/15/15.
//  Copyright (c) 2015 Wahab Akhtar. All rights reserved.
//

#include <iostream>

int main(int argc, const char * argv[]) {
    
    // business logic here
    int matrix[5][5] = {{1, 2, 0, -1, 4}, {3, 1, 2, 4, 6}, {0, 2, 3, 1, 4}, {1, 3, 2, 0, 7}, {2, 1, 3, 2, 9}};
    
    int input = 2, result = 0;
    
    // print array
    std::cout<<"Print array ..."<<std::endl;
    for (int i=0; i<sizeof(matrix)/sizeof(matrix[0]); i++) {
        for (int j=0; j<sizeof(matrix[i])/sizeof(int); j++) {
            std::cout<<matrix[i][j];
            std::cout<<"|";
        }
        std::cout<<std::endl;
    }
    
    // search horizontally
    std::cout<<"Searching horizontally ..."<<std::endl;
    for (int i=0; i<sizeof(matrix)/sizeof(matrix[0]); i++) {
        for (int j=0; j+input<=sizeof(matrix[i])/sizeof(int); j++) {
            int product = 1;
            for (int k=0; k<input; k++) {
                std::cout<<matrix[i][j+k];
                product = product * matrix[i][j+k];
            }
            if (product > result) {
                result = product;
            }
            std::cout<<"|";
        }
        std::cout<<std::endl;
    }
    
    // search vertically
    std::cout<<"Searching vertically ..."<<std::endl;
    for (int i=0; i<sizeof(matrix)/sizeof(matrix[0]); i++) {
        for (int j=0; j+input<=sizeof(matrix[i])/sizeof(int); j++) {
            int product = 1;
            for (int k=0; k<input; k++) {
                std::cout<<matrix[j+k][i];
                product = product * matrix[j+k][i];
            }
            if (product > result) {
                result = product;
            }
            std::cout<<"|";
        }
        std::cout<<std::endl;
    }
    
    // search diagonally
    std::cout<<"Searching diagonally ..."<<std::endl;
    for (int i=0; i<2; i++) {
        switch (i) {
            case 0:
                for (int j=0; j+input<=sizeof(matrix[i])/sizeof(int); j++) {
                    int product = 1;
                    for (int k=0; k<input; k++) {
                        std::cout<<matrix[j+k][j+k];
                        product = product * matrix[j+k][j+k];
                    }
                    if (product > result) {
                        result = product;
                    }
                    std::cout<<"|";
                }
                break;
            case 1:
                for (int j=0; j+input<=sizeof(matrix[i])/sizeof(int); j++) {
                    int product = 1;
                    for (int k=0; k<input; k++) {
                        std::cout<<matrix[j+k][sizeof(matrix[j])/sizeof(int)-1-k-j];
                        product = product * matrix[j+k][sizeof(matrix[j])/sizeof(int)-1-k-j];
                    }
                    if (product > result) {
                        result = product;
                    }
                    std::cout<<"|";
                }
                break;
            default:
                break;
        }
        
        std::cout<<std::endl;
    }
    
    std::cout<<"Result: "<<result<<std::endl;
    // exit
    return 0;
}

- Wahab February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static boolean[][] dpRow,dpCol,dpDiagonal;

	/*
	 * For a given matrix, find the maximum product of k elements. 
	 * The elements can be formed from continuous 4 elements horizontally, 
	 * vertically or diagonally. Eg: For k= 4, the maximum product is (6*4*7*9)
	 *  from the last column, 

		1 2 0 -1 4 
		3 1 2 4 6 
		0 2 3 1 4 
		1 3 2 0 7 
		2 1 3 2 9
	 */	
	//recursion call row and store it in max reeturn max
	public static int findMaxProduct(int[][] matrix,int row,int col,int maxProd){
		if(row>=matrix.length || col>=matrix[0].length){
			return maxProd;
		}
		if(dpRow[row][col] && dpCol[row][col] && dpDiagonal[row][col]){
			return maxProd;
		}
		//check for the row
		int product = 0;
		if(!dpRow[row][col] && col<=matrix[0].length-4){
			product = matrix[row][col]*matrix[row][col+1]*matrix[row][col+2]*matrix[row][col+3];
			dpRow[row][col] = true;
			if(product>maxProd){
				maxProd = product;
			}			
		}
		
		//check for the column		
		if(!dpCol[row][col] && row<=matrix.length-4){
			product = matrix[row][col]*matrix[row+1][col]*matrix[row+2][col]*matrix[row+3][col];
			dpCol[row][col] = true;
			if(product>maxProd){
				maxProd = product;
			}
			
		}
		//check for the diagonal		
		if(!dpDiagonal[row][col] && row<=matrix.length-4 && col<=matrix[0].length-4){
			product = matrix[row][col]*matrix[row+1][col+1]*matrix[row+2][col+2]*matrix[row+3][col+3];
			dpDiagonal[row][col] = true;
			if(product>maxProd){
				maxProd = product;
			}
			
		}
		maxProd = findMaxProduct(matrix, row, col+1, maxProd);
		maxProd = findMaxProduct(matrix, row+1, col, maxProd);
		maxProd = findMaxProduct(matrix, row+1, col+1, maxProd);
		
		return maxProd;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] matrix = {
				{1, 2, 0, -1, 4 },
				{3, 1, 2, 4, 6 },
				{0, 2, 3, 1, 4 },
				{1, 3, 2, 0, 7} ,
				{2, 1, 3, 2, 9}
		};
		dpRow = new boolean[matrix.length][matrix[0].length];
		dpCol = new boolean[matrix.length][matrix[0].length];
		dpDiagonal = new boolean[matrix.length][matrix[0].length];
		System.out.println(findMaxProduct(matrix, 0, 0, Integer.MIN_VALUE));

	}

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

Here is my Java implementation, it's essentially brute force with short-circuiting some calculations if we can.

public static long findGreatestProduct(int[][] matrix, int k) {
        Long max = Long.MIN_VALUE;
        for (int i=0; i < matrix.length; i++) {
            for(int j=0; j < matrix[i].length; j++) {
                for (int x=-1; x <= 1; x+=2)
                    for(int y=-1; y <= 1; y+=2)
                        max = Math.max(max, buildProduct(matrix, i, j, x, y, k, max > 0));
            }
        }
        return max;
    }

    //Utility functions
    private static boolean isWithinRange(int[][] matrix, int r, int c) {
        if (r < 0 || r >= matrix.length) return false;
        return (c >= 0 && c < matrix[r].length);
    }
    private static long buildProduct(int[][]matrix, int r, int c, int x, int y, int move,
                                     boolean shortNeg) {
        assert(Math.abs(x)<=1);
        assert(Math.abs(y)<=1);
        //short-circuit
        if(!isWithinRange(matrix, r,c)) return Long.MIN_VALUE;
        int rBound = r + (y*move);
        int cBound = c + (x*move);
        if (!isWithinRange(matrix, rBound, cBound)) return Long.MIN_VALUE;

        int p = matrix[r][c];
        for (int i = 1; i <= move; i++) {
            if (p <= 0 && shortNeg) return Long.MIN_VALUE;
            p *= matrix[r+y*i][c+x*i];
        }

        return p;
    }

- Anon February 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

How about DP approach? Consider the right bottom cell. The only way it can belong to the maximum product is if it contributes to the maximum product itself. So with regard of matrix boundaries:

Ph = Product of A[i-3..i,j]
Pv = Product of A[i, j-3..j]
Pd = Product of A[i-3..i,j-3..j]
A[i,j] = max(Ph, Pv, Pd)

And BTW, does every coding monkey here seriously expect people to read truck load of code you manage to dump here? Get real people! You need to come up with an algorithm, not 3 pages of something that will take all evening to figure out.

- Coding Owl February 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package Amazon;

/**
 *
 * @author Viral
 */
public class MatrixMaxMultiplication {

    
    private int find(int[][] array,  int x, int y, int n) {
        int max = Integer.MIN_VALUE;
    
          if (y+n > array.length && x+n > array[y].length) {
                return max;
          }
    
        boolean checkDiagonal = true;
        if (array.length - y >= n) {
            max =1;
            for (int i =y; i<n+y;i++){
                max = max *array[i][x] ;
            }
            
        } else {
            checkDiagonal = false;
        }

        if (array[y].length - x >= n) {
            int val =1;
            for (int i =x; i<n+x;i++){
                val = val *array[y][i] ;
            }
            max = Math.max(max, val);
        } else {
            checkDiagonal = false;
        }
        
        if (checkDiagonal) {
            int val = 1;
            for (int i=y,j=x; i<n+y;i++,j++){
                val = val *array[i][j] ;
            }
            if (val > max) {
                max = val;
            }
        }
        
// move the x position
        

        return max;
    }
    
    public void doit(int[][] array, int n) {
        int max = Integer.MIN_VALUE;

// move the y position
        for (int y = 0; y < (array.length); y++) {
            for (int x = 0; x < (array.length); x++) {
 
               max = Math.max(max, find(array, x, y,6));  
            }   
            
        }
        
        System.out.println(max);
   }

    public static void main(String[] args) {
        int[][] array = {
            {1, 2, 0, -1 ,4},
            {3, 1, 2, 4, 6},
            {0, 6, 3, 1, 4},
            {1, 3, 50, 0, 7},
            {2, 0, 3, 2, 9}};
            
        MatrixMaxMultiplication cl = new MatrixMaxMultiplication();
        cl.doit(array,3);
    }
    

}

- viralsanghavi7 February 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Coding owl's suggestions is the best.. try providing a readable algorithm. even a monkey can write a peice of code. Having said that, I again have to agree with coding owl, DP is the only approach "I" can think of:

1. create a matrix with n*m column for every element in the matrix
2. the number of rows will be the number k from the question
3. start making entries: for every entry do the following
a) for first row:
1. compute values from all possible directions.
2.store the max product and the direction u pick
b) for rows other than first row:
1. compute values from direction indicated in previous step. if its up/down, u can check only for biggest of two values, go up or down etc
2.store the max product and the direction u pick

so if u have already computed a value, u can reuse. If any one can make it better please post you answers

- catchclrs June 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Test

- Nitin Gupta February 14, 2015 | 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