Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;

vector<vector<string> > sets;
vector<string> cs;

void print(int k) {

	if(k == sets.size()) {
		for(auto &x : cs) {
			cout << x << " ";
		}
		cout << endl;
	}
	else {

		for(int i = 0; i < sets[k].size(); i++) {
			cs.push_back(sets[k][i]);
			print(k+1);
			cs.pop_back();
		}


	}

}


int main () {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	sets = {{"quick", "slow"}, {"brown", "red"}, {"fox", "dog"}};

	print(0);
	return 0;
}

- Anonymous October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the time complexity?

- mikewhity October 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

O(A1 * A2 * ... * An) where A1 is the number of elements of the first set, etc

- Anonymous October 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Algo

call recursively for each position after adding every string in current position

//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
	if(pos==n){print v;return;}
	for i from 0 to list[pos].size()
		v.push_back(list[pos][i])
		print(pos+1,v);
		v.pop_back();
}

- kevseb1993 October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
			}
		}
	}

- kim October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}

- Anonymous October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You will need to remove last inserted element after the recursive call in your for loop.

- next_big_gig October 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using backtracking.

void printRec(String[][] arrays, int index, String[] res){
		
		if( index >= arrays.length ){
			System.out.println( Arrays.toString(res) );
			return;
		}
		
		String[] cur = arrays[index];
		
		for( int i = 0; i < cur.length; i++ ){
			res[index] = cur[i];
			printRec(arrays, index+1, res);
		}
		
	}

- m@}{ October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- ahj October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Man what does if __name == '__main__':
...
do?

- Kush October 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;	
	}            
    }

- Ehsan October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo

call recursively for each position after adding every string in current position

//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
	if(pos==n){print v;return;}
	for i from 0 to list[pos].size()
		v.push_back(list[pos][i])
		print(pos+1,v);
		v.pop_back();
}

- kevseb1993 October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo

call recursively for each position after adding every string in current position

//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
	if(pos==n){print v;return;}
	for i from 0 to list[pos].size()
		v.push_back(list[pos][i])
		print(pos+1,v);
		v.pop_back();
}

- kevseb1993 October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo

call recursively for each position after adding every string in current position

//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
	if(pos==n){print v;return;}
	for i from 0 to list[pos].size()
		v.push_back(list[pos][i])
		print(pos+1,v);
		v.pop_back();
}

- kevseb1993 October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo

call recursively for each position after adding every string in current position

//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
	if(pos==n){print v;return;}
	for i from 0 to list[pos].size()
		v.push_back(list[pos][i])
		print(pos+1,v);
		v.pop_back();
}

- kevseb1993 October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo

call recursively for each position after adding every string in current position

//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
	if(pos==n){print v;return;}
	for i from 0 to list[pos].size()
		v.push_back(list[pos][i])
		print(pos+1,v);
		v.pop_back();
}

- kevseb1993 October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }

- s/w dev October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }
    }

- Hafeez Jaffer October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }
    }

- Hafeez Jaffer October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }
    }

- Hafeez Jaffer October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }
    }

- Hafeez Jaffer October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }
    }

- Hafeez Jaffer October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }
    }

- Hafeez Jaffer October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }
    }

- Hafeez Jaffer October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }
    }

- Hafeez Jaffer October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }
    }

- Hafeez Jaffer October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }
    }

- Hafeez Jaffer October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import Control.Monad
import Data.List
 
ioAction :: [[String]] -> IO ()
ioAction input = forM_ (sequence input ) $ putStrLn . intercalate " "

-- Test
main = ioAction [["quick","slow"],["brown","red"],["fox","dog"]]

- gonzaw308 October 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}
}

- rgaut October 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- jllaca October 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

String s1[]={"1","2"};
String s2[]={"A","B"};
String s3[]={"X","Z"};
for (int i = 0; i < s1.length; i++) {
for (int j = 0; j < s2.length; j++) {
for (int k = 0; k < s3.length; k++) {
System.out.println(s1[i]+"-"+s2[j]+"-"+s3[k]);
}
}
}

- shoeb Siddiqui October 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

String s1[]={"1","2"};
String s2[]={"A","B"};
String s3[]={"X","Z"};
for (int i = 0; i < s1.length; i++) {
for (int j = 0; j < s2.length; j++) {
for (int k = 0; k < s3.length; k++) {
System.out.println(s1[i]+"-"+s2[j]+"-"+s3[k]);
}
}
}

- Shoeb Siddiqui October 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);

}

- khunima October 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}		
};

- czhao86 October 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
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();
}
}
}}

- rgaut October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}
}

- alpha October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- rgaut October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }

- alisovenko October 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
        }
    }
};

- xuuubo October 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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());
}

- jovi October 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def main():
sets= [['quick', 'slow'], ['brown', 'red'], ['fox', 'dog']]


stringPrint(sets,0)

def stringPrint(sets,k):
if k==len(sets):
print words
else:
for _w in sets[k]:
words.append(_w)
stringPrint(sets,k+1)
words.pop()

- t88h October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def main():
sets= [['quick', 'slow'], ['brown', 'red'], ['fox', 'dog']]


stringPrint(sets,0)

def stringPrint(sets,k):
if k==len(sets):
print words
else:
for _w in sets[k]:
words.append(_w)
stringPrint(sets,k+1)
words.pop()

- t88h October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
        }
    }

- radhakrishna November 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/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']])

- bilalgce November 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- fmars November 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"]])

- me November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
  };
}());

- JavaScript solution November 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- Flux December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }
}

- Alb_Erc December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

}

- Anonymous December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a global int[] to restore the state. And use recursion to traverse them. It is quite similar as 8 queens game.

- allen.lipeng47 December 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is another Python implementation using itertools:

def combinations(listoflists):
    import itertools
    for elements in list(itertools.product(*listoflists)):
            print ' '.join(elements)

- Murali December 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void PrintAll(List<List<String>> in, String comb, int depth)
    {
        if (depth == in.size()) {
            System.out.println(comb);
        }
        else {
            List<String> lst = in.get(depth);
            for (String s : lst) {
                PrintAll(in, comb + ' ' + s, depth+1);
            }
        }
    }

- pavel.kogan January 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    	
    		
    }
    

    
}

- Davi_singh January 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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')])

- valoris February 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}
}

- ord August 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 
*/

- guilhebl September 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More