## Google Interview Question for Software Engineer / Developers

• 0

Country: United States

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

Given info: Width of the page = N, A vector of words (of length K)

For simplification of logic, I assume start index = 1.

Idea: Let l_i be the length of ith word. For a meaningful sentence there must be
at least one space after every word (except the last word). Then total MINIMUM length
needed is [sum(l_i) i=1 to K] + (K-1) = M.

Sanity check: If M>N => not acceptable => error/return

If (N>M), we need to accommodate (N-M) additional spaces after first K-1 words.
Let x = (N-M)/(K-1). y= (N-M)%(K-1).

for each word of first K-1 words:
if word index is <= y => number of spaces next to it = 1+x+1; // default space + additional spaces
else word index >y => number of spaces next to it = 1+x;// default space + additional spaces

Concatenate the words into one string with spaces as defined above.

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

I did not understand the concept of using x and y and how addtional spaces are spread uniformly, can you explain?

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

@daydreamer
Sure, I am assuming you understood till the point: We need to distribute (N-M) spaces across (K-1) words. For example, 12 spaces across 4 words. How will you distribute them evenly? 3,3,3,3. ( 12 / 4). That is the x. But what if it was not exact multiple of 4? example, 14 spaces and 4 words => 4, 4, 3, 3 i.e. floor(14/4 = x) for each word. remaining 2 spaces (14%4 = y ) I just append it to first two words.

I hope this clarifies your doubt.

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

It does, thank you Dilbert

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

For the above example, is 4, 3, 3, 4 better than 4, 4, 3, 3?

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

For the above example, is 4, 3, 3, 4 better than 4, 4, 3, 3?

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

@sw
For such minor details both in interview as well as real word implementation, you can ask them as requirements. If what you suggested is the given requirement, the change in the above algorithm is very trivial. Hope this helps.

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

1. calculate number of space between words: here it is 2
2. calculate number of space to be distributed : here 15-11 = 4
3. each space between words will have additional space: 4/2 and either first or last space will have 4%2 (here 0, so distribution is common) additional space

finally: "DOG<space><space><space>IS<space><space><space>CUTE"

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

This solution is valid if line length is smaller than page width. Not sure if this is always true, maybe need some judgment first.

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

If there is only one word with length less than width (say width is 15 and word length is 5) the above soln may not work.
I think the question is more like justify alignment (refer to css text-align: justify)

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

do we need to distribute the space between words or within words??

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

``````Assuming page width >= lenth of the sentence

1. Calculate the number of words and total letters.
2. if total_words != 1 then
2.1 Extra_width = (page width - total_letter_count)
2.2 space_in_bet_words = total_wrods - 1
2.3 each_word_spacing = Extra_width / space_in_bet_words
2.4 Extra_width = Extra_width % space_in_bet_words
2.5 fill the extra width by putting extra spaces not in between consecutive word rather than first spacing, last spacing, second spacing, second last spacing etc like that.
3. else
3.a align the word in the middle. Divide the extra spaces by half. If not divisible by 2, Then add the extra space in the front (by design). So the style would be more like (<spaces(may be extra one)> <Word> <Spaces>)``````

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

Take this example.
"I am an ordinary student"
Length = 24. Page width = 26.
Words = 5
extra_space = 6
space_in_bet_words = 4
each_word_spacing = 6/4 = 1
Extra_width = 6%4 = 2
So the sentence after alignment :
"I<s><s>am<s>an<s>ordinary<s><s>student"
<s> represents space.

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

1. count no. of spaces in the sentence( say nos)
2. calculate diff = page width - sentence length - nos
3. calculate diff/nos. replace all spaces by this number of spaces.
4. calculate xtra = diff%nos. add one extra space to every space and dcrement xtra untill xtra is zero.

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

Why point 4 is needed?

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

``````char* Adjust(char* s, int width)
{
//TODO: argument validation

//
//get number of words
//
int cWords = 0; // number of words
bool IsWord = false;
char* p = s;    // pointer to s

while(*p != '\0')
{
if(*p==' ')
{
IsWord = false;
}
else
{
if(!IsWord)
{
IsWord = true;
cWords++;
}
}
p++;
}

//
//compute extra space distribution
//

int cExtraSpaces = width - strlen(s);

int dist, remain;
if(cWords > 1)
{
dist = cExtraSpaces/(cWords-1);
remain = cExtraSpaces%(cWords-1);
}
else
{
ASSERT(FALSE);
}

//
//copy and insert spaces.
//

//create buf for new string
char* s2 = new char[width+1];
s2[width]='\0';

p=s;
int idxS2=0; // index to iterate through s2
IsWord = false;
int cWords2 = 0; // word count visited in s

while(*p != '\0')
{
if(*p == ' ')
{
IsWord = false;
}
else
{
if(!IsWord)
{
cWords2++;
IsWord = true;
if (cWords2 > 1)
{
int cSpacesInsert = cExtraSpaces;
if(remain>0)
{
cSpacesInsert++;
remain--;
}

for(int i=0;i<cSpacesInsert;++i)
{
s2[idxS2++]=' ';
}
}
}
}

s2[idxS2++] = *p;
}

return s2;
}``````

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

``seriously dude!! you asking this question ? :P``

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

The question itself is pretty vague, can there be spaces between chars in a word as well? Otherwise this seems trivial. Considering a line with a single word, since there should be no spaces before and after, how would that case work?

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

I think requirement is not clear. Think of an use case where word is just "TEST" so how would you align this word on entire page width.

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

``````public void adjustPageWidth(String s, int pageWidth){
if(s.length()>1){
String [] words = s.split("\\s");
int space = words.length-1;
int totalSpace = space+(pageWidth-s.length());
space = totalSpace/(words.length-1);
int xtraSpace = totalSpace%(words.length-1);
StringBuffer str = new StringBuffer();
if(s.length()==pageWidth){
}
else{
for(int i =0;i<words.length;i++){
int temp = space;
str.append(words[i]);
while(temp>0){
str.append(" ");
temp--;
}
if(xtraSpace>0){
str.append(" ");
xtraSpace--;
}

}
}
System.out.println(str);
}
System.out.println("orginal string-->" + s);
}``````

This should work for strings with length>1. The algorithm inserts the spaces in between the words. But here the complexity is not O(n).

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

It may or may not be adjusted. Like if the sentence is
"Dog<s><s><s>is<s>good" If page size is 13 - it is not adjusted.

``````if(s.length()==pageWidth){

}

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

qss

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

``````#include <iostream>
#include <string>
using namespace std;

int main()
{
char str[] = "The quick brown fox jumps over the lazy dog";
int  wd = 200;
int  num_space = 0;
int  num_allspace;
int  mul_space;
int  temp1,temp2;

int len = strlen(str);

if(wd<len){
cout<<"space not enough!"<<endl;
} else if(wd == len){
cout<< str << endl;
} else {
for(int i=0; i<len; i++){
if(str[i]==' ') num_space += 1;
}
num_allspace = wd - len;
mul_space = num_allspace/num_space;
temp1 = num_allspace%num_space;

for(int i=0; i<len; i++){
if(str[i]==' '){
temp2 = (temp1 > 0)?1:0;
cout << string(mul_space+temp2,' ');
temp1 -=1;
}
else
cout << str[i];
}
}
return 0;
}``````

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

``````import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

Pattern pattern = Pattern.compile( "\\s" );
public static final int NUMBER_OF_CHARACTERS = 15;

if ( isNull( input ) ) {
return null;
}

if ( input.isEmpty() ) {
return returnSpaces();
}

List<String> list = new ArrayList<String>();

String res = "";
int count = 0;
for ( String str : list ) {

if ( count >= 1 ) {
res += "\n";
}

count++;
}

return res;
}

private boolean isNull(String input) {

if ( input == null ) {
return true;
}

return false;
}

private String returnSpaces() {
String res = "";
for ( int i = 0; i < NUMBER_OF_CHARACTERS; i++ ) {
res += " ";
}

return res;
}

private void addString(String input, List<String> list) {

if ( input.length() < NUMBER_OF_CHARACTERS ) {
}
else {
splitInput( input, list );
}
}

private void splitInput(String input, List<String> list) {

int startIndex = 0, endIndex = NUMBER_OF_CHARACTERS;

while ( true ) {

list.add( input.substring( startIndex, endIndex ) );

if ( endIndex == input.length() ) {
break;
}

startIndex = endIndex;
endIndex = endIndex + ( input.length() - endIndex );
}
}

int spaceLeft = getNumberOfSpacesLeft( input, NUMBER_OF_CHARACTERS );
int spaceDiff = 0;
Matcher matcher = pattern.matcher( input );

List<Integer> minSpaceList = new ArrayList<Integer>();
StringBuilder str = new StringBuilder( input );
while ( matcher.find() ) {

spaceDiff = matcher.end() - matcher.start();
System.out.println( "start: " + matcher.start() + " end: " + matcher.end() + " spaceDiff: " + spaceDiff
+ " spaceLeft: " + spaceLeft );

if ( spaceDiff < spaceLeft ) {
}
}

if ( !minSpaceList.isEmpty() ) {

System.out.println( "minSpaceList size: " + minSpaceList.size() + " space size: "
+ ( spaceLeft / minSpaceList.size() ) );

int offset = 0;

for ( int index : minSpaceList ) {
System.out.println( "index: " + index );

index += offset;
if ( minSpaceList.size() == 1 ) {
int indx = index;
for ( int i = 0; i < 2; i++ ) {
for ( int j = 0; j < ( spaceLeft / 2 ); j++ ) {
str.insert( indx + j, " " );
}

indx = str.length();
}
}
else {
for ( int i = 0; i < ( spaceLeft / minSpaceList.size() ); i++ ) {
str.insert( index + i, " " );
offset++;
}
}
}
}

return str.toString();
}

private int getNumberOfSpacesLeft(String input, int numberOfCharacters) {

return numberOfCharacters - input.length();
}
}``````

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

python:

``````import sys

def leftRightJustify(words, width):
# print words as a paragraph with (width) width
# each line shall be left and right justified
i = 0
while i < len(words):
w_len = len(words[i])
if w_len > width:
print
print 'ABORT: CANNOT CONTAIN WORD'
return
# current length of line
c_len = 0
line = []
n_space = width
n_words = 0
while c_len + w_len <= width:
line.append(words[i])
# current length shall contain a space for a whitespace
c_len += w_len+1
n_words += 1
i += 1
if not (i < len(words)):
break
w_len = len(words[i])
# we added n_words number of extra whitespaces in the length
n_space = width - c_len + n_words + 1
# at least put this number of spaces between two words
n_space_each  = n_space / (n_words-1)
# if we equally distribute all spaces inbetween the words
# how many extra spaces we are left with
n_extra_space = n_space % (n_words-1)

for n in xrange(0, len(line)):
sys.stdout.write(line[n])
sys.stdout.write(' ' * n_space_each)
if n_extra_space > 0:
sys.stdout.write(' ')
n_extra_space -= 1
print

if __name__ == '__main__':
words = "In my younger and more vulnerable years my father gave me some advice that I've been turning over in my mind ever since. 'Whenever you feel like criticizing any one,' he told me, 'just remember that all the people in this world haven't had the advantages that you've had.' He didn't say any more, but we've always been unusually communicative in a reserved way, and I understood that he meant a great deal more than that. In consequence, I'm inclined to reserve all judgments, a habit that has opened up many curious natures to me and also made me the victim of not a few veteran bores. The abnormal mind is quick to detect and attach itself to this quality when it appears in a normal person, and so it came about that in college I was unjustly accused of being a politician, because I was privy to the secret griefs of wild, unknown men. Most of the confidences were unsought - frequently I have feigned sleep, preoccupation, or a hostile levity when I realized by some unmistakable sign that an intimate revelation was quivering on the horizon; for the intimate revelations of young men, or at least the terms in which they express them, are usually plagiaristic and marred by obvious suppressions. Reserving judgments is a matter of infinite hope. I am still a little afraid of missing something if I forget that, as my father snobbishly suggested, and I snobbishly repeat, a sense of the fundamental decencies is parcelled out unequally at birth.".split(' ')
leftRightJustify(words, 50)``````

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

Oops, I missed a word length check in the inner while loop...

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

Nevermind, this code still has little bugs...

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

``````import sys

def leftRightJustify(words, width):
# print words as a paragraph with (width) width
# each line shall be left and right justified
i = 0
while i < len(words):
w_len = len(words[i])
if w_len > width:
print
print 'ABORT: CANNOT CONTAIN WORD:'
print words[i]
return
# current length of line
c_len = 0
line = []
n_space = width
n_words = 0
while c_len + w_len <= width:
line.append(words[i])
# current length shall contain a space for a whitespace
c_len += w_len+1
n_words += 1
i += 1
if not (i < len(words)):
break
w_len = len(words[i])
if w_len > width:
print
print 'ABORT: CANNOT CONTAIN WORD:'
print len(words[i])
print words[i]
return
# we added n_words number of extra whitespaces in the length
n_space = width - c_len + n_words
# at least put this number of spaces between two words
if n_words == 1:
n_space_each = 0
else:
n_space_each  = n_space / (n_words-1)
# if we equally distribute all spaces inbetween the words
# how many extra spaces we are left with
if n_words == 1:
n_extra_space = 0
else:
n_extra_space = n_space % (n_words-1)
for n in xrange(0, len(line)):
sys.stdout.write(line[n])
sys.stdout.write(' ' * n_space_each)
if n_extra_space > 0:
sys.stdout.write(' ')
n_extra_space -= 1
print

if __name__ == '__main__':
words = "In my younger and more vulnerable years my father gave me some advice that I've been turning over in my mind ever since. 'Whenever you feel like criticizing any one,' he told me, 'just remember that all the people in this world haven't had the advantages that you've had.' He didn't say any more, but we've always been unusually communicative in a reserved way, and I understood that he meant a great deal more than that. In consequence, I'm inclined to reserve all judgments, a habit that has opened up many curious natures to me and also made me the victim of not a few veteran bores. The abnormal mind is quick to detect and attach itself to this quality when it appears in a normal person, and so it came about that in college I was unjustly accused of being a politician, because I was privy to the secret griefs of wild, unknown men. Most of the confidences were unsought - frequently I have feigned sleep, preoccupation, or a hostile levity when I realized by some unmistakable sign that an intimate revelation was quivering on the horizon; for the intimate revelations of young men, or at least the terms in which they express them, are usually plagiaristic and marred by obvious suppressions. Reserving judgments is a matter of infinite hope. I am still a little afraid of missing something if I forget that, as my father snobbishly suggested, and I snobbishly repeat, a sense of the fundamental decencies is parcelled out unequallyiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii at birth. unequallyiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii".split(' ')
print '11111000001111100000111110000011111000001111100000'
leftRightJustify(words, 50)``````

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.