Google Interview Question Software Engineers
Country: United States
//Time Complexity: Worst case: O(NM) where N is the number of words in input and M is the number of rows.
public class Solution
{
public String[] arrange(String[] words,int rows, int cols)
{
if(words==null||words.length==0||rows<=0||cols<=0)
{
return null;
}
String[] arr=new String[rows];
int i=0;
for(int j=0;j<arr.length;j++)
{
int c=0;
int wordCount=0;
int spaceCount=0;
while(c+arr[i].length()<=cols)
{
wordCount++;
if(c+arr[i].length()<cols)
{
spaceCount++;
c++;
}
c+=arr[i++].length();
if(i==arr.length)
{
i=0;
}
}
StringBuilder sb=new StringBuilder();
spaceCount=spaceCount+((c!=0)?cols-c:0);
sb.append(wordCount + " words " + spaceCount+ " spaces" );
arr[j]=sb.toString();
}
return arr;
}
}
Time complexity: O (row * col)
// Example program
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int findNumberOfWords(vector<string> stringList, int row, int col){
int r = 0, c = 0, i = 0;
int res = 0;
while (r < row){
cout << r << " " << c << " " << stringList[i] << " " << res << endl;
if (stringList[i].length() > col) return res;
if (stringList[i].length()+ (c==0?0:1) + c <= col) {
if (c + stringList[i].length()+ (c==0?0:1) == col) r++;
c = (c + stringList[i].length()+ (c==0?0:1)) % col;
i = (i + 1) % stringList.size();
res++;
} else {
r++; c = 0;
}
}
return res;
}
int main()
{
//Input
vector<string> stringList = {"aa", "aaa"};
int row = 2;
int col = 9;
cout << findNumberOfWords(stringList, row, col) << endl;
return 0;
}
TimeComplexity O(mn)
public class WordsCounting {
public static void main(String[] args) {
String words[] = new String[] { "Do" , "run"};
int row = 2 , col = 9;
System.out.println(countWords( words , row , col));
}
private static int countWords(String[] words, int row, int col) {
// TODO Auto-generated method stub
int wordCount = 0;
int rowIterator = 0;
int wordIterator = 0;
int remainingCol;
while ( rowIterator < row ) {
remainingCol = col;
while ( remainingCol > 0 && words[wordIterator].length() <= remainingCol) {
wordCount++;
// update remainingCol , takes wordspacing into account
remainingCol = remainingCol - words[wordIterator].length() - 1;
wordIterator++;
if (wordIterator == words.length)
wordIterator = 0;
}
// IF the word length in any case doesn't fit in the column , increment the wordIterator
if ( words[wordIterator].length() > col) {
wordIterator++;
if (wordIterator == words.length)
wordIterator = 0;
}
//else do a row increment
else {
rowIterator++;
}
}
return wordCount;
}
}
import java.util.*;
public class stringifyMe {
public static void main(String[] args) {
System.out.println(Arrays.toString(countWord( new String [] {"Do", "Run"}, 9,2)));
}
public static int [] countWord (String [] wordList, int cols, int rows) {
int [] charCount = new int [rows]; //number of chars used
int [] wordCount = new int [rows]; //number of words used
int N = wordList.length; //number of available words in the list
int wordLoc = 0; //location of the current word (start from the first word)
for (int i = 0; i < rows; i++) { //Loops over the rows
while(true) {
int temp = wordList[wordLoc].length();
if (temp > cols-charCount[i]) break; //Quit a row once there are no more spaces available
else { //If there are still space increment
charCount[i] += temp+1;
wordCount[i] += 1;
wordLoc = (wordLoc + 1) % N; //Index of the word should stay between 0 -> N-1
}
}
}
return wordCount;
}
}
void ConvertWordsinRowCol(const vector<string>& vWords, int numRows, int numCols, vector<string>& LineofWords)
{
int cols = 0, rows = 0;
int sizes = vWords.size();
int last = 0;
bool first = true;
string rowStr;
while (rows < numRows)
{
while (cols < numCols)
{
for (int i = last; i < sizes; i++)
{
if (first)
cols += vWords[i].length();
else
cols += vWords[i].length() + 1;
if (cols > numCols)
{
last = i; break;
}
if (first)
first = false;
else
rowStr += ' ';
rowStr += vWords[i];
}
if (cols <= numCols) last = 0;
}
LineofWords.push_back(rowStr);
rows++; cols = 0;
first = true; rowStr = "";
}
}
void WordFitRow(const std::vector<std::string>& str, int row, int col){
int count =0;
int strLength = str.size();
while(row--){
int length =0;
while(length+str[count%strLength].size() <=col){
std::cout << str[count%strLength];
length = length + str[count%strLength].size()+1;
count++;
if(length+str[count%strLength].size() <=col) std::cout << " ";
}
if(length!=0)std::cout << std::endl;
}
}
public class Main {
public static void main(String[] args) {
List<String> words = new ArrayList<>();
words.add("Do");
words.add("Run");
System.out.println(CountWordsInMatrix.countWordsInMatrix(words, 2, 9));
}
}
public class CountWordsInMatrix {
public static int countWordsInMatrix(List<String> words, int rows, int columns) {
if (words == null || words.size() == 0 || rows <= 0 || columns <= 0) {
return 0;
}
int countWords = 0;
int numberOfWord = 0;
for (int i = 0; i < rows; i++) {
int freeColumns = columns;
while (freeColumns > 0) {
for (int j = numberOfWord; j < words.size(); j++) {
freeColumns = numberOfFreeColumns(freeColumns, words.get(j).length(), freeColumns == columns);
if (freeColumns >= 0) {
countWords++;
} else {
numberOfWord = j;
break;
}
}
}
}
return countWords;
}
public static int numberOfFreeColumns(int freeColumn, int wordLength, boolean isBeginning) {
if (freeColumn < wordLength) {
return -1;
}
if (isBeginning) {
return freeColumn - wordLength;
}
return freeColumn - wordLength - 1;
}
}
public static void main(String[] args) {
String list[]={"Do","Run","Jump","Hide"};
int c =20;
int r=4;
int count =findwc(list,c,r);
}
private static int findwc(String[] list, int c, int r) {
String result="";
int count =0;
int currentrow=0;
int i=0;
while(currentrow<r){ //through rows
while(true){
if(result.length()>=c){ //checking number of columns used
break;
}
if(result.length()>0){ // checking when to add space
result=result+" ";
}
if(i==list.length){ // resetting list iterator
i=0;
}
result=result+list[i];
count++;
i++; //1 //2 //1
}
System.out.println(result);
currentrow++;
result="";
}
System.out.println(count);
return count;
}
}
/*
Given a list of words, and the number of rows and columns, return the number of words that can be fit into the rows and columns by stringing together each consecutive word. If the next word doesn't fit in the same line, it should move to the next line. Find an efficient solution for this. For eg.
List of words: { "Do", "Run" }
Number of columns: 9
Number of rows: 2
First row: "Do Run Do" (7 letters + 2 spaces fit into 9 columns)
Second row: "Run Do" (Only 2 words fit into 9 columns)
*/
#include <vector>
#include <string>
#include <iostream>
void WordFitRow(const std::vector<std::string>& str, int row, int col){
int count =0;
int strLength = str.size();
while(row--) {
int length =0;
while(length+str[count%strLength].size() <=col) {
std::cout << str[count%strLength];
length = length + str[count%strLength].size()+1;
count++;
if(length+str[count%strLength].size() <=col) std::cout << " ";
}
if(length!=0) std::cout << std::endl;
}
}
int main(){
std::vector<std::string> v = { "Do", "Run" };
WordFitRow(v, 2, 9);
return 0;
}
public class Solution {
public static void main(String [] args) {
String [] array = {"DO", "RUN"};
print(array, 2, 9);
}
public static void print(String [] words, int row, int column) {
int word = 0;
int i = 0;
int j = 0;
while (i < row) {
if (words[word].length() <= column-j) {
System.out.print(words[word] + " ");
j = j + 1 + words[word].length();
word++;
word %= words.length;
} else {
System.out.println();
j = 0;
i++;
}
}
}
}
def build_text_grid(w_list, row, col):
i = 0
j = 0
w = 0
words_num = 0
while i < row:
word = w_list[w]
added = False
if j == 0 and len(word) <= col:
j = len(word)
added = True
elif len(word) + 1 <= col - j:
j += len(word) + 1
added = True
else:
i += 1
j = 0
if added:
words_num += 1
w += 1
if w == len(w_list):
w = 0
return words_num
print build_text_grid(["do", "more"], 2, 20)
thanks for posting question. But as posted its not clear what is required in question. Why can't second row be "run do do" (7 letters and 2 spaces fit in second row)
- Anonymous July 15, 2016