Interview Question
Country: United States
can you clarify the following?
if page break is happening only once, then what do you mean by return all positions of pixels?
Do you mean breaking the matrix in to multiple pages such that all rows between two white rows are skipped?
Also, if its a Nx1000 matrix isn't it mean N rows and 1000 columns or do you mean to say NxN matrix with N is atmost 1000?
Regards
Sorry I forgot to mention.
Page size is 1000 X 1000, so you have to break the N X 1000 matrix according to the mentioned conditions in 1000 X 1000 matrices.
The program should return the number of pages used to print and the position of pixels on the matrix where the page breaks were applied.
using javascript...
function getPageBreaks(img, N) {
var i=0, prevAllWhite=0, pageLineCount=0, pageBreak=0, breaksStack = [];
while (i < N) {
// isAllWhiteLine just scans the line looking for a black pixel
if (isAllWhiteLine(img, i)) {
prevAllWhite = i;
}
if (++pageLineCount === 1000) {
if (prevAllWhite > 0) {
pageBreak = prevAllWhite;
} else {
pageBreak = pageBreak + pageLineCount;
}
breaksStack.push(pageBreak);
prevAllWhite = 0;
pageLineCount = 0;
}
++i;
}
if (pageLineCount > 0) {
breaksStack.push(pageBreak + pageLineCount);
}
// The number of pages is breaksStack.length
return breaksStack;
}
A greedy algorithm is optimal here. I suppose a good answer would include a proof that this is so.
- eugene.yarovoi December 05, 2011