Amazon Interview Question
Quality Assurance EngineersCountry: India
Interview Type: Written Test
In Python:
def sumRowCol(matrixlist):
sumRowList = [sum(x) for x in matrixlist]
sumColList = [sum(x) for x in zip(*matrixlist)]
return sumRowList, sumColList
listSumRow, listSumCol = sumRowCol([[3,-5,10],[6,2,-1],[2,6,1]])
print 'Row num:{} has maximum value {}\nRow num:{} has minimum value {}'.format(listSumRow.index(max(listSumRow)),max(listSumRow),listSumRow.index(min(listSumRow)),min(listSumRow))
print 'Col num:{} has maximum value {}\nCol num:{} has minimum value {}\n'.format(listSumCol.index(max(listSumCol)),max(listSumCol),listSumCol.index(min(listSumCol)),min(listSumCol))
Concept : In this example, calculate the 6 entities, 3 row sums, and 3 column sums. Store this in a dictionary with key as "sum value" and value as "index of row/col" . Now pick up all the keys and find min/max of these - and then just display then corresponding values along with the keys.
When I say dictionary I am *thinking* python - you could do the same with associative arrays/hash-maps
package vrts.common.test.deepak;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Matrix {
private int matrix[][] = {
{1,22,2,34,4},
{1,2,342,34,4},
{11,2,2,34,4},
{1,2,2,34,34},
{1,221,2,34,4},
{11,2,12,34,24}
};
private List<IndexSumPair> rowSum = new ArrayList<IndexSumPair>();
private List<IndexSumPair> colSum = new ArrayList<IndexSumPair>();
class IndexSumPair implements Comparable<IndexSumPair> {
private int index;
private int sum;
public IndexSumPair(int index, int sum) {
this.index = index;
this.sum = sum;
}
/**
* @return the sum
*/
public int getSum() {
return sum;
}
/**
* @param sum
* the sum to set
*/
public void setSum(int sum) {
this.sum = sum;
}
/**
* @return the index
*/
public int getIndex() {
return index;
}
@Override
public int compareTo(IndexSumPair object) {
if (object != null) {
return object.sum > sum ? -1 : 1;
}
return 0;
}
}
void updateColSum(int row,int col){
if(col>=colSum.size()){
colSum.add(new IndexSumPair(col,matrix[row][col]));
return;
}
IndexSumPair colValue = colSum.get(col);
colValue.setSum(colValue.getSum()+ matrix[row][col]);
}
void updateRowSum(int row,int col){
if(row>=rowSum.size()){
rowSum.add(new IndexSumPair(row,matrix[row][col]));
return;
}
IndexSumPair rowValue = rowSum.get(row);
rowValue.setSum(rowValue.getSum()+ matrix[row][col]);
}
void printValues(){
Collections.sort(rowSum);
System.out.println("Max row:"+rowSum.get(rowSum.size()-1).getIndex() + " Sum "+rowSum.get(rowSum.size()-1).getSum());
System.out.println("Min row:"+rowSum.get(0).getIndex() + " Sum "+rowSum.get(0).getSum());
System.out.println("Max Col:"+colSum.get(colSum.size()-1).getIndex() + " Sum "+colSum.get(colSum.size()-1).getSum());
System.out.println("Min Col:"+colSum.get(0).getIndex() + " Sum "+colSum.get(0).getSum());
}
void processMatrix(){
for(int row=0; row<matrix.length;row++){
for(int col=0; col<matrix[row].length;col++){
updateColSum(row,col);
updateRowSum(row,col);
}
}
printValues();
}
public static void main(String[] args) {
new Matrix().processMatrix();
}
}
public static void main(String[] args) {
int[][] data = new int [3][3];
data[0][0] = 3;
data[0][1] = -5;
data[0][2] = 10;
data[1][0] = 6;
data[1][1] = 2;
data[1][2] = -1;
data[2][0] = 2;
data[2][1] = 6;
data[2][2] = 1;
Map<Integer, Integer> rows = new TreeMap<Integer, Integer>();
Map<Integer, Integer> cols = new TreeMap<Integer, Integer>();
for (int i = 0; i < data.length; i++) {
for (int j = 0; j < data[i].length; j++) {
if (!rows.containsKey(i)) {
rows.put(i, data[i][j]);
} else {
int val = data[i][j] + rows.get(i);
rows.put(i, val);
}
if (!cols.containsKey(i)) {
cols.put(i, data[j][i]);
} else {
int val = data[j][i] + cols.get(i);
cols.put(i, val);
}
}
}
sortMap(rows);
sortMap(cols);
System.out.println(String.format("Min Row sum %d and Max row sum %d", rows.get(0), rows.get(rows.size() -1)));
System.out.println(String.format("Min Column sum %d and Max Column sum %d", cols.get(0), cols.get(cols.size() -1)));
}
private static void sortMap(Map<Integer, Integer> map) {
for (int i = 0; i < map.size(); i++) {
for (int j = i + 1; j < map.size(); j++) {
int temp = map.get(i);
if (map.get(j) < temp) {
map.put(i, map.get(j));
map.put(j, temp);
}
}
}
}
public static void main(String[] args) {
int[][] data = new int [3][3];
data[0][0] = 3;
data[0][1] = -5;
data[0][2] = 10;
data[1][0] = 6;
data[1][1] = 2;
data[1][2] = -1;
data[2][0] = 2;
data[2][1] = 6;
data[2][2] = 1;
Map<Integer, Integer> rows = new HashMap<Integer, Integer>();
Map<Integer, Integer> cols = new HashMap<Integer, Integer>();
for (int i = 0; i < data.length; i++) {
for (int j = 0; j < data[i].length; j++) {
if (!rows.containsKey(i)) {
rows.put(i, data[i][j]);
} else {
int val = data[i][j] + rows.get(i);
rows.put(i, val);
}
if (!cols.containsKey(i)) {
cols.put(i, data[j][i]);
} else {
int val = data[j][i] + cols.get(i);
cols.put(i, val);
}
}
}
System.out.println(String.format("The Row: %d has the Min Sum %d", getMinIndex(rows), rows.get(getMinIndex(rows))));
System.out.println(String.format("The Col: %d has the Min Sum %d", getMinIndex(cols), cols.get(getMinIndex(cols))));
System.out.println(String.format("The Row: %d has the Max Sum %d", getMaxIndex(rows), rows.get(getMaxIndex(rows))));
System.out.println(String.format("The Col: %d has the Max Sum %d", getMaxIndex(cols), cols.get(getMaxIndex(cols))));
}
private static int getMaxIndex(Map<Integer, Integer> map) {
Set<Entry<Integer, Integer>> entrySet = map.entrySet();
int max = entrySet.iterator().next().getValue();
int index = entrySet.iterator().next().getKey();
for (Entry<Integer, Integer> entry : entrySet) {
if (entry.getValue() > max) {
max = entry.getValue();
index = entry.getKey();
}
}
return index;
}
private static int getMinIndex(Map<Integer, Integer> map) {
Set<Entry<Integer, Integer>> entrySet = map.entrySet();
int min = entrySet.iterator().next().getValue();
int index = entrySet.iterator().next().getKey();
for (Entry<Integer, Integer> entry : entrySet) {
if (entry.getValue() < min) {
min = entry.getValue();
index = entry.getKey();
}
}
return index;
}
Displays row number OR column number having the maximum sum and the minimum sum.
public int minmaxSum(int[][] matrix) {
int[] sums = new int[6];
int min = Integer.MAX_VALUE;
String imin = null;
int max = Integer.MIN_VALUE;
String imax = null;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
sums[i] += matrix[i][j];
sums[3 + i] += matrix[j][i];
}
int tmin = sums[i] < sums[3 + i] ? sums[i] : sums[3 + i];
int tmax = sums[i] > sums[3 + i] ? sums[i] : sums[3 + i];
if (tmin < min) {
min = tmin;
imin = sums[i] == tmin ? "Row " + i : "Column " + i;
}
if (tmax > max) {
max = tmax;
imax = sums[i] == tmax ? "Row " + i : "Column " + i;
}
}
System.out.println("Max value: " + max + " in " + imax);
System.out.println("Min value: " + min + " in " + imin);
return 0;
}
Keep it simple and this should work with any size matrix
public static void getMaxMinFromMatrix(int[][] m){
int sum[] = new int[m.length + m[0].length];
int maxIndex = 0;
int minIndex = 0;
for(int i = 0; i < m.length; i++){
for (int j = 0; j< m[i].length; j++){
sum[i] += m[i][j];
sum[m.length+j] += m[i][j];
}
if(sum[i] > sum[maxIndex])
{
maxIndex = i;
}
else
{
if(sum[i]<sum[minIndex])
{
minIndex = i;
}
}
}
for(int k = m.length; k < (m.length + m[0].length); k++){
if(sum[k] > sum[maxIndex])
{
maxIndex = k;
}
else
{
if(sum[k]<sum[minIndex])
{
minIndex = k;
}
}
}
System.out.println("Max sum is " + sum[maxIndex] + (maxIndex>m.length-1 ? " at column " :" at row ") +
(maxIndex>m.length-1 ? (maxIndex-(m.length-1)) : (maxIndex+1)));
System.out.println("Min sum is " + sum[minIndex] + (minIndex>m.length-1 ? " at column " :" at row ") +
(minIndex>m.length-1 ? (minIndex-(m.length-1)) : (minIndex+1)));
}
- Anonymous January 07, 2014