Amazon Interview Question SDE-2s
Country: India
Interview Type: Written Test
c++, implementation
unsigned int getMaxDecialIndex(vector<vector<int>> matrix) {
unsigned int maxIndex, i, j;
if (matrix.size() == 0) return 0;
maxIndex = 0;
for (i = 1; i < matrix.size(); i++) {
for (j = 0; j < matrix[i].size(); j++) {
if (matrix[maxIndex][j] == matrix[i][j]) continue;
if (matrix[i][j] == 1) {
maxIndex = i;
}
break;
}
}
return maxIndex + 1;
}
is there any other way to find without converting the rows into decimal and maximum.. i expect solutions other than this
int max = 0;
for (int i = 0; i < A.length; i++) {
int tmp = 0;
for (int j = 0; j < A[0].length; j++) {
tmp |= (A[i][j] << (A[0].length - 1 - j));
}
if (tmp > max) {
max = tmp;
}
}
#include <iostream>
#include <queue>
using namespace std;
int arr[4][4]={{1,0,0,0},{1,0,0,0},{1,0,0,0},{1,0,0,0}};
int main ()
{
queue<int> myqueue,copyqueue;
int val=0,cnt=0,res;
for (int i=0; i<4; ++i) { myqueue.push(i) ; copyqueue.push(i) ; }
cnt=myqueue.size();
while (!myqueue.empty())
{
if(myqueue.size()==1||val==4){
break;
}
copyqueue=myqueue;
for(int i=0;i<cnt;i++)
{
res=myqueue.front();
if(arr[res][val]==0)
{
myqueue.pop();
}
else
{
myqueue.pop();
myqueue.push(res);
}
}
if(myqueue.empty()){
myqueue=copyqueue;
}
val++;
cnt=myqueue.size();
}
if(myqueue.size()==4){
cout << "All are equal" << endl;
return 0;
}
while(myqueue.size()!=0)
{
res=myqueue.front();
myqueue.pop();
cout << "Final Result : " << res << endl;
}
return 0;
}
#include <iostream>
#include <queue>
using namespace std;
int arr[4][4]={{1,0,0,0},{1,0,0,0},{1,0,0,0},{1,0,0,0}};
int main ()
{
queue<int> myqueue,copyqueue;
int val=0,cnt=0,res;
for (int i=0; i<4; ++i) { myqueue.push(i) ; copyqueue.push(i) ; }
cnt=myqueue.size();
while (!myqueue.empty())
{
if(myqueue.size()==1||val==4){
break;
}
copyqueue=myqueue;
for(int i=0;i<cnt;i++)
{
res=myqueue.front();
if(arr[res][val]==0)
{
myqueue.pop();
}
else
{
myqueue.pop();
myqueue.push(res);
}
}
if(myqueue.empty()){
myqueue=copyqueue;
}
val++;
cnt=myqueue.size();
}
if(myqueue.size()==4){
cout << "All are equal" << endl;
return 0;
}
while(myqueue.size()!=0)
{
res=myqueue.front();
myqueue.pop();
cout << "Final Result : " << res << endl;
}
return 0;
}
My implementation is equivalent to o(n). I scan column wise, and eliminate rows in next scan, which have zeros in that column. Read through the code to get idea.
int find_max(int arr[ARR][ARR]){
int j,i;
int index=0,oldindex;
bool flag=0;
float ret;
/* Start Columnwise, where you find 1,0 make that bit set/reset in index.
* Go through this till only 1 bit is set in index or you go through all the loop.
* Special conditions,
* 1. We need flag to make sure , we handle initial coloumns with all zeros.
* 2. After first iteration and first one is found ( flag ) , skip the rows where index is zero.
* 3. If index is zero after a column , reset it back to oldindex. i.e. stick with old index data.
* Enable prints to get more insight.
* */
for(j=0;j<ARR;j++){
oldindex = index;
for(i=0;i<ARR;i++){
/* Check if this row can be skipped, after first coloumn and flag set */
if(flag && j>0 && ((index & (0x1<<i))==0)) {
//printf("Skipping this row %d \n",i);
continue;
}
//TODO: Can be optimized
/* Set/Reset bit in index based on arr[i][j] */
if(arr[i][j]==1){
flag=1;
index |= 0x1 << i;
} else{
index &= ~(0x1 << i);
}
//printf("index = %d\n",index);
}
/* If index is 0 , use old index. This is needed to make sure , index values are unaffected by zero in same column. */
if(index==0) index=oldindex;
/* Check if index is perfect power of two, to break */
if(flag && (index & (index-1)) == 0){
//printf("Done\n");
break;
}
}
/* Return the row number , from index. Basically finding x in , 2^x = index*/
ret=log(index)/log(2);
//printf("only match left, index = %d\n",(int)ret);
return (int)ret;
}
Start column wise and eliminate rows with zeros.
int find_max(int arr[ARR][ARR]){
int j,i;
int index=0,oldindex;
bool flag=0;
float ret;
/* Start Columnwise, where you find 1,0 make that bit set/reset in index.
* Go through this till only 1 bit is set in index or you go through all the loop.
* Special conditions,
* 1. We need flag to make sure , we handle initial coloumns with all zeros.
* 2. After first iteration and first one is found ( flag ) , skip the rows where index is zero.
* 3. If index is zero after a column , reset it back to oldindex. i.e. stick with old index data.
* Enable prints to get more insight.
* */
for(j=0;j<ARR;j++){
oldindex = index;
for(i=0;i<ARR;i++){
/* Check if this row can be skipped, after first coloumn and flag set */
if(flag && j>0 && ((index & (0x1<<i))==0)) {
//printf("Skipping this row %d \n",i);
continue;
}
//TODO: Can be optimized
/* Set/Reset bit in index based on arr[i][j] */
if(arr[i][j]==1){
flag=1;
index |= 0x1 << i;
} else{
index &= ~(0x1 << i);
}
//printf("index = %d\n",index);
}
/* If index is 0 , use old index. This is needed to make sure , index values are unaffected by zero in same column. */
if(index==0) index=oldindex;
/* Check if index is perfect power of two, to break */
if(flag && (index & (index-1)) == 0){
//printf("Done\n");
break;
}
}
/* Return the row number , from index. Basically finding x in , 2^x = index*/
ret=log(index)/log(2);
//printf("only match left, index = %d\n",(int)ret);
return (int)ret;
}
My implementation is equivalent to o(n). I scan column wise, and eliminate rows in next scan, which have zeros in that column. Read through the code to get idea.
int find_max(int arr[ARR][ARR]){
int j,i;
int index=0,oldindex;
bool flag=0;
float ret;
/* Start Columnwise, where you find 1,0 make that bit set/reset in index.
* Go through this till only 1 bit is set in index or you go through all the loop.
* Special conditions,
* 1. We need flag to make sure , we handle initial coloumns with all zeros.
* 2. After first iteration and first one is found ( flag ) , skip the rows where index is zero.
* 3. If index is zero after a column , reset it back to oldindex. i.e. stick with old index data.
* Enable prints to get more insight.
* */
for(j=0;j<ARR;j++){
oldindex = index;
for(i=0;i<ARR;i++){
/* Check if this row can be skipped, after first coloumn and flag set */
if(flag && j>0 && ((index & (0x1<<i))==0)) {
//printf("Skipping this row %d \n",i);
continue;
}
//TODO: Can be optimized
/* Set/Reset bit in index based on arr[i][j] */
if(arr[i][j]==1){
flag=1;
index |= 0x1 << i;
} else{
index &= ~(0x1 << i);
}
//printf("index = %d\n",index);
}
/* If index is 0 , use old index. This is needed to make sure , index values are unaffected by zero in same column. */
if(index==0) index=oldindex;
/* Check if index is perfect power of two, to break */
if(flag && (index & (index-1)) == 0){
//printf("Done\n");
break;
}
}
/* Return the row number , from index. Basically finding x in , 2^x = index*/
ret=log(index)/log(2);
//printf("only match left, index = %d\n",(int)ret);
return (int)ret;
}
iterate all columns and eliminate rows with '0', worst case O(n^2)
public int findMaximumDecimal(int[][] array) {
List<Integer> prevIndexes = new ArrayList<>(array.length);
List<Integer> allIndexes = new ArrayList<>(array.length);
// filter first column
int column = 0;
for(int row = 0; row < array.length; row++) {
if (array[row][column] == 1) {
prevIndexes.add(row);
}
allIndexes.add(row);
}
// filter other columns
for(column = 1; column < array.length; column++) {
if (prevIndexes.isEmpty()) {
prevIndexes = allIndexes;
}
List<Integer> nextIndexes = new ArrayList<>(array.length);
for (int row : prevIndexes) {
if (array[row][column] == 1) {
nextIndexes.add(row);
}
}
if (nextIndexes.isEmpty() && !prevIndexes.isEmpty()) {
// return any solution from previous step
return prevIndexes.get(0);
}
if (nextIndexes.size() == 1) {
// return only one solution from current step
return nextIndexes.get(0);
}
prevIndexes = nextIndexes;
}
return prevIndexes.isEmpty() ? 0 : prevIndexes.get(0);
}
Couldn't this be done just by traversing rows keeping index of max row at every iteration, without conversion to decimal, just by comparing?
public static int getMaxDecialIndex(int[][] matrix) {
if (matrix.length == 0) return -1;
int maxRowIdx = 0;
for (int r = 1; r<matrix.length; r++) {
int[] currRow = matrix[r];
if (compare(matrix[maxRowIdx], currRow) < 0 ) {
maxRowIdx = r;
}
}
return maxRowIdx;
}
private static int compare(int[] first, int[] second) {
for (int c = 0; c<first.length; c++) {
if (first[c] > second[c]) {
return 1;
} else if (first[c] < second[c]){
return -1;
}
}
return 0;
}
Complexity is O(m*n)
public static int getRowWithMaximumDecimal(int[][] twoDarray){
if(twoDarray.length==0)
throw new IllegalArgumentException("Invalid Array");
int max=0;
int maxRow = 0;
for(int i=0; i<twoDarray.length;i++){
int[] row = twoDarray[i];
int dec=0;
System.out.println("Computing Decimal value for Row "+i);
for(int j=0; j<row.length; j++){
dec = (int) (dec+(row[j]*Math.pow(2, (row.length-1)-j)));
}
System.out.println("Dec: "+dec);
if(dec>max){
max=dec;
maxRow=i;
}
}
return maxRow;
}
public static int getRowWithMaximumDecimal(int[][] twoDarray){
if(twoDarray.length==0)
throw new IllegalArgumentException("Invalid Array");
int max=0;
int maxRow = 0;
for(int i=0; i<twoDarray.length;i++){
int[] row = twoDarray[i];
int dec=0;
System.out.println("Computing Decimal value for Row "+i);
for(int j=0; j<row.length; j++){
dec = (int) (dec+(row[j]*Math.pow(2, (row.length-1)-j)));
}
System.out.println("Dec: "+dec);
if(dec>max){
max=dec;
maxRow=i;
}
}
return maxRow;
}
/**
* Created by akhil on 12/13/2015.
*/
public class RowWithMaxVal {
public static int getmaxValRow(int[][] mat) {
int max = 0;
int rowNo = 0;
int row = mat.length;
int col = mat[0].length;
int temp = 0;
int k;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
k = col - j;
temp += mat[i][j] * 2 ^ k;
}
if (temp > max) {
max = temp;
rowNo = i;
}
temp = 0;
}
System.out.print(" max is " + max);
return rowNo;
}
public static int getMax(int[][] mat) {
int max = 0;
int row = mat.length;
int col = mat[0].length;
int temp = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.println(" to " + mat[i][j]);
int t = mat[i][j] << col - 1 - j;
System.out.println(" now " + t);
temp |= t;
System.out.println(" final" + temp);
}
}
return 0;
}
public static void main(String args[]) {
int[][] mat = {{0, 1, 0},
{1, 1, 0},
{1, 0, 1}
};
//getMax(mat);
System.out.println("--" + getmaxValRow(mat));
}
}
I have done both approaches:
Say, we have a n X m matrix
1. row-wise: converting row to decimal value and then compare it with prev. max => O(n + m)
2. col-wise: for each column, find the rows that have 1's for that specific col. intersect it with the previously found one (prev. col means a col with higher order). I guess, the complexity is O(m * n)
import math
def bin2Dec(xs):
xl = len(xs)
sum = 0
for i,v in enumerate(xs):
if v == 1:
sum += math.pow(2, xl-1-i)
return sum
def maxRow(xss):
local_max = 0
max_row = -1
for r,xs in enumerate(xss):
local_sum = bin2Dec(xs)
if local_sum > local_max:
local_max = local_sum
max_row = r
print(max_row)
def maxByCols(xss):
rL = len(xss)
cL = len(xss[0])
max_row = -1
upperLayer = set()
lowerLayer = set()
for c in range(cL):
lowerLayer = set()
for r in range(rL):
if xss[r][c] == 1:
lowerLayer.add(r)
if len(upperLayer) == 0:
upperLayer = lowerLayer
else:
z = upperLayer.intersection(lowerLayer)
if len(z):
upperLayer = z
print(upperLayer)
a = [[1,1 ,0,0],[0,1,1,0],[1,1,1,1],[1,0,1,1],[1,1,1,0]]
maxRow(a)
maxByCols(a)
Both of them works!!!
public int FindRow(int[,] a)
{
int[] rows = new int[a.GetLength(0)];
int pow = 1;
int maxIndex = -1;
for (int j = a.GetLength(1) - 1; j >= 0; j--)
{
maxIndex = 0;
for (int i = 0; i < a.GetLength(0); i++)
{
rows[i] += a[i, j] * pow;
if (rows[i] > rows[maxIndex])
maxIndex = i;
}
pow *= 2;
}
return maxIndex + 1;
}
column wise greedy alg
1. each column we have winners
(those with 1s if there are some with 0; otherwise, everyone is a winner if all 1 or all 0)
2. winners carry to next round (column) and only the winners are competing in the new column
3. whoever left in the pool is the winner
Time complexity should be O(n*m) - worst case, but average case might be much better.
int maxDecimal(int a[][], int n, int m)
{
vector<int> win(n); // initially, we have all candidates
iota(win.begin(), win.end(), 0); // add 0, 1, ..., n-1 to the winner pool
for (int j = 0; j < m; j++) {
vector<int> t;
for (auto i : win) // winner carried to next round
if (a[i][j] == 1) t.push_back(i);
if (t.size() != 0) win.swap(t); // new winners
}
return win[0];
}
column wise greedy alg
1. each column we have winners
(those with 1s if there are some with 0; otherwise, everyone is a winner if all 1 or all 0)
2. winners carry to next column and only the winners are competing in the new column
3. whoever left in the pool is the winner
Time complexity should be O(n*m) - worst case, but average case might be much better.
int maxDecimal(int a[][], int n, int m)
{
vector<int> win(n); // initially, we have all candidates
iota(win.begin(), win.end(), 0); // add 0, 1, ..., n-1 to the winner pool
for (int j = 0; j < m; j++) {
vector<int> t;
for (auto i : win) // winner carried to next round
if (a[i][j] == 1) t.push_back(i);
if (t.size() != 0) win.swap(t); // new winners
}
return win[0];
}
quite simple task.
O(n).
(the output index is 0-based).
using System;
namespace MaxDecimalFrom2DArray {
class Program {
private static int GetMaxDecimalPerRow( int[,] arr ) {
int maxRes = 0;
int retVal = 0;
int pow = arr.GetLength(1);
for ( int i = 0; i < arr.GetLength(0); i++ ) {
int n = pow;
int res = 0;
for ( int j = 0; j < arr.GetLength(1); j++ ) {
res += (int)( arr[ i, j ] * Math.Pow( 2, --n ) );
}
if ( res > maxRes ) {
maxRes = res;
retVal = i;
}
}
return retVal;
}
static void Main(string[] args)
{
int[,] arr = new int[3,3] { {0,1,0}, {1,1,0}, {1,0,1} };
Console.WriteLine( GetMaxDecimalPerRow( arr ) );
Console.ReadLine();
}
}
}
how can it be O(n^2) ? can you explain?
given an array with n elements, loop in my solution visits each element only once. So, it is O(n).
We can do column wise scan with in each scan eliminating all rows with zero value if there exists at least one 1 in that column
- sameer November 22, 2015