## Amazon Interview Question for SDE-3s

Country: United States

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

``````#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> findCuts(vector<vector<int>>& binaryMatrix, int horizontalCuts, int verticalCuts)
{
// Calculate row sums
vector<int> rowSums(binaryMatrix.size(), 0);
int rowTotal = 0;
int sum = 0;
for(int row = 0; row < binaryMatrix.size(); ++row)
{
sum = 0;
for(int col = 0; col < binaryMatrix[row].size(); ++col)
{
sum += binaryMatrix[row][col];
}

rowSums[row] = sum;
rowTotal += sum;
}

// Calculate column sums
vector<int> colSums(binaryMatrix[0].size(), 0);
int colTotal = 0;
sum = 0;
for(int col = 0; col < binaryMatrix[0].size(); ++col)
{
sum = 0;
for(int row = 0; row < binaryMatrix.size(); ++row)
{
sum += binaryMatrix[row][col];
}
colSums[col] = sum;
colTotal += sum;
}

// Number of ones contained in each sub matrix after the horizonzal split(s)
int numberOfOneRowSub = rowTotal / (horizontalCuts + 1);
// Number of ones contained in each sub matrix after the vertical split(s)
int numberOfOneColSub = colTotal / (verticalCuts + 1);

// Find row cuts
vector<int> rowCuts;
int rowsSum = 0;
for(int row = 0; row < rowSums.size(); ++row)
{
if(horizontalCuts == 0)
{
break;
}

rowsSum += rowSums[row];
if(rowsSum == numberOfOneRowSub)
{
rowsSum = 0;
rowCuts.push_back(row + 1);
horizontalCuts--;
}
}

// Find col cuts
vector<int> colCuts;
int colsSum = 0;
for(int col = 0; col < colSums.size(); ++col)
{
if(verticalCuts == 0)
{
break;
}

colsSum += colSums[col];
if(colsSum == numberOfOneColSub)
{
colsSum = 0;
colCuts.push_back(col + 1);
verticalCuts--;

}
}

vector<vector<int>> cutIndices;
cutIndices.push_back(rowCuts);
cutIndices.push_back(colCuts);

return cutIndices;

}

int main()
{
int h = 1;
int v = 3;

vector<vector<int>> binaryMatrix;
binaryMatrix.push_back({1,1,1,1,1});
binaryMatrix.push_back({0,0,1,1,1});
binaryMatrix.push_back({0,1,1,1,1});
binaryMatrix.push_back({1,0,1,1,1});

vector<vector<int>> cutIndices = findCuts(binaryMatrix, h, v);

cout << "Cut indices for rows and columns:" << endl;
for(int c = 0; c < cutIndices.size(); ++c)
{
for(int i = 0; i < cutIndices[c].size(); ++i)
{
cout << cutIndices[c][i] << " ";
}
cout << endl;
}

return 0;``````

}

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

// 1 1 1 0 0
// 1 1 1 0 0
// 0 0 1 1 1
// 0 0 1 1 1

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

Try the following input,
// 1 1 1 0 0
// 1 1 1 0 0
// 0 0 1 1 1
// 0 0 1 1 1

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

``````public class Split2DArray {

public static void main(String[] args) {
int[][] darray = { { 1, 1, 1, 0, 0 }, { 1, 1, 1, 0, 0 }, { 0, 0, 1, 1, 1 }, { 0, 0, 1, 1, 1 } };// {{1,1,1,1,1},
// {0,0,1,1,1},{0,1,1,1,1},{1,0,1,1,1}};
int ones = 0;
for (int i = 0; i < darray.length; i++) {
for (int j = 0; j < darray[i].length; j++) {
if (darray[i][j] == 1) {
ones++;
}
}
}
int height = 4;
int width = 5;
int H = 3;
int V = 2;
if (ones % (H + 1) == 0) {
divideH(darray, height, H, ones / (H + 1));
} else {
System.out.println("Horizontal Cuts 0");
}

if (ones % (V + 1) == 0) {
divideV(darray, width, V, ones / (V + 1));
} else {
System.out.println("Vertical Cuts 0");
}

}

private static void divideV(int[][] darray, int width, int v, int ones) {
int index = 0;
int innerones = ones;
for (int i = 0; i < darray[0].length; i++) {
for (int j = 0; j < darray.length; j++) {
if (darray[j][i] == 1) {
--innerones;
if (innerones == 0) {
innerones = ones;
index = i + 1;
--v;
if (i + 1 != width) {
System.out.println("Vertical Cuts " + index);
}
if (v == 0) {
break;
}
}
}
}
}

}

private static void divideH(int[][] darray, int height, int h, int ones) {
int index = 0;
int innerones = ones;
for (int i = 0; i < darray.length; i++) {
for (int j = 0; j < darray[i].length; j++) {
if (darray[i][j] == 1) {
--innerones;
if (innerones == 0) {
innerones = ones;
index = i + 1;
--h;
if (i + 1 != height) {
System.out.println("Horizontal Cuts " + index);
}
if (h == 0) {
break;
}
}
}
}
}

}
}``````

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

``and``

public class Split2DArray {

public static void main(String[] args) {
int[][] darray = { { 1, 1, 1, 0, 0 }, { 1, 1, 1, 0, 0 }, { 0, 0, 1, 1, 1 }, { 0, 0, 1, 1, 1 } };// {{1,1,1,1,1},
// {0,0,1,1,1},{0,1,1,1,1},{1,0,1,1,1}};
int ones = 0;
for (int i = 0; i < darray.length; i++) {
for (int j = 0; j < darray[i].length; j++) {
if (darray[i][j] == 1) {
ones++;
}
}
}
int height = 4;
int width = 5;
int H = 3;
int V = 2;
if (ones % (H + 1) == 0) {
divideH(darray, height, H, ones / (H + 1));
} else {
System.out.println("Horizontal Cuts 0");
}

if (ones % (V + 1) == 0) {
divideV(darray, width, V, ones / (V + 1));
} else {
System.out.println("Vertical Cuts 0");
}

}

private static void divideV(int[][] darray, int width, int v, int ones) {
int index = 0;
int innerones = ones;
for (int i = 0; i < darray[0].length; i++) {
for (int j = 0; j < darray.length; j++) {
if (darray[j][i] == 1) {
--innerones;
if (innerones == 0) {
innerones = ones;
index = i + 1;
--v;
if (i + 1 != width) {
System.out.println("Vertical Cuts " + index);
}
if (v == 0) {
break;
}
}
}
}
}

}

private static void divideH(int[][] darray, int height, int h, int ones) {
int index = 0;
int innerones = ones;
for (int i = 0; i < darray.length; i++) {
for (int j = 0; j < darray[i].length; j++) {
if (darray[i][j] == 1) {
--innerones;
if (innerones == 0) {
innerones = ones;
index = i + 1;
--h;
if (i + 1 != height) {
System.out.println("Horizontal Cuts " + index);
}
if (h == 0) {
break;
}
}
}
}
}

}
}

``and``

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

``and``

public class Split2DArray {

public static void main(String[] args) {
int[][] darray = { { 1, 1, 1, 0, 0 }, { 1, 1, 1, 0, 0 }, { 0, 0, 1, 1, 1 }, { 0, 0, 1, 1, 1 } };// {{1,1,1,1,1},
// {0,0,1,1,1},{0,1,1,1,1},{1,0,1,1,1}};
int ones = 0;
for (int i = 0; i < darray.length; i++) {
for (int j = 0; j < darray[i].length; j++) {
if (darray[i][j] == 1) {
ones++;
}
}
}
int height = 4;
int width = 5;
int H = 3;
int V = 2;
if (ones % (H + 1) == 0) {
divideH(darray, height, H, ones / (H + 1));
} else {
System.out.println("Horizontal Cuts 0");
}

if (ones % (V + 1) == 0) {
divideV(darray, width, V, ones / (V + 1));
} else {
System.out.println("Vertical Cuts 0");
}

}

private static void divideV(int[][] darray, int width, int v, int ones) {
int index = 0;
int innerones = ones;
for (int i = 0; i < darray[0].length; i++) {
for (int j = 0; j < darray.length; j++) {
if (darray[j][i] == 1) {
--innerones;
if (innerones == 0) {
innerones = ones;
index = i + 1;
--v;
if (i + 1 != width) {
System.out.println("Vertical Cuts " + index);
}
if (v == 0) {
break;
}
}
}
}
}

}

private static void divideH(int[][] darray, int height, int h, int ones) {
int index = 0;
int innerones = ones;
for (int i = 0; i < darray.length; i++) {
for (int j = 0; j < darray[i].length; j++) {
if (darray[i][j] == 1) {
--innerones;
if (innerones == 0) {
innerones = ones;
index = i + 1;
--h;
if (i + 1 != height) {
System.out.println("Horizontal Cuts " + index);
}
if (h == 0) {
break;
}
}
}
}
}

}
}

``and``

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

``````public class Split2DArray {

public static void main(String[] args) {
int[][] darray = { { 1, 1, 1, 0, 0 }, { 1, 1, 1, 0, 0 }, { 0, 0, 1, 1, 1 }, { 0, 0, 1, 1, 1 } };// {{1,1,1,1,1},
// {0,0,1,1,1},{0,1,1,1,1},{1,0,1,1,1}};
int ones = 0;
for (int i = 0; i < darray.length; i++) {
for (int j = 0; j < darray[i].length; j++) {
if (darray[i][j] == 1) {
ones++;
}
}
}
int height = 4;
int width = 5;
int H = 3;
int V = 2;
if (ones % (H + 1) == 0) {
divideH(darray, height, H, ones / (H + 1));
} else {
System.out.println("Horizontal Cuts 0");
}

if (ones % (V + 1) == 0) {
divideV(darray, width, V, ones / (V + 1));
} else {
System.out.println("Vertical Cuts 0");
}

}

private static void divideV(int[][] darray, int width, int v, int ones) {
int index = 0;
int innerones = ones;
for (int i = 0; i < darray[0].length; i++) {
for (int j = 0; j < darray.length; j++) {
if (darray[j][i] == 1) {
--innerones;
if (innerones == 0) {
innerones = ones;
index = i + 1;
--v;
if (i + 1 != width) {
System.out.println("Vertical Cuts " + index);
}
if (v == 0) {
break;
}
}
}
}
}

}

private static void divideH(int[][] darray, int height, int h, int ones) {
int index = 0;
int innerones = ones;
for (int i = 0; i < darray.length; i++) {
for (int j = 0; j < darray[i].length; j++) {
if (darray[i][j] == 1) {
--innerones;
if (innerones == 0) {
innerones = ones;
index = i + 1;
--h;
if (i + 1 != height) {
System.out.println("Horizontal Cuts " + index);
}
if (h == 0) {
break;
}
}
}
}
}

}
}``````

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

``````public class Split2DArray {

public static void main(String[] args) {
int[][] darray = { { 1, 1, 1, 0, 0 }, { 1, 1, 1, 0, 0 }, { 0, 0, 1, 1, 1 }, { 0, 0, 1, 1, 1 } };// {{1,1,1,1,1},
// {0,0,1,1,1},{0,1,1,1,1},{1,0,1,1,1}};
int ones = 0;
for (int i = 0; i < darray.length; i++) {
for (int j = 0; j < darray[i].length; j++) {
if (darray[i][j] == 1) {
ones++;
}
}
}
int height = 4;
int width = 5;
int H = 3;
int V = 2;
if (ones % (H + 1) == 0) {
divideH(darray, height, H, ones / (H + 1));
} else {
System.out.println("Horizontal Cuts 0");
}

if (ones % (V + 1) == 0) {
divideV(darray, width, V, ones / (V + 1));
} else {
System.out.println("Vertical Cuts 0");
}

}

private static void divideV(int[][] darray, int width, int v, int ones) {
int index = 0;
int innerones = ones;
for (int i = 0; i < darray[0].length; i++) {
for (int j = 0; j < darray.length; j++) {
if (darray[j][i] == 1) {
--innerones;
if (innerones == 0) {
innerones = ones;
index = i + 1;
--v;
if (i + 1 != width) {
System.out.println("Vertical Cuts " + index);
}
if (v == 0) {
break;
}
}
}
}
}

}

private static void divideH(int[][] darray, int height, int h, int ones) {
int index = 0;
int innerones = ones;
for (int i = 0; i < darray.length; i++) {
for (int j = 0; j < darray[i].length; j++) {
if (darray[i][j] == 1) {
--innerones;
if (innerones == 0) {
innerones = ones;
index = i + 1;
--h;
if (i + 1 != height) {
System.out.println("Horizontal Cuts " + index);
}
if (h == 0) {
break;
}
}
}
}
}

}
}``````

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

``````const m = 4;
const n = 5;

const hCutNumber = 1;
const vCutNumber = 3;

const matrix = [
[1, 1, 1, 1, 1],
[0, 0, 1, 1, 1],
[0, 1, 1, 1, 1],
[1, 0, 1, 1, 1],
];

const flat = matrix.reduce((acc, next) => {
return acc.concat(next);
}, []);

let accumlator = {
matrixSum: 0,
rowTotals: [],
columnTotals: new Array(5).fill(0),
};

let rowTotal = 0;
let columnCount = 1;

const dimensions = flat.reduce((acc, value, index) => {
rowTotal = rowTotal + value;
if (index > 0 && (index + 1) % n === 0) {
acc.rowTotals.push(rowTotal);
acc.matrixSum += rowTotal;
rowTotal = 0;
}
acc.columnTotals[columnCount - 1] += value;

if (columnCount === n) {
columnCount = 1;
} else {
columnCount++;
}

return acc;
}, accumlator);

console.log(dimensions);

console.log(
findCutIndexes(vCutNumber, dimensions.matrixSum, dimensions.columnTotals)
);

function findCutIndexes(numberOfCuts, matrixSum, matrixTotals) {
let cutIndexes = [];
let limit = matrixSum / (numberOfCuts + 1);
let len = matrixTotals.length;
let total = 0;
for (var i = 0; i < len; i++) {
total += matrixTotals[i];
if (total === limit && i !== len - 1) {
cutIndexes.push(i);
total = 0;
}
}

return cutIndexes;
}``````

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.