Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
class Position {
int node;
int index;
}
void print(List<List<String>> input) {
if (input == null || input.size() == 0) {
return ;
}
int root = findNextList(input, 0);
if (root == -1) {
return ;
}
Position[] path = new Position[input.size()];
for (int i=0; i<input.size(); i++) {
path[i] = new Position();
}
dfs(input, root, path, 0);
}
int findNextList(List<List<String>> input, int start) {
for (; start < input.size(); start++) {
if (input.get(start).size() > 0) {
return start;
}
}
return -1;
}
void dfs(List<List<String>> input, int root, Position[] path, int k) {
for (int i=0; i<input.get(root).size(); i++) {
path[k].node = root;
path[k].index = i;
int next = findNextList(input, root+1);
if (next == -1) {
for (int j=0; j<=k; j++) {
System.out.print(input.get(path[j].node).get(path[j].index) + " ");
}
System.out.println();
} else {
dfs(input, next, path, k+1);
}
}
}
public static void wordPerm(ArrayList<ArrayList<String>> lists) {
wordPermUtil(lists,0,"");
}
private static void wordPermUtil(ArrayList<ArrayList<String>> lists, int depth, String cur) {
if (depth == lists.size()) {
System.out.println(cur.trim());
return;
}
for (int i = 0; i < lists.get(depth).size(); i++) {
wordPermUtil(lists, depth + 1, cur + " " + lists.get(depth).get(i));
}
}
Test:
public static void main(String[] args) {
ArrayList<ArrayList<String>> lists = new ArrayList<ArrayList<String>>();
ArrayList<String> list1 = new ArrayList<String>(Arrays.asList("quick","slow");
ArrayList<String> list2 = new ArrayList<String>(Arrays.asList("brown","red"));
ArrayList<String> list3 = new ArrayList<String>(Arrays.asList("fox","dog"));
lists.add(list1);
lists.add(list2);
lists.add(list3);
wordPerm(lists);
}
input_list = [['quick', 'slow'], ['brown', 'red'], ['fox', 'dog']]
def main(str, input):
if(input):
items = input[0]
for item in items:
main(str + ' ' + item, input[1:])
else:
print str
if __name__ == '__main__':
main('', input_list)
Here is a non-recursive solution. The complexity is of course O(N1 x N2 x ... x Nk) where Ni is the number of elements in set i.
public static void main(String[] args) {
String[][] sets = new String[][] {{"quick", "slow"}, {"brown", "red"}, {"fox", "dog"}};
int[] state = new int[sets.length];
int p = 0;
while (true) {
for (int i = 0; i < state.length; i++) {
System.out.print(sets[i][state[i]] + " ");
}
System.out.println();
state[p]++;
while( state[p] == sets[p].length) {
state[p] = 0;
p++;
if (p == sets.length) return;
state[p]++;
}
p = 0;
}
}
public List<string> Combinations(List<List<string>> li)
{
List<string> combinationlist = new List<string>(); ;
StringBuilder sb = new StringBuilder();
int l;
int i;
for(l = 0; l < (li[0].Count); l++)
{
for(i = 1; i < (li.Count); i++)
{
for (int j = 0; j < (li[i].Count); j++)
{
sb.Append((li[0])[l].ToString());
sb.Append(" ");
sb.Append((li[i])[j].ToString());
combinationlist.Add(sb.ToString());
sb.Clear();
}
}
}
return combinationlist;
}
public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}
public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}
ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}
public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}
public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}
ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}
public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}
public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}
ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}
public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}
public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}
ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}
public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}
public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}
ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}
public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}
public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}
ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}
public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}
public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}
ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}
public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}
public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}
ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}
public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}
public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}
ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}
public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}
public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}
ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}
We can implement this recursively:
def combinations(item_lists):
"""Returns a list with all possible lists generated by choosing
one item from each list in item_lists"""
if not item_lists:
return [[]]
combination_list = []
for item in item_lists[0]:
for combination in combinations(item_lists[1:]):
combination_list.append([item] + combination)
return combination_list
Having written this function, we just have to call it and print the values. E.g.:
item_lists = [['quick','slow'],['brown','red'],['fox','dog']]
for combination in combinations(item_lists):
for s in combination:
print s + ' ',
print
Output:
quick brown fox
quick brown dog
quick red fox
quick red dog
slow brown fox
slow brown dog
slow red fox
slow red dog
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void printAllCombination(int index, vector<vector<string> > &list,vector<string> &strs)
{
if(index==list.size())
{
for(int i=0;i<strs.size();i++)
cout<<strs[i]<<" ";
cout<<"\n";
return;
}
for(int i=0;i<list[index].size();i++)
{
strs.push_back(list[index][i]);
printAllCombination(index+1,list,strs);
strs.pop_back();
}
}
int main()
{
vector<vector<string> > list;
vector<string> v;
v.push_back("quick");v.push_back("slow");v.push_back("fast"); list.push_back(v); v.clear();
v.push_back("brown");v.push_back("red"); list.push_back(v); v.clear();
v.push_back("fox");v.push_back("dog");v.push_back("tiger");v.push_back("elephant"); list.push_back(v); v.clear();
printAllCombination(0,list,v);
}
class Solution
{
public:
list<list<string> > comb(list<list<string> > &input)
{
list<list<string> > ans,abl;
if (input.empty()) return ans;
list<string> last=input.back();
input.pop_back();
abl=comb(input);
for (list<string>::iterator ls=last.begin();ls!=last.end();++ls)
{
for (list<list<string> >::iterator lls=abl.begin();lls!=abl.end();++lls)
{
list<string> tmp=*lls;
tmp.push_back(*ls);
ans.push_back(tmp);
}
if (abl.empty())
{
list<string> tmp;
tmp.push_back(*ls);
ans.push_back(tmp);
}
}
return ans;
}
};
#include<iostream>
#include<vector>
#include<string>
using namespace std;
void comb(vector<vector<string> > dict, int s, vector<string> tmp )
{
if(s==dict.size())
{
for(int i=0; i<tmp.size(); i++)
cout<<tmp[i]<<" ";
cout<<"\n";
return;
}
for(int j=0; j<dict[s].size(); j++)
{
tmp.push_back(dict[s][j]);
comb(dict, s+1, tmp);
tmp.pop_back();
}
}
int main()
{
vector<vector<string> > dict;
vector<string> tmp;
tmp.push_back("quick");
tmp.push_back("slow");
dict.push_back(tmp);
tmp.clear();
tmp.push_back("brown");
tmp.push_back("red");
dict.push_back(tmp);
tmp.clear();
tmp.push_back("fox");
tmp.push_back("dog");
dict.push_back(tmp);
tmp.clear();
int s = 0;
vector<int> l;
for(int i=0; i<dict.size(); i++)
l.push_back(0);
int j=0;
vector<string> temp;
comb(dict, s , temp);
return 0;
}
This is a recursive task.
We recurse to N levels, where N is the number of lists of strings. On each level we iterate through all strings in current level list, store its index in int[] array and recurse further. Next level will fill it's own index with its next word. When we came to the next after last level - we have the indexes array filled with indexes of words in matching lists - we just iterate through them and print matching words.
When recursion goes back, the matching index in indexes array is overwritten with next word.
This has O(1) size complexity and O(M^N) time complexity where M is the largest number of words in lists and N is the number of lists.
O(1) size complexity is a big win as almost all solutions, that I see here, use strings concatenations, that would produce lots of garbage
public static void print(String[][] strings) {
permutate (strings, new int[strings.length], 0);
}
public static void permutate (String[][] strings, int[] indexes, int level) {
if (level >= strings.length) {
// we came to end, let's print the string
for (int i = 0; i < strings.length; i++) {
System.out.print(strings[i][indexes[i]]);
System.out.print(" ");
}
System.out.println();
return;
}
for (int i = 0; i < strings[level].length; i++) {
indexes[level] = i;
permutate(strings, indexes, level + 1);
}
}
public static void main(String[] args) {
String[][] strings = {{"quick", "slow"}, {"brown", "red"}, {"fox", "dog"}};
print(strings);
}
class Solution_ListComb {
public:
void PrintListComb(const vector<vector<string> >& List) {
vector<string> curr;
dfs(List, curr, 0, List.size());
}
void dfs(const vector<vector<string> >& List, vector<string>& curr, int k, int n){
if (k == n) {
for (string str : curr)
cout << str << " ";
cout << endl;
return;
}
for (auto word : List[k]) {
curr.push_back(word);
dfs(List, curr, k + 1, n);
curr.pop_back();
}
}
};
#include<iostream>
vector<vector<string> > listE; vector<string> nodeE;
char * itos(int a){char *p=new char;sprintf(p,"%d",a);return p;}
void test(int maxC,string s,unsigned int k)
{
if(s.size()==k){cout<<"\n\t\t String::"<<s;return;}
for(int ii=0;ii<maxC;ii++)
test(maxC,s+itos(ii),k);
}
void recur(int index,string s1,bool flag,unsigned int maxS)
{
//cout<<"\n"<<"\t Si size::"<<s1.size()<<"\t maxS::"<<maxS<<"\tString:"<<s1;
if(s1.size()==maxS && flag){cout<<"\n\t\t Inner ::"<<s1 ;return;}
if(s1.size()==maxS && !flag)
{
cout<<"\n Outter-->::"<<s1;
//for(unsigned int ii=0;ii<2;ii++)
{
s1="";
test(2,s1,4);
}
return;
}
for(unsigned int ii=0;ii<maxS;ii++)
{
//cout<<"\nS::"<<s1;
if(s1.find(itos(ii))!=string::npos)continue;
recur(index+1,s1+itos(ii),flag,maxS);
}
}
int main()
{
//[[quick, slow], [brown, red], [fox, dog]]
string a; nodeE.clear();
a="quick";nodeE.push_back(a);
a="slow";nodeE.push_back(a);
listE.push_back(nodeE);
nodeE.clear();
a="brown";nodeE.push_back(a);
a="red";nodeE.push_back(a);
listE.push_back(nodeE);
nodeE.clear();
a="brown";nodeE.push_back(a);
a="red";nodeE.push_back(a);
listE.push_back(nodeE);
nodeE.clear();
a="fox";nodeE.push_back(a);
a="dog";nodeE.push_back(a);
listE.push_back(nodeE);
recur(0,"",false,listE.size());
}
comb(inputList, new ArrayList<String>(), 0);
public void comb(List<List<String>> list, List<String> res , int k ) {
if(k == list.size()) {
System.out.println(res);
// res.clear();
return;
}
List<String> subList = list.get(k);
for(int i =0 ; i< subList.size(); i++) {
res.add(subList.get(i));
comb(list, res, k+1);
res.remove(subList.get(i));
}
}
#!/usr/bin/python
def combinations(a,list2dstring):
if isASolution(a, list2dstring):
processSolution(a)
else:
nxtCandidates = constructCandidates(a, list2dstring)
for candidate in nxtCandidates:
a += [candidate]
combinations(a, list2dstring)
a.pop()
def isASolution(a, list2dstring):
return len(a) == len(list2dstring)
def processSolution(a):
print " ".join(a)
def constructCandidates(a, list2dstring):
return list2dstring[len(a)]
combinations([], [['quick', 'slow'], ['brown', 'red'], ['fox', 'dog']])
Hope I can get a coding problem as simple as this one tomorrow
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#include<climits>
using namespace std;
void dfs(vector<string>&ret,vector<string> &tmp,vector<vector<string>>&input,int cur){
if(cur==input.size()){
string str=tmp[0];
for(int i=1;i<tmp.size();i++)
str+=" "+tmp[i];
ret.push_back(str);
}else{
for(int i=0;i<input[cur].size();i++){
tmp.push_back(input[cur][i]);
dfs(ret,tmp,input,cur+1);
tmp.pop_back();
}
}
}
vector<string>com(vector<vector<string>>&input){
vector<string>ret,tmp;
if(input.empty())
return ret;
dfs(ret,tmp,input,0);
return ret;
}
int main(){
vector<vector<string>>input;
vector<string>v1,v2,v3;
v1.push_back("a1");
v1.push_back("a1");
v2.push_back("b1");
v2.push_back("b2");
v3.push_back("c1");
v3.push_back("c2");
input.push_back(v1);
input.push_back(v2);
input.push_back(v3);
vector<string>ret=com(input);
for(int i=0;i<ret.size();i++)
cout<<ret[i]<<endl;
return 0;
}
def print_combinations_cheating(word_lists):
import itertools
for t in itertools.product(*word_lists):
print " ".join(t)
def print_combinations_generator(word_lists):
result = [[]]
for words in word_lists:
result = [x+[y] for x in result for y in words]
for combination in result:
print " ".join(combination)
def print_combinations(word_lists):
combinations = [[]]
for words in word_lists:
new_combinations = []
for L in combinations:
for word in words:
new_combinations.append(L + [word])
combinations = new_combinations
for combination in combinations:
print " ".join(combination)
print_combinations([["quick", "slow"], ["brown", "red"], ["fox", "dog"]])
var findCombinations = (function () {
var res;
function getCombinations(list, current, index, el) {
if (index === list.length) {
return res.push(current.slice());
}
for (var i = 0; i < list[el].length; i += 1) {
current[index] = list[el][i];
getCombinations(list, current, index + 1, el + 1);
}
}
return function (list) {
res = [];
getCombinations(list, [], 0, 0);
return res;
};
}());
Too few different codes. Must add my own implementation on C#:
static IEnumerable<string[]> AllCombinations(string[][] lists)
{
long cnt = lists.Aggregate(1L, (curr, list) => curr * list.Length);
for (long mask = 0; mask < cnt; ++mask)
{
string[] next = new string[lists.Length];
long m = mask;
for (int i = 0; i < lists.Length; ++i)
{
next[i] = lists[i][m % lists[i].Length];
m /= lists[i].Length;
}
yield return next;
}
}
This is my version. The complexity is O(length(L1)xlength(L2)x...). Still looking for a better one. Probably there is something better and with less memory usage but mine is easy to read plus using new Java 8 functionality.
public class StringCombinations {
public static void printStringCombinations(List<List<String>> setList) {
printAndCreateStringCombination(setList, new LinkedList<String>());
}
private static void printAndCreateStringCombination(List<List<String>> setList, List<String> combination) {
if (setList.isEmpty()) {
printCombination(combination);
} else {
List<String> set = setList.get(0);
for (String s : set) {
List<String> newCombination = new LinkedList<String>(combination);
newCombination.add(s);
printAndCreateStringCombination(setList.subList(1, setList.size()), newCombination);
}
}
}
private static void printCombination(List<String> combination) {
StringJoiner stringJoiner = new StringJoiner(",");
for (String s : combination) {
stringJoiner.add(s);
}
System.out.println("[" + stringJoiner.toString() + "]");
}
public static void main (String[] args) {
List<List<String>> setList = new LinkedList<List<String>>();
setList.add(Arrays.asList("quick", "slow"));
setList.add(Arrays.asList("brown", "red"));
setList.add(Arrays.asList("fox", "dog"));
printStringCombinations(setList);
}
}
public class RedBrownFox {
String[][] db ={{"red", "brown"},{"fox", "dog"},{"jumps","runs"}};
void printPerm(String sb, int n) {
if(db.length<=n) {
System.out.println(sb);
return ;
}
for(int i=0; i<db[n].length; i++) {
printPerm(sb+db[n][i], n+1);
}
}
public static void main(String[] args) {
RedBrownFox r = new RedBrownFox();
r.printPerm("", 0);
}
}
package p1;
import java.util.ArrayList;
import java.util.List;
public class ListExample
{
public static void main(final String[] args)
{
List<List<List>> sentences = new ArrayList<List<List>>();
List<List> each_sentence = new ArrayList<List>();
ArrayList<String> iob = new ArrayList<String> ();
ArrayList<String> pos = new ArrayList<String> ();
ArrayList<String> word = new ArrayList<String> ();
iob.add("quick");
iob.add("slow");
pos.add("brown");
pos.add("red");
word.add("fox");
word.add("dog");
each_sentence.add(iob);
each_sentence.add(pos);
each_sentence.add(word);
int i=0,j=0,k=0,l=0;
sentences.add(each_sentence);
perm(sentences,i,j,k,l);
}
// System.out.println(sentences.get(0).get(2).get(0));
public static void perm(List<List<List>> sentences, int i,int j,int k, int l){
System.out.print(sentences.get(0).get(i).get(j)+" ");
System.out.print(sentences.get(0).get(i+1).get(k)+" ");
System.out.print(sentences.get(0).get(i+2).get(l)+" ");
l=l+1;
if(l==2)
{
l=0;
k=k+1;
}
if(k==2)
{
k=0;
j=j+1;
}
if(j==2)
{
return;
}
System.out.println();
perm(sentences,i,j,k,l);
}
}
Another solution in Python with O(N1 * N2 * ... * Nk), where Nk is a number of elements in list number k.
def combine(input_list, words=None):
if words is None:
words = []
if input_list is None:
print ' '.join(words)
return
for word in input_list[0]:
combine(input_list[1:] if len(input_list) > 1 else None, words + [word])
combine([('quick', 'slow'), ('brown', 'red'), ('fox', 'dog')])
void recPrintLists(vector < vector < string >> vec , string prefix) {
if (vec.size() == 0) {
cout << prefix + "\n";
return;
}
vector < vector < string >> nextVector(&vec[0] + 1, &vec[0] + vec.size());
for (int i = 0; i < vec[0].size(); i++) {
string newPreFix = prefix + vec[0][i] + " ";
recPrintLists(nextVector , newPreFix);
}
}
public class MultiArrayPermutation {
public static void main(String[] args) {
solveMultiPerms2();
}
public static void solveMultiPerms2() {
String[][] sets = new String[][] {
{ "quick", "slow" },
{ "brown", "red" },
{ "fox", "dog" }
};
List<List<String>> r = new ArrayList<List<String>>();
backtrack(r, sets, new LinkedList<String>(), 0);
printLists(r);
}
private static void printLists(List<List<String>> r) {
for (List<String> list : r) {
for (String string : list) {
System.out.print(string + " ");
}
System.out.println();
}
}
private static void backtrack(List<List<String>> strs, String[][] sets, LinkedList<String> list, int start) {
if (start == sets.length) {
strs.add(new ArrayList<>(list));
} else if (start < sets.length) {
for (int i = 0; i < sets[start].length; i++) {
list.addLast(sets[start][i]);
backtrack(strs, sets, list, start + 1);
list.removeLast();
}
}
}
}
/*
output:
quick brown fox
quick brown dog
quick red fox
quick red dog
slow brown fox
slow brown dog
slow red fox
slow red dog
*/
- Anonymous October 23, 2014