Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

1. Start from top right corner.
2. Go left if it has 1 on its left, down otherwise
3. We find the longest 1 sequence in O(m+n).

We keep count of the longest sequence.

Reiterate over the collumn where the longest ends
And print the row info if it has a 1 on that position.

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

Binary search each row to find the starting location of 1s. This will have a O(m*log(n)) run time.

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

"1. Start from top right corner.
2. Go left if it has 1 on its left, down otherwise
3. We find the longest 1 sequence in O(m+n).

We keep count of the longest sequence.

Reiterate over the collumn where the longest ends
And print the row info if it has a 1 on that position."

Your answer is good but I think it is incomplete, what if the last row in the example matrix had one more 1, the sequence you found in step 3 might not be the longest, one fix could be to iterate over the column where the current longest sequence begins and try to reapply steps 1 and 2. You must also keep track of the current max length and the position of the row that you found it and if there are no more rows to reapply steps 1 and 2 then you know you got the longest sequence and you can start printing the positions. I think the complexity should stay the same.

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

Binary search each row to find the first location of 1. This will have a run time of O(m*log(n))

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

pretty easy in recursion - DP - C#.

``````public void RecursionColumnWise(int[,] matrix, int rowSize, int colSize, int row = 0, int col = 0)
{
if (col > colSize) return;

if (matrix[row, col] == 1)
{
Console.WriteLine("{0}, {1}", row + 1, colSize - col + 1); //Adding 1 to prime the index
if (row >= rowSize)
return;
}
if (row >= rowSize && col < colSize)
// Only when it scanned all of the rows and still columns left to scan - jump to next column from the beginning.
// Beginning means row = 0 and next column
RecursionColumnWise(matrix, rowSize, colSize, 0, col + 1);
else
// else scan across all the element in the row
RecursionColumnWise(matrix, rowSize, colSize, row + 1, col);
}``````

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

Here is my implementation in Java:

``````public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = scanner.nextInt();
}
}
StringBuilder output = new StringBuilder();
for (int[] rowDetails : getRowsWithMaxOnes(matrix)) {
output.append('[').append(rowDetails[0]).append(", ").append(rowDetails[1]).append(']')
.append(System.lineSeparator());
}
System.out.print(output);
}
}

private static List<int[]> getRowsWithMaxOnes(int[][] matrix) {
List<int[]> results = new ArrayList<>();
int maxAmount = 0;
for (int i = 0; i < matrix.length; i++) {
int maxOfCurrentLine = 0;
if (maxAmount == 0) {
for (int j = matrix[i].length - 1; j >= 0; j--) {
if (matrix[i][j] == 1) {
maxAmount = matrix[i].length - j;
} else {
results.add(new int[]{i + 1, maxAmount});
break;
}
}
} else {
for (int j = matrix[i].length - maxAmount; j >= 0; j--) {
if (matrix[i][j] == 0) {
maxOfCurrentLine = matrix[i].length - j - 1;
break;
}
}
if (maxOfCurrentLine == maxAmount) {
results.add(new int[]{i + 1, maxAmount});
} else if (maxOfCurrentLine > maxAmount) {
results.clear();
maxAmount = maxOfCurrentLine;
results.add(new int[]{i + 1, maxAmount});
}
}
}
return results;
}``````

Samples of both input and output:

``````The first:
12 6
0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1

[2, 8]
[6, 8]
The second:
3 3
0 0 0
0 0 0
0 0 0

[1, 0]
[2, 0]
[3, 0]
The third:
3 3
0 0 0
0 0 1
0 1 1

[3, 2]``````

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

Implementation based on first response:

``````// Returns: Row index and Count
public static IEnumerable<Tuple<int, int>> GetMaximumRows(int[,] a)
{

var result = new List<Tuple<int,int>>();
int m = a.GetLength(1);
int j = m - 1;

for (int i=0; i < a.GetLength(0); i++)
{

if (a[i,j] == 0)
continue;

if (j > 0 && a[i,j-1] == 1)
{
result.Clear();
while (j > 0 && a[i,j-1] == 1)
j--;
}

}

return result;
}``````

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

``````def row_max_1s(mat):
m = len(mat)
n = len(mat[0])
j = len(mat[0]) - 1
cur_row = 0
while cur_row < len(mat):
while j >= 0 and mat[cur_row][j] == 1:
j -= 1
if j < 0:
return cur_row
cur_row += 1
return cur_row``````

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

``````public static int getMaxOnes(int[][] arr) {
if(arr==null)throw new NullPointerException("Null array");
int max = 0;
int row = 0;
for (int col = arr[0].length-1;col >= 0 && row<arr.length;col-- ){
if(arr[row][col]==1)
max++;
else {
row++;
while(row < arr.length && arr[row][col]==0)
row++;
if(row < arr.length)
max++;
}
}
return max;
}``````

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

``````import java.io.*;

class Array {
public static void main (String[] args) {
int arr[][] = {{0,0,0,1,1,1},
{0,0,1,1,1,1},
{0,0,0,0,0,0},
{0,0,1,1,1,1}};
findMaxRow(arr);
}

static void findMaxRow(int arr[][]) {
int index = arr[0].length - 1;
for(int i=0; i<arr.length; i++){
while(arr[i][index] == 1) {
index--;
}
}
for(int i=0; i<arr.length; i++){
if(arr[i][index+1] == 1)
System.out.println(i);
}
}
}``````

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

``````import java.util.Scanner;

public class MainClassTestesEstudos {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] matrix = new int[m][n];
int max = 0;
String result = "";
for (int i = 0; i < m; i++)
{
int ones = 0;
for (int j = 0; j < n; j++)
{
matrix[i][j] = scanner.nextInt();
if (matrix[i][j] == 1) ones++;
}
if (ones > max)
{
max = ones;
result = "["+(i+1)+", "+max+"]\n";
} else if (ones == max) result += "["+(i+1)+", "+max+"]\n";
}
scanner.close();
System.out.println(result);
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

As the array is sorted :
1. Iterate through all the rows.
2. For each row, start from the last column, until you hit a 0 element.
3. Keep track of the 1 count for each row in a HashMap, and also keep track of the max 1 count seen so far.
4. Iterate through the HashMap and print all the rows (keys) with the value as the max count of 1.

``````public static List<List<Integer>> getAnswer(int[][] arr){
int maxCount = 0;
int colLength = arr[0].length -1;
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < arr.length; i++){
int j = arr[i].length-1;
while(arr[i][j] != 0){
j--;
}
int currL = colLength - j;
map.put(i, currL);
if(maxCount < currL ){
maxCount = currL;
}
}
List<List<Integer>> res = new ArrayList<>();
for(Map.Entry<Integer, Integer> e: map.entrySet()){
if(e.getValue() == maxCount){
List<Integer> t = new ArrayList<>();
}
}
return res;
}

public static void main(String[] args){
int[][] arr = {{0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,1,1,1,1,1,1,1,1}};
}``````

Comment hidden because of low score. Click to expand.
-1
of 3 vote

zeroFound = false
for col = 0 to len(row 1) {
for each row in source array
if row[col] == 1, this row must have the maximum of 1s
zeroFound = true
if zeroFound, break
}

``````public class MostOnes {
public static String run(int[][] src) {
StringBuilder s = new StringBuilder();
int len = src[0].length;
boolean zeroFound = false;
for(int col = 0 ; col < len && !zeroFound; col ++) {
for(int row = 0; row < src.length; row++) {
if(src[row][col] == 1) {
zeroFound = true;
s.append("[").append(row + 1).append(",").append(len - col).append("]");
}
}
}
return s.toString();
}
}``````

test case

``````@Test
public void test() {
int[][] arr = {{0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,1,1,1,1,1,1,1,1}};
String result = MostOnes.run(arr);
Assert.assertEquals("[2,8][6,8]", result);
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public static void main(String args[]) {
int[][] arr = {
{ 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1 }
};
System.out.println(maxOnesInRow(arr));
}

public static int maxOnesInRow(int matr[][]) {
int maxOnes = 1;
int i = matr.length - 1;
int j = 0;
while (i >= 0 && j >= 0) {
while (matr[i][j] == 1)
j--;
while (matr[i][j] == 0)
j++;
maxOnes = Math.max(matr[0].length - j, maxOnes);
i--;
}
return maxOnes;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int row = in.nextInt();
int col = in.nextInt();
int[][] arr = new int[row][col];
for(int i = 0; i < row; i++) {
for(int j = 0 ; j < col; j++) {
arr[i][j] = in.nextInt();
}
}

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int maxCount = 0;
int count = 0;
int l = 0;
for(int k = col-1; k >= 0; k--){
while(l < row) {
if(arr[l][k] == 1) {
count++;
k--;
} else {
if(count >= maxCount) {
maxCount = count;
//System.out.println("arr[" + l + "][" + k + "] " + arr[l][k]);
map.put(l, maxCount);

}
l++;
}
}
}

for(int i : map.keySet()) {
if(map.get(i) == maxCount && arr[i][col-maxCount] == 1) {
System.out.println(i+1 + " " + map.get(i));
}
}
}

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.

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.