Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
that was what I had in my mind before. But the re-multiply logic will definitely slow you down in the interview session.
Division is much slower than multiplications, so it's unclear if it would perform better.
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);
}
}
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;
}
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));
}
}
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.
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)
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.
//
// 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;
}
//
// 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;
}
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));
}
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;
}
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.
/*
* 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);
}
}
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
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.
- Skor February 13, 2015Say 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