Amazon Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
In this code, don't you think the same cell's value has been considered twice(Once during row array and another during column array). I think that instead of "int val = rows[i] * col[j]", it should be
int val =(rows[i] * col[j])/arr[i][j]. Then in this case also we need to handle delived by zero scenario. Since we just bother for sign, instead of deviding, we can multiply arr[i][j].
Please let me know if my understanding is correct.
Thanks for pointing out the mistake. I think what you said is correct. Either we should divide or multiply to get the proper sign.
One easier solution is to calculate the multiplication of all elements in i'th rows(int[] rowMul) and j'th columns(int[] colMul). So total 3+4=7 multiplication.
Later just go through the matrix to do
for(int i=0; i<rows; i++)
for(int j=0; j<columns; j++)
{
if(rowMul[i]*colMul[j] > 0)
matrix[i][j] = 1;
else if(rowMul[i]*colMul[j] < 0)
matrix[i][j] = -1;
else
matrix[i][j] = 0;
}
/*
Running time is terrible
*/
Original[n][n];
result[n+1][n+1];
for(row =0; row < NumOfRow; row++)
{
result[row][n] = 1;
for(col=0;col<NumOfColumn;col++)
{
result[row][n] = result[row][n] * Original[row][col] //last row cell
result[n][col] = result[row][n] * Original[row][col] //last col cell
}
}
for(row =0; row < NumOfRow; row++)
{
for(col=0;col<NumOfColumn;col++)
{
if(result[row][n] * result[n][col] > 0)
{
result[row][col] = 1;
}
else if (result[row][n] * result[n][col] == 0)
{
result[row][col] = 0;
}
else
{
result[row][col] = -1;
}
}
}
This cpp code worked perfectly fine with no error:
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
signed int a[10][10],b[10][10],m,p;
signed int i,j,k,l;
cout<<"Enter the array value"<<endl;
for(i=1;i<=3;i++)
{for(j=1;j<=4;j++)
{cin>>a[i][j];
}
}
for(i=1;i<=3;i++)
{for(j=1;j<=4;j++)
{cout<<a[i][j];
}cout<<endl;
}cout<<endl;
for(i=1;i<=3;i++)
{for(j=1;j<=4;j++)
{ m=1;p=1;
for(k=1;k<=4;k++)
{m*=a[i][k];
}
for(l=1;l<=3;l++)
{p*=a[l][j];
}
if((m*p)==0)
{b[i][j]=0;
}
else if((m*p)>0)
{b[i][j]=1;
}
else if((m*p)<0)
{b[i][j]=-1;
}
}
}
cout<<"Final result: "<<endl;
for(i=1;i<=3;i++)
{for(j=1;j<=4;j++)
{cout<<b[i][j];
}cout<<endl;
}
getch();
}
I think my below code is a partial dynamic program
I have used a dictionary to store the values of column. multiplying the column values will take at most len(column) and after that theta(1) amortized running time.
And the inner for loop will be skipped if the multiplication of row values = 0.
If I'm wrong or any other improvement can be done for the efficiency, pls post it!
#!usr/bin/python3
col_dict = {}
def row_calculation(row,number):
total = 1
for elem in row:
total = elem * total
return total
def column_calculation(column,number):
if number not in col_dict:
total =1
for elem in column:
total = elem * total
col_dict[number] = total
return total
else:
return col_dict[number]
def main():
matrix_list = [[1,2,3,1],[1,0,-1,2],[-1,1,1,1]]
new_matrix = []
row_length = len(matrix_list)
column_length = len(matrix_list[0])
for row in range(len(matrix_list)):
temp_list = []
row_value = row_calculation(matrix_list[row],row)
if row_value is 0:
temp_list = [0]*column_length
new_matrix.append(temp_list)
continue
for elem in range(len(matrix_list[row])):
column_list = [matrix_list[col_number][elem] for col_number in range(row_length)]
column_value = column_calculation(column_list,elem)
if (column_value * row_value) > 0:
temp_list.append(1)
elif (column_value * row_value) < 0:
temp_list.append(-1)
else:
temp_list.append(0)
new_matrix.append(temp_list)
print(new_matrix)
if __name__ == "__main__" : main()
O(N) - Using TreeMap
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
public class matrixMul {
public static void main(String[] args) {
TreeMap<String,Integer> hm = new TreeMap<String,Integer>();
TreeMap<String,Integer> tm1 = new TreeMap<String,Integer>();
TreeMap<String,Integer> tm2 = new TreeMap<String,Integer>();
hm.put("1,1",1); hm.put("2,1",1); hm.put("3,1",-1);
hm.put("1,2",2); hm.put("2,2",0); hm.put("3,2",1);
hm.put("1,3",3); hm.put("2,3",-1); hm.put("3,3",1);
hm.put("1,4",1); hm.put("2,4",2); hm.put("3,4",1);
Set<Entry<String, Integer>> s = hm.entrySet();
Iterator<Entry<String, Integer>> i = s.iterator();
while(i.hasNext()){
@SuppressWarnings("rawtypes")
Map.Entry he = (Map.Entry)i.next();
String Key = he.getKey().toString();
int Value = (Integer)he.getValue();
String [] sarray = Key.split(",");
if(tm1.containsKey(sarray[0])){
int num = (Integer)tm1.get(sarray[0]);
tm1.put(sarray[0], num*Value);
}
else
tm1.put(sarray[0], Value);
if(tm2.containsKey(sarray[1])){
int num = (Integer)tm2.get(sarray[1]);
tm2.put(sarray[1], num*Value);
}
else
tm2.put(sarray[1], Value);
}
System.out.println(tm1);
System.out.println(tm2);
Set<Entry<String, Integer>> st = hm.entrySet();
Iterator<Entry<String, Integer>> it = st.iterator();
while(it.hasNext()){
@SuppressWarnings("rawtypes")
Map.Entry he = (Map.Entry)it.next();
String Key = he.getKey().toString();
String [] sarray = Key.split(",");
int Value1 = tm1.get(sarray[0]);
int Value2 = tm2.get(sarray[1]);
int Value3 = Value1*Value2;
if(Value3 == 0){
hm.put(Key, 0);
}
else if(Value3 < 0){
hm.put(Key, -1);
}
else{
hm.put(Key, 1);
}
}
System.out.println(hm);
}
}
package code;
public class Matrix {
public static void main(String[] args)
{
int[][] matrix={{1,2,3,1},{1,0,-1,2},{-1,1,1,1}};
int[] row=new int[3];
int[] col=new int[4];
for(int i=0;i<3;i++)
{
row[i]=1;
}
for(int j=0;j<4;j++)
{
col[j]=1;
}
for(int i=0;i<3;i++)
{
for(int j=0;j<4;j++)
{
if(matrix[i][j]<0)
{
if(row[i]!=0)
{
row[i]=-row[i];
}
if(col[j]!=0)
{
col[j]=-col[j];
}
}
else if(matrix[i][j]==0)
{
row[i]=0;
col[j]=0;
}
}
}
/*for(int i=0;i<row.length;i++)
{
System.out.println("row: "+row[i]);
}
for(int j=0;j<col.length;j++)
{
System.out.println("col: "+col[j]);
}*/
int[][] output=new int[row.length][col.length];
for(int i=0;i<row.length;i++)
{
for(int j=0;j<col.length;j++)
{
if(row[i]==0||col[0]==0)
output[i][j]=0;
if((row[i]==col[j])&&(row[i]!=0))
output[i][j]=1;
if((row[i]==-1&&col[j]==1)||(row[i]==1&&col[j]==-1))
{
output[i][j]=-1;
}
}
}
for(int i=0;i<row.length;i++)
{
System.out.println();
for(int j=0;j<col.length;j++)
System.out.print(output[i][j]+" ");
}
}
}
matrix=[[1, 2, 3, 1], [1, 0, -1, 2], [-1, 1, 1, 1]]
def column_multiplication(rows,col_elem):
col_result=1
while rows>0:
col_result=col_result * matrix[rows-1][col_elem]
rows=rows-1
return col_result
def rows_multiplication(col,row_elem):
rows_result=1
while col>0:
rows_result=rows_result * matrix[row_elem][col-1]
col=col-1
return rows_result
def main():
print "Given Matrix : ", matrix
rows=len(matrix)
col=len(matrix[0])
new_matrix=[ [ None for i in range(col) ] for j in range(rows) ]
for row_elem in range(rows):
for col_elem in range(col):
col_result=column_multiplication(rows,col_elem)
rows_result=rows_multiplication(col,row_elem)
if col_result * rows_result == 0:
new_matrix[row_elem][col_elem]= 0
elif col_result * rows_result > 0:
new_matrix[row_elem][col_elem]= 1
elif col_result * rows_result < 0:
new_matrix[row_elem][col_elem]= -1
print "Result Matrix : ", new_matrix
if __name__=="__main__":
main()
static int[][] findMult(int[][] arr)
{
int[][] result = new int[arr.length][arr[0].length];
int mult =1;
for(int i=0; i<arr.length ; i++)
{
for(int j=0; j< arr[i].length ; j++)
{
for(int k=0; k< arr.length ; k++)
{
mult *= arr[k][j];
}
for(int k=0; k< arr.length ; k++)
{
mult *= arr[i][k];
}
if(mult > 0)
{
result[i][j] = 1;
}else if(mult < 0)
{
result[i][j] = -1;
}else
{
result[i][j] = 0;
}
mult = 1;
}
}
return result;
}
matrix=[[1, 2, 3, 1], [1, 0, -1, 2], [-1, 1, 1, 1]]
def column_multiplication(rows,col_elem):
col_result=1
while rows>0:
col_result=col_result * matrix[rows-1][col_elem]
rows=rows-1
return col_result
def rows_multiplication(col,row_elem):
rows_result=1
while col>0:
rows_result=rows_result * matrix[row_elem][col-1]
col=col-1
return rows_result
def main():
print "\nGiven Matrix : ", matrix, "\n"
rows=len(matrix)
col=len(matrix[0])
new_matrix=[ [ None for i in range(col) ] for j in range(rows) ]
for row_elem in range(rows):
for col_elem in range(col):
col_result=column_multiplication(rows,col_elem)
rows_result=rows_multiplication(col,row_elem)
if col_result * rows_result == 0:
new_matrix[row_elem][col_elem]= 0
elif col_result * rows_result > 0:
new_matrix[row_elem][col_elem]= 1
elif col_result * rows_result < 0:
new_matrix[row_elem][col_elem]= -1
print "Result Matrix : ", new_matrix
if __name__=="__main__":
main()
public static int[][] computeIndicators(int[][] inputMatrix){
int rows = inputMatrix.length;
int cols = inputMatrix[0].length;
int[] rowIndicators = new int[rows];
int[] colIndicators = new int[cols];
int[][] outputMatrix = new int[rows][cols];
for(int i = 0; i < rows; i++){
int rowIndicator = 1;
for(int j = 0; j < cols; j++){
rowIndicator *= inputMatrix[i][j];
}
if(rowIndicator > 0) rowIndicators[i] = 1;
else if(rowIndicator == 0) rowIndicators[i] = 0;
else rowIndicators[i] = -1;
}
for(int i = 0; i < cols; i++){
int colIndicator = 1;
for(int j = 0; j < rows; j++){
colIndicator *= inputMatrix[j][i];
}
if(colIndicator > 0) colIndicators[i] = 1;
else if(colIndicator == 0) colIndicators[i] = 0;
else colIndicators[i] = -1;
}
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
outputMatrix[i][j] = rowIndicators[i] * colIndicators[j];
}
}
return outputMatrix;
}
public static int[][] getMatrix01(int[][] a) {
int r = a.length;
int c = a[0].length;
int[][] b = new int[r][c];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
int result = 1;
for (int i2 = 0; i2 < r; i2++) {
result *= a[i2][j];
}
for (int j2 = 0; j2 < c; j2++) {
result *= a[i][j2];
}
if (result > 0) {
b[i][j] = 1;
} else if (result < 0) {
b[i][j] = -1;
} else {
b[i][j] = 0;
}
}
}
return b;
}
def pos_neg_matrix(A):
M,N = len(A), len(A[0])
rnegs, cnegs = M*[0], N*[0]
rzeros, czeros = M*[False], N*[False]
B = [N*[0] for i in range(M)]
######################################
for r in range(M):
for c in range(N):
rzeros[r] |= A[r][c]==0
czeros[c] |= A[r][c]==0
rnegs[r] += A[r][c]<0
cnegs[c] += A[r][c]<0
######################################
for r in range(M):
if rzeros[r]:
continue
for c in range(N):
if not czeros[c]:
negcount = rnegs[r] + cnegs[c] - (A[r][c]<0)
B[r][c] = 1 - 2*(negcount%2)
return B # in total M*N running time
##########################################
if __name__ =='__main__':
A = [[1, 2, 3, 1],
[1, 0, -1, 2],
[-1, 1, 1, 1]]
print pos_neg_matrix(A)
# [[-1, 0, -1, 1], [0, 0, 0, 0], [-1, 0, 1, -1]]
We can solve this problem by storing the product of all rows in a rows array and then the product of all column in a column array. Then, we will be simple multiplication of the rows and column.
Code:
- Coder February 08, 2014