## Google Interview Question for SDE1s

Country: United States

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

To me the approach seems like :
Pick the max length string, see if it fits in 10-width, if yes fit it in. Then for the remaining width see if there is a string that can fit in, if yes fit it in too.
Continue this process until you fit all strings, and count number of lines.
Intuitively this should give minimum number of lines, the reason is once you fit in the max length string, you have 1 line lost already.

Implementation wise, I can have 2 heaps: 1 max, 1 min.
Pick the top from max and fit it in first, if there is space remaining, peek from min see if it fits in remaining space.
Continue to fill up the lines.

Any comments would be most welcome.

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

You misunderstood the question. The words are ordered by column. You cannot shuffle the words.

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

``````public static int minRows(String[] strings, int K) {
int rows = 0;

while (rows < Integer.MAX_VALUE) {
rows++;

if (testMinRows(strings, rows, K)) return rows;
}

return -1;
}

private static boolean testMinRows(String[] strings, int rows, int K) {
for (int i = 0; i < rows; i++) {
int rowCharCount = 0;
int space = 0;

for (int j = i; j < strings.length; j += rows) {
rowCharCount += space;
rowCharCount += strings[j].length();
space = 1;

if (rowCharCount > K) return false;
}
}

return true;
}``````

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

Binary search can be used?

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

Binary Search can be used??

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.