Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

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;

- zahidbuet106 April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Santosh Dhakad April 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Above solution will work only if row==column, will post another solution also

- Santosh Dhakad April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your return type is int which is not what it requires

- lemma April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- ninhnnsoc April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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. :-(

- iroodaz April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- wei April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- iroodaz April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
    }

- Danstahr April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}
}

- Harish April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Anonymous April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- hankm2004 April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
     }
}

- Nitin April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- Anonymous April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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);

- SumitGaur April 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

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;

- zahidbuet106 April 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ganesh April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It won't work ... as
0110011 sums to 4
0111000 sums to 3

but ans should be 0111000 (consecutive 1s)

- Manku April 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 + " ");
        }

}

- Scott May 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// 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);

- Asmi May 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// 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;
}

- jiangok2006 May 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* 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);

}

- Sami May 31, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More