Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
public int findSequence(int arr[][])
int rhcount,chcount,trcount,tccount;
for(int i=0:i<m;i++){
trcount=currRowCount(arr,i);
if(trcount>rhcount) rhcount=trcount;
tccount=currColCount(arr,i);
if(tccount>chcount) chcount=tccount;
}
return (rhcount>chcount)?rhcount:chcount;
}
public int currRowCount(int arr[][], int tr){
int count=0,tcount=0;
for(int i=0;i<row;i++){
if(arr[tr][i]==1){ tcount++;
if(count<tcount) count=tcount;
}else
tcount=0;
}
return count;
}
public int currColCount(int arr[][], int tr){
int count=0,tcount=0;
for(int i=0;i<row;i++){
if(arr[i][tr]==1){ tcount++;
if(count<tcount) count=tcount;
}else
tcount=0;
}
return count;
}
A follow up question may be:
The binary matrix is very big and it's stored in a file, with N = 2*10^6 lines, and M = 5000 characters each line. You cannot use more than 64 KB of main memory to store data.
Find the longest sequence of 1's in column wise.
Any one?
My initial idea is to keep a counter for every column. However, this counters will utilize 5000*4 = 20 KB of main memory and we will be left with only 44 KB of memory. This means we would be able to process only two rows at a time. Although this would seem inefficient, I am not sure we could do much better. :-(
Is the follow up question possible? Even if each 1 is stored as bits. In the case where a column is all 1s, you need 2*10^6 bits, which is 250k bytes, to store the sequence
Good idea to store the matrix as bits.
It is of course possible. During execution, you'll only need to store the length of the longest sequence and the length of the sequence for every column leading to the current row and not discard them. For the matrix, you can bring in one block at a time and update your variables and discard that block because you do not need it anymore. You'll need ~20k memory for the variables. The remaining memory could be used for bringing in the blocks.
Just remember an array of size M which determines "the length of the sequence of ones above me".
public static int longestOnes(int[][] input, int M) {
int best = 0;
int[] counters = new int[M];
for (int[] line : input) {
for (int i = 0; i < line.length; ++i) {
counters[i] = line[i] == 1 ? counters[i] + 1 : 0;
best = Math.max(counters[i], best);
}
}
return best;
}
max=0;
count=0;
left=0; right=0;
//Check the rows
for(int i=0;i<row;i++)
{
count=0;
for(int j=0;j<col;j++)
{
if(arr[i][j]==1) count++;
else if(count>0)
{
if(count>max)
{
max=count;
}
count = 0;
}
if(j==col-1)
{
if(count>max)
{
max=count;
}
}
}
}
//Check the columns
for(int i=0;i<col;i++)
{
count=0;
for(int j=0;j<row;j++)
{
if(arr[j][i]==1) count++;
else if(count>0)
{
if(count>max)
{
max=count;
}
count=0;
}
if(j==row-1)
{
if(count>max)
{
max=count;
}
}
}
}
Here is a solution in python.
I was not sure what should be return type, so I printed out the result.
def find_long_seq(matrix, vlen, hlen):
is_vertial = False
max_seq = 0
for i in range(0, vlen):
cur_seq=0
for j in range(0, hlen):
if matrix[i][j] == 1:
cur_seq+=1
elif matrix[i][j] == 0:
if max_seq < cur_seq:
max_seq = cur_seq
is_vertical = False
cur_seq = 0
if max_seq > hlen - j:
continue
if j == hlen-1 and max_seq < cur_seq:
max_seq = cur_seq
is_vertical = False
for h in range(0, hlen):
cur_seq = 0
for l in range(0, vlen):
if matrix[l][h] == 1:
cur_seq+=1
elif matrix[l][h] == 0:
if max_seq < cur_seq:
max_seq = cur_seq
is_vertical = True
cur_seq = 0
if l == vlen-1 and max_seq < cur_seq:
max_seq = cur_seq
is_vertical = True
print "max sequence = " + str(max_seq) + " is_vertial : " + str(is_vertical)
Enhanced previous one to avoid unnecessary search.
Here is a solution in python.
I was not sure what should be return type, so I printed out the result.
def find_long_seq(matrix, vlen, hlen):
is_vertial = False
max_seq = 0
for i in range(0, vlen):
cur_seq=0
for j in range(0, hlen):
if matrix[i][j] == 1:
cur_seq+=1
elif matrix[i][j] == 0:
if max_seq < cur_seq:
max_seq = cur_seq
is_vertical = False
cur_seq = 0
if max_seq > hlen - j:
continue
if j == hlen-1 and max_seq < cur_seq:
max_seq = cur_seq
is_vertical = False
for h in range(0, hlen):
cur_seq = 0
for l in range(0, vlen):
if matrix[l][h] == 1:
cur_seq+=1
elif matrix[l][h] == 0:
if max_seq < cur_seq:
max_seq = cur_seq
is_vertical = True
cur_seq = 0
if max_seq > vlen - l:
continue
if l == vlen-1 and max_seq < cur_seq:
max_seq = cur_seq
is_vertical = True
print "max sequence = " + str(max_seq) + " is_vertial : " + str(is_vertical)
void longest(int a[][M])
{
int i=0,j=0;
int max=0,row=-1,col=-1,count=0;
for(j=0;j<M;j++)
{
count=0;
for(i=0;i<N;i++)
{
if(a[i][j]==1)
count++;
else
{
if(count>max)
{
max = count;
row = j;
}
count =0;
}
}
if(count>max)
{
max = count;
row = j;
}
}
for(i=0;i<N;i++)
{
count=0;
for(j=0;j<M;j++)
{
if(a[i][j]==1)
count++;
else
{
if(count>max)
{
max = count;
col = i;
}
count =0;
}
}
if(count>max)
{
max = count;
col = i;
}
}
if(col==-1)
{
printf("Row is %d and sequence count is %d\n",row,max);
count=0;
for(i=0;i<N;i++)
{
if(a[i][row]==1)
count++;
else
count =0;
if(count==max)
col=i;
}
printf("Sequence is from [%d,%d] to [%d,%d]\n",col-max+1,row,col,row);
}
else
{
printf("Column is %d and sequence count is %d\n",col,max);
count=0;
for(i=0;i<M;i++)
{
if(a[col][i]==1)
count++;
else
count =0;
if(count==max)
row=i;
}
printf("Sequence is from [%d,%d] to [%d,%d]\n",col,row-max+1,col,row);
}
}
in java
public static ArrayList<Integer> longestPath(int[][] grid) {
int x = 0;
int y = 0;
// save the starting point of the longest path
int sx = 0;
int sy = 0;
int max = 0;
boolean fromCol = false;
// go through each rows
for (int i = 0; i < grid.length; i++) {
int row = 0;
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
if (row == 0) {
x = i;
y = j;
}
row++;
} else {
if (grid.length - j - 1 > row) {
row = 0;
} else {
break;
}
}
}
if (max < row) {
max = row;
sx = x;
sy = y;
}
}
// go through each columns
for (int i = 0; i < grid[0].length; i++) {
int col = 0;
for (int j = 0; j < grid.length; j++) {
if (grid[j][i] == 1) {
if (col == 0) {
x = j;
y = i;
}
col++;
} else {
if (grid.length - j - 1 > col) {
col = 0;
} else {
break;
}
}
}
if (max < col) {
// this flag determines the longest path was found in a column
fromCol = true;
max = col;
sx = x;
sy = y;
}
}
// print out where the longest path is
if (fromCol) {
System.out.println("col => from [" + sx + ", " + sy + "] to [" + (sx + max - 1) + ", " + sy + "]");
} else {
System.out.println("row => from [" + sx + ", " + sy + "] to [" + sx + ", " + (sy + max - 1) + "]");
}
ArrayList<Integer> path = new ArrayList<Integer>();
for (int i = 0; i < max; i++)
path.add(1);
return path;
}
The following code work assuming all the 1s are grouped together
//Original Matrix
int[][] originalMatrix = new int[][] { { 0, 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 0, 0 }, { 0, 0, 0, 1, 0, 0 } };
//Two temp arrays of length derived from number of rows and cols
int[] row = new int[originalMatrix.length];
int[] col = new int[originalMatrix[0].length];
//For every element in the original Matrix
for (int i = 0; i < row.length; i++) {
for (int j = 0; j < col.length; j++) {
//If a 1 is found
if (originalMatrix[i][j] == 1) {
//Increment the corresponding row and col number
row[i] += 1;
col[j] += 1;
}
}
}
//Find the maximum value
int maxLength = -1;
for (int i = 0; i < (row.length > col.length ? row.length : col.length); i++) {
if (i < row.length) {
if (row[i] > maxLength) {
maxLength = row[i];
}
}
if (i < col.length) {
if (col[i] > maxLength) {
maxLength = col[i];
}
}
}
//Print
System.out.println(maxLength);
BAD assumption. There is a better solution without any assumption
max_row_len = Integer.Min;
max_col_len = Integer.Min;
cur_max_len = 0;
for each row
{
for each col
{
if (matrix[row][[col] == 0 || col == matrix[0].length-1)
{
if (cur_max_len > max_row_len)
max_row_len = cur_max_len;
cur_max_len = 0;
}
else cur_max_len++;
}
}
if (cur_max_len!=0 && cur_max_len > max_row_len)
max_row_len = cur_max_len;
cur_max_len = 0;
for each col
{
for each row
{
if (matrix[row][[col] == 0 || row == matrix.length-1)
{
if (cur_max_len > max_col_len)
max_col_len = cur_max_len;
cur_max_len = 0;
}
else cur_max_len++;
}
}
if (cur_max_len!=0 && cur_max_len > max_col_len)
max_col_len = cur_max_len;
max_len = max(max_row_len, max_col_len);
return sequence of 1's of size max_len;
Why can't we try to add the numbers rowwise and columnwise . so whichever is greater we will get to find the row/col with max no. Of 1s.
Then try printing it based on the value obtained . is it a good approach,
Please advice
public static void findMaxNumOfOne(int [][] matrix){
int [][] dp = new int[matrix.length][matrix[0].length] ;
dp [0][0] = matrix[0][0] == 1 ? 1 : 0;
int max_h = -1 ;
int max_d = -1 ;
for (int i = 0 ; i < matrix.length ; ++i){
for (int j = 1 ; j < matrix[0].length ; ++j){
//horizon
if ( matrix[i][j] != 0 && dp [i][j] < matrix[i][j] + dp [i][j-1]) {
dp [i][j] = matrix[i][j] + dp [i][j-1];
max_h = Math.max(max_h, dp [i][j]);
}
}
}
int [][] dp1 = new int[matrix.length][matrix[0].length] ;
dp1 [0][0] = matrix[0][0] == 1 ? 1 : 0;
for (int i = 0 ; i < matrix.length ; ++i){
for (int j = 1 ; j < matrix[0].length ; ++j){
//down
if ( i+1 < matrix.length && matrix[i+1][j-1] != 0 && dp1 [i+1][j-1] < matrix[i+1][j-1] + dp1 [i][j-1] ){
dp1 [i+1][j-1] = matrix[i+1][j-1] + dp1 [i][j-1];
max_d = Math.max(max_d, dp1 [i+1][j-1]);
}
}
}
max_h = Math.max(max_h, max_d) ;
for (int i = 0 ; i < max_h ; ++i ){
System.out.print(1 + " ");
}
}
// TODO Auto-generated method stub
int[][] a =
{ {1,0,0,0,1},
{0,0,1,1,1},
{1,0,0,0,1},
{1,0,1,0,1},
{1,0,0,1,1},
{1,1,0,0,1}};
HashMap<Integer, String> hash=new HashMap<Integer, String>();
String row="";
String col="";
int prevRow=-1;
int prevCol=-1;
for (int i = 0; i < 6; i++)
{
row="";
col="";
prevRow=-1;
prevCol=-1;
for (int j = 0; j < 5; j++)
{
if(i<6 && j<5)
{
if(a[i][j]==0)
{
prevRow=-1;
row="";
}else if(a[i][j]==1 && (prevRow==-1 || prevRow==1))
{
prevRow=1;
row+="1,";
hash.put(row.length(), row);
}
}
if(j<6 && i<5)
{
if(a[j][i]==0)
{
prevCol=-1;
col="";
}else if(a[j][i]==1 && (prevCol==-1 || prevCol==1))
{
prevCol=1;
col+="1,";
hash.put(col.length(), col);
}
}
}
}
System.out.println(hash);
// change the question to return the length of the longest sequence
// Pnt is a class having two int members v and h. v means vertical sequence length starting
// from this point, h means horizontal sequence length starting from this point.
int f(int[,] mat, Pnt[,] pnt)
{
int max = INT_MIN;
for(int i=0;i<mat.length;++i)
for(int j=0;j<mat[i].length;++j)
{
if(mat[i,j]==0)
{
pnt[i,j]= new Pnt(0, 0);
}
else
{
int h = i==0 ? 1 : pnt[i-1,j].v+1;
int v = j==0 ? 1 : pnt[i,j-1].h+1;
pnt[i,j]= new Pnt(h, v);
if(h>max) max=h;
if(v>max) max=v;
}
}
return max;
}
/* Code written in c#. will works
*/
private static void PrintLargestSequence()
{
int[][] a = new int[][] { new int[] { 0, 0, 0, 1, 0, 0 },
new int[] { 1, 0, 1, 0, 1, 0 },
new int[] { 0, 0, 0, 1, 0, 0 },
new int[] { 1, 0, 0, 0, 0, 0 },
new int[] { 0, 1, 1, 1, 1, 1 },
new int[] { 0, 0, 0, 1, 0, 0 } ,
new int[] { 0, 0, 0, 1, 0, 0 }
};
int x_seq_count=0,max_x=0;
int[] stIdxX = new int[a.Length];
int[] max_y = new int[a[0].Length];
int[] y_seq_count = new int[a[0].Length];
//For every element in the original Matrix
for (int i = 0; i < a.Length; i++)
{
x_seq_count = 0;
for (int j = 0; j < a[0].Length; j++)
{
//If a 1 is found
if (a[i][j] == 1)
{
x_seq_count += 1;
y_seq_count[j] += 1;
if (x_seq_count > max_x || x_seq_count == a[0].Length)
{
max_x = x_seq_count;
}
if (y_seq_count[j] > max_y[j] || y_seq_count[j] == a.Length)
{
max_y[j] = y_seq_count[j];
}
}
else {
x_seq_count = 0;
y_seq_count[j] = 0;
}
}
}
//Find largest seq in y
for (int j = 0; j < max_y.Length; j++)
{
if (max_y[j] > max_x) {
max_x = max_y[j];
}
}
string output = string.Empty;
for (int j = 0; j < max_x; j++)
output = !string.IsNullOrEmpty(output) ? string.Join(",", new string[] { output, "1" }) :"1";
Console.WriteLine(output);
}
- zahidbuet106 April 29, 2014