Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
What's the time complexity? Is it less than O(nlogn)? I think it would be O(nlogn) if you used binary search in each row to find the first occurrence of 1.
complexity should be O(max(m, n)). each row at least we need scan once, and for each column, at most we scan once.
Here is the code in java:
public int maxOnesInMatrix(int[][]A, int row, int col){
int count =0;
if(A[0][0]==1){
count = col;
}
else{
for(int i=0; i< row; i++){
if(count==col-1){
break;
}
int oldCount =count;
for(int j= col-oldCount-1; j >=0; j--){
if(A[i][j]==0){
break;
}
count++;
}
}
}
return count;
}
It can be solved by applying binary search.
Here is the solution code..
#include<iostream>
#include<conio.h>
using namespace std;
int arr[5][5]={{1,1,1,1,1},{0,0,0,1,1},{0,1,1,1,1},{0,1,1,1,1},{1,1,1,1,1}};
int scanlist(int arr[][5],int result[],int mid,int count)
{
int curcount=0;
for(int i=0;i<count;i++)
{
if(arr[result[i]][mid]==1)
{
result[curcount]=result[i];
curcount++;
}
}
return curcount;
}
int find(int arr[][5],int n)
{
int start=0,end=n-1;
int result[5]={0,1,2,3,4};
int count=5;
while(start<=end)
{
int mid=(start+end)/2;
count=scanlist(arr,result,mid,count);
if(count==0)
{
start=mid+1;
}
else if(count==1)
{
cout<<"Row is "<<result[0]<<endl;
return result[0];
}
else{
end=mid-1;
}
}
int i=0;
while(i<count){
cout<<"Row is "<<result[i]<<endl;
i++;
}
return result[0];
}
int main()
{
find(arr,5);
getch();
return 0;
}
I wrote the next solution in google doc. It uses binary serach so the time complexity is O(m * lg n)
public class Main{
private int leftmostBinSearch(int [] arr, int v, int l, int r){
if(l > r) return -1;
int mid = l + (r - l) / 2;
if(arr[mid] == v){
int leftmost = leftmostBinSearch(arr, v, l, mid - 1);
if(leftmost > -1)
return leftmost;
return mid;
}
if(arr[mid] < v)
leftmostBinSearch(arr, v, mid + 1, r);
if(arr[mid] > v)
leftmostBinSearch(arr, v, l, mid - 1);
return -1;
}
public int findRow(int [][] arr){
if(arr == NULL) return -1;
int rows = arr[0].length;
int maxIndex = -1;
int maxQuantity = -1;
for(int i = 0; i < rows; i++){
int currentQuantity = leftmostBinSearch(arr[i], 1);
if(currentQuantity > maxQuantity){
maxQuantity = currentQuantity;
maxIndex = i;
}
}
return maxIndex;
}
}
I guess this is good enough.
Just a slight improvement:
- when you call leftmostBinSearch within the 'for' loop, first check whether the arr[i][maxQuantity-1] is '1'.
- If yes, only then call leftmostBinSearch and that too by passing it the values: l = 0, r = maxQuantity-1.
- Else, there is no use as we are not interested in anything less than the maxQuantity we already have.
This will improve the performance (although the complexity will still be written as O(m*logn))
Just do a binary search on each column, the row that has the first 1 will be the answer since rows are sorted.
int GetRowWithMaxOne(int[,] matrix)
{
for (int i = 0; i < matrix.GetLength(1); i++)
{
int row = DoBinarySearch(matrix, i, 1, 0, matrix.GetLength(1));
if (row != -1) { return row; }
}
return -1;
}
int DoBinarySearch(int[,] matrix, int i, int low, int high, int x)
{
if (low > high)
{
return -1;
}
int mid = low + (high - low) / 2;
if (matrix[i, mid] == x)
{
return mid;
}
if (matrix[i,mid] > x)
{
return DoBinarySearch(matrix, i, low, mid - 1, x);
}
return DoBinarySearch(matrix, i, mid + 1, high, x);
}
Sorry I made a mistake when I call the DobinarySearch in the first method. Here is the corrected one....all in c#
int GetRowWithMaxOne(int[,] matrix)
{
for (int i = 0; i < matrix.GetLength(1); i++)
{
int row = DoBinarySearch(matrix, i, 0, matrix.GetLength(1),0);
if (row != -1) { return row; }
}
return -1;
}
Sorry I made a mistake when I call the DobinarySearch in the first method. Here is the corrected one....all in c#
int GetRowWithMaxOne(int[,] matrix)
{
for (int i = 0; i < matrix.GetLength(1); i++)
{
int row = DoBinarySearch(matrix, i, 0, matrix.GetLength(1),1);
if (row != -1) { return row; }
}
return -1;
}
int M[1000][1000], row, col ;
cout << "Enter row :";
cin>>row;
cout <<endl << "Enter col :";
cin>>col;
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
cin >> M[i][j];
int count;
count = 0;
for (int i=0; i<=row; i++)
{
count = 0;
for(int j=0; j<=col; j++)
{
if(M[i][j] == 1)
{
count++;
}
}
if(count > col/2)
{
cout << "Row no" << i + 1;
}
}
outer loop binary search. inner loop each line.
1. If at that column, no line is 1, move column cursor left (binary jump).
2. If found one line has 1, remove all lines having 0 on that column until another line having 1 is found.
3. If two lines are found, move column cursor right (binary jump).
4. If there is only one line left, return that line.
5. If there is no column to move, return the first line of the array (all lines having same number of 1s).
<?php
function findMaxOnes($a) {
$nl = count($a);
if ($nl == 0) return null;
$nc = count($a[0]);
$s = 0;
$e = $nc - 1;
while ($s <= $e) {
$founds = 0;
$m = (int)(($s + $e) / 2);
foreach ($a as $i => $l) {
if ($l[$m] == 1) {
if ($founds == 0) {
$founds = 1;
foreach ($a as $j => $ll) {
if ($j == $i) break;
unset($a[$j]);
}
} elseif ($founds == 1) {
$e = $m - 1;
break;
}
} elseif ($founds == 1) {
unset($a[$i]);
}
}
if ($founds == 0) {
$s = $m + 1;
}
if (count($a) == 1) {
return reset($a);
}
}
return reset($a);
}
$a = [[0, 0, 0, 1,],
[1, 1, 1, 1,],
[0, 0, 1, 1,],
[0, 1, 1, 1,],
];
var_dump(findMaxOnes($a));
Java Code
Complexity: O(mlogn)
public class ZerosOnesIn2DArray {
public static void main(String[] args) {
int arr[][] = {{0,0,0,1},{0,1,1,1},{1,1,1,1},{0,0,1,1}};
System.out.println(new ZerosOnesIn2DArray().getMaxOnesRow(arr));
}
public int getMaxOnesRow(int[][] arr){
int row = arr.length;
int col = arr[0].length;
int temp[]=arr[0];
int maxOnesLoc = binarySearch(arr[0], 0, col, 1);
int maxOnesRow = 0;
for(int i=1;i<row;i++){
if(arr[i][maxOnesLoc]==1){
int currOnesLoc = binarySearch(arr[i], 0, maxOnesLoc, 1);
if(currOnesLoc<maxOnesLoc){
maxOnesLoc = currOnesLoc;
maxOnesRow = i;
}
}
}
return maxOnesRow;
}
public int binarySearch(int []arr, int low, int high, int val)
{
if(high<low){
return -1;
}
int mid =(low+high)/2;
int output = 0;
if(arr[mid]<val){
low = mid+1;
output =binarySearch(arr, low, high, val);
}
else if(arr[mid]>val){
high = mid-1;
output =binarySearch(arr, low, high, val);
}
else{
if(mid!=0 && arr[mid-1]==val){
high = mid-1;
output =binarySearch(arr, low, high, val);
}
else{
output = mid;
}
}
return output;
}
}
/*
* Solution:
* Convert the bits in each row to a number
* store max_number while comparing
* Complexity: O(n)
* Better solution would be O(logn)
*/
main()
{
int arr[][4] =
{
{0,0,0,1},
{0,0,1,1},
{0,1,1,1},
{1,1,1,1}
};
int max_num =0;
int max_row =0;
unsigned int num =0;
int i =0;
for(i=0;i<4;i++)
{
num = arr[i][0] | (arr[i][1] << 1UL) | (arr[i][2] << 2UL)| (arr[i][3] << 3UL);
if(num > max_num)
{
max_num = num;
max_row = i;
}
}
printf("\nMax num of 1 are in row =%d\n",max_row);
}
/*
* Earlier tried with O(n)
* but that is not correct. If we make a large array then it boils down to O(n2)
* Following is an effort for O(nlog(n))
* Please let me know comments
*/
{
int small_index =1;
int large_index =4; /* Number of columns */
int middle_index = (small_index + large_index)/2;
int row =0;
int lowest_pos = 4; /* At max pos */
int pos =0;
for(i=0;i<4;i++)
{
small_index =1;
large_index =4; /* Number of columns */
while(1)
{
if(small_index > large_index)
break;
if(arr[i][middle_index] == 1)
{
large_index = middle_index-1;
pos = middle_index;
}
else
{
small_index = middle_index +1;
}
middle_index = (small_index + large_index)/2;
}
if(pos < lowest_pos)
{
lowest_pos = pos;
row = i;
}
}
printf("\n By O(nlog(n)) Menthod: Max num of 1 are in row =%d\n",row);
}
import java.io.DataInputStream;
import java.io.IOException;
public class MatrixCount {
public static void main(String[] args) throws NumberFormatException, IOException{
int arr[][] = new int[4][4];
int max =0;
System.out.println("Matrix");
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
DataInputStream dis = new DataInputStream(System.in);
arr[i][j] = Integer.parseInt(dis.readLine());
}
}
for(int i=0;i<4;i++){
int count =0;
for(int j=0;j<4;j++){
if(arr[i][j] == 1){
count ++;
}
}
if(count > max){
max = count;
}
}
System.out.println("Max 1's "+max);
}
}
Here is my code in Java that uses a binary search to solve the problem. This implementation of binary search is aware of duplicates, and returns the first position where the element being searched occurs in the array.
In case of more than one row in the matrix contains the same number of 1's, the latest row will be returned. This can be easily fixed maintaining a data structure to store all indexes with the same result of binary search.
public class JobInterviewQuestion {
public static void main(String[] args) {
final int[][] m = {
{0, 0, 0, 1}, // Row 1
{1, 1, 1, 1}, // Row 2
{0, 0, 1, 1}, // Row 3
{0, 1, 1, 1}, // Row 4
};
System.out.println("The row that contains maximum number of 1s is: " + findMaxNumberOf1s(m));
}
//Time complexity: O(nlog(n))
public static int findMaxNumberOf1s(final int[][] m) {
int smallerPos = m.length;
int maxRow = -1;
for (int r = 0; r < m.length; r++) {
final int currPos = binarySearchFirstPosition(m[r], 1);
if (currPos < smallerPos) {
smallerPos = currPos;
maxRow = r;
}
}
return maxRow + 1;
}
//Time complexity: O(log(n))
private static int binarySearchFirstPosition(final int[] a, final int value) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
final int mid = (lo + hi) / 2;
if (value < a[mid]) hi = mid - 1;
else if (value > a[mid]) lo = mid + 1;
else if (mid - 1 >= lo && a[mid - 1] == a[mid]) hi = mid - 1;
else return mid;
}
return -1;
}
}
int max_num_one(int [][] matrix, int row, int col)
{
int maxrow = 0;
int num_one = col;
for(int i=0; i<row;++i){
for (int j = 0; j < col; ++j){
if(matrix[i][j] == 1){
if (j == 0)
return i;
else{
if(j < num_one){
max_row = i;
num_one = j;
}
break;
}
}
}
}
return maxrow;
}
// Method 2: O(n) start at position [0][n - 1]
// if we see 1 we move left (j--)
// if we see 0 we move down (i++)
int maximumRow2(int **a, int rows, int cols) {
int maxRow = -1;
int i = 0;
int j = cols - 1;
while (i < rows - 1 && j > 0) {
if (a[i][j] == 1) {
j--;
maxRow = i;
} else {
i++;
}
}
return i;
}
int row = -1;
for(int i=0; i<n.length; i++){
// Start scan from right end
int zeroPos = -1;
for(int j=n[i].length-1; j>=0; j--){
if(n[i][j] == 0){
zeroPos = j;
break;
}
}
if(zeroPos == -1){
row = i;
break;
} else {
int thisRow = n[i].length - 1 - zeroPos;
if(thisRow > row){
row = i;
}
}
}
System.out.println(row);
package com.practice.algo.and.ds.bitmanipulation;
public class BitMask {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] arr = {{0,0,0,1},{1,1,1,1},{0,0,1,1},{0,1,1,1}};
int n = 1;
for(int i =0;i<3;i++){
n |=(n<<1);
}
int count = Integer.MIN_VALUE;
for(int i=0;i<arr.length;i++){
String str = "";
for(int j=0;j<arr.length;j++){
str+=arr[i][j];
}
int c= Integer.bitCount(Integer.parseInt(str, 2) & n);
if(c > count){
count = c;
}
}
System.out.println(count);
}
}
//Algorithm
traverse column wize, Stop the element which has 1
//
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
int MyArray[10][10];
void main(int argc, char **argv)
{
int Row = 0;
int Col = 0;
//Get the number of row and column
printf("Enter the number of rows ");
scanf("%d",&Row);
printf("\nEnter the number of Col ");
scanf("%d",&Col);
// Get the array
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf("\n Enter the element Row %d Col %d -->",i,j);
scanf("%d",&MyArray[i][j]);
}
}
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf(" %d",MyArray[i][j]);
}
printf("\n");
}
/// *** Logic Starts from Here ***///
for(int j=0; j < Col; j++)
{
int sum= 0;
int i;
for(i=0; i < Row; i++)
{
if(MyArray[i][j])
{
break;
}
}
if(i < Row)
{
//We got an row with 1
printf("row %d you are looking for",i);
break;
}
}
getch();
}
Traverse column wize. Stop to the element which has 1.
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
int MyArray[10][10];
void main(int argc, char **argv)
{
int Row = 0;
int Col = 0;
//Get the number of row and column
printf("Enter the number of rows ");
scanf("%d",&Row);
printf("\nEnter the number of Col ");
scanf("%d",&Col);
// Get the array
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf("\n Enter the element Row %d Col %d -->",i,j);
scanf("%d",&MyArray[i][j]);
}
}
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf(" %d",MyArray[i][j]);
}
printf("\n");
}
/// *** Logic Starts from Here ***///
for(int j=0; j < Col; j++)
{
int sum= 0;
int i;
for(i=0; i < Row; i++)
{
if(MyArray[i][j])
{
break;
}
}
if(i < Row)
{
//We got an row with 1
printf("row %d you are looking for",i);
break;
}
}
getch();
}
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
int MyArray[10][10];
void main(int argc, char **argv)
{
int Row = 0;
int Col = 0;
//Get the number of row and column
printf("Enter the number of rows ");
scanf("%d",&Row);
printf("\nEnter the number of Col ");
scanf("%d",&Col);
// Get the array
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf("\n Enter the element Row %d Col %d -->",i,j);
scanf("%d",&MyArray[i][j]);
}
}
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf(" %d",MyArray[i][j]);
}
printf("\n");
}
/// *** Logic Starts from Here ***///
for(int j=0; j < Col; j++)
{
int sum= 0;
int i;
for(i=0; i < Row; i++)
{
if(MyArray[i][j])
{
break;
}
}
if(i < Row)
{
//We got an row with 1
printf("row %d you are looking for",i);
break;
}
}
getch();
}
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
int MyArray[10][10];
void main(int argc, char **argv)
{
int Row = 0;
int Col = 0;
//Get the number of row and column
printf("Enter the number of rows ");
scanf("%d",&Row);
printf("\nEnter the number of Col ");
scanf("%d",&Col);
// Get the array
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf("\n Enter the element Row %d Col %d -->",i,j);
scanf("%d",&MyArray[i][j]);
}
}
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf(" %d",MyArray[i][j]);
}
printf("\n");
}
/// *** Logic Starts from Here ***///
for(int j=0; j < Col; j++)
{
int sum= 0;
int i;
for(i=0; i < Row; i++)
{
if(MyArray[i][j])
{
break;
}
}
if(i < Row)
{
//We got an row with 1
printf("row %d you are looking for",i);
break;
}
}
getch();
}
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
int MyArray[10][10];
void main(int argc, char **argv)
{
int Row = 0;
int Col = 0;
//Get the number of row and column
printf("Enter the number of rows ");
scanf("%d",&Row);
printf("\nEnter the number of Col ");
scanf("%d",&Col);
// Get the array
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf("\n Enter the element Row %d Col %d -->",i,j);
scanf("%d",&MyArray[i][j]);
}
}
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf(" %d",MyArray[i][j]);
}
printf("\n");
}
/// *** Logic Starts from Here ***///
for(int j=0; j < Col; j++)
{
int sum= 0;
int i;
for(i=0; i < Row; i++)
{
if(MyArray[i][j])
{
break;
}
}
if(i < Row)
{
//We got an row with 1
printf("row %d you are looking for",i);
break;
}
}
getch();
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
int MyArray[10][10];
void main(int argc, char **argv)
{
int Row = 0;
int Col = 0;
//Get the number of row and column
printf("Enter the number of rows ");
scanf("%d",&Row);
printf("\nEnter the number of Col ");
scanf("%d",&Col);
// Get the array
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf("\n Enter the element Row %d Col %d -->",i,j);
scanf("%d",&MyArray[i][j]);
}
}
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf(" %d",MyArray[i][j]);
}
printf("\n");
}
/// *** Logic Starts from Here ***///
for(int j=0; j < Col; j++)
{
int sum= 0;
int i;
for(i=0; i < Row; i++)
{
if(MyArray[i][j])
{
break;
}
}
if(i < Row)
{
//We got an row with 1
printf("row %d you are looking for",i);
break;
}
}
getch();
}
Y cant we traverse columns. presence of 1 in the Zeroth index of the row means that is the row which contains the maximum number of 1s. Please correct me if i am wrong.
My idea is
for(i=0;i<m;i++)
{
for (j=0;j<n;j++)
{
if(a[j][i]=='1')
{
arraylist1.add(j);
break;
}
}
}
The value in the arraylist+1 gives the Row wiith max num of 1s.
This is a very simple question:
since it is already sorted on each row, the first 1 you find while scanning top to bottom on each column will be the row with the max 1's.
int findRowWithMaxNumberOfOnes(int[][] matrix, int len, int hight)
{
for(int i=0; i<len; i++) //scanning column on each row
for(int j=0; j<hight; j++) //scanning the column
if(matrix[j][i] == 1)
return j;
return 0;
}
(above was my answer- i was just not signed in)
BTW- if all of the rows contains all ones than return the first row is fine.
In the worst case , when all are zero except the one at right bottom, it takes O(m*n).... I like your idea but instead lets do binary search on column for number 1 ---- in this case the worst case will be O(mlogn)
Here is O(mlogn) implementation in c#
int GetRowWithMaxOne(int[,] matrix)
{
for (int i = 0; i < matrix.GetLength(1); i++)
{
int row = DoBinarySearch(matrix, i, 1, 0, matrix.GetLength(1));
if (row != -1) { return row; }
}
return -1;
}
int DoBinarySearch(int[,] matrix, int i, int low, int high, int x)
{
if (low > high)
{
return -1;
}
int mid = low + (high - low) / 2;
if (matrix[i, mid] == x)
{
return mid;
}
if (matrix[i,mid] > x)
{
return DoBinarySearch(matrix, i, low, mid - 1, x);
}
return DoBinarySearch(matrix, i, mid + 1, high, x);
}
This code will not work if the following input is given
00111
01111
00011
It will return the first row, not second row.
Algo:
- Anonymous January 24, 20151. start scanning from right most end of first row and find first occurrence of 0.
suppose it is some value x.
then max_numer of 1 till now is col-x-1.
2. then go to next row but start from x. if you found 1 at that place then scan this row and find new x as in first step and replace max_number by new value of col-x-1.
3. repeat it till last row mean while if you get x=-1 then return the length of col.
if anyone want code i can provide.