Amazon Interview Question
SDE-3sCountry: United States
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
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
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
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;
}
}
}
}
}
}
}
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;
}
}
}
}
}
}
}
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;
}
}
- Frank May 17, 2020