Google Interview Question
SDE-2sCountry: United States
Interview Type: Phone Interview
How about this compact code?
public static void main(String[] args) {
// TODO Auto-generated method stub
String[][] input = { { "abc", "def", "gh" },
{ "f", "g" },
{ "qrt","xyz","pqr" } };
print(input, "", 0);
}
private static void print(String[][] input, String current, int row) {
if(row == input.length){
System.out.println(current);
return;
}
for(int i = 0; i < input[row].length; i++)
print(input, current + input[row][i], row + 1);
}
void stringComb(vector<vector<std::string>> &myStrings) {
vector<vector<std::string>>::iterator itr = myStrings.begin();
if (itr != myStrings.end()) {
std::string newStr = "";
stringComb(myStrings, itr, newStr);
}
}
void stringComb(vector<vector<std::string>> &myStrings, vector<vector<std::string>>::iterator itr, std::string myString) {
static int printCount = 0;
if (itr == myStrings.end()) {
printf("%d: %s\n", ++printCount, myString.c_str());
return;
}
for (auto &innerItr : *itr) {
std::string newStr = myString + innerItr;
stringComb(myStrings, itr+1, newStr);
}
}
Take two consecutive rows, concatenate the strings as a cartesian product of the rows and merge them into a single row. Repeat the steps until only one row is left. The procedure can follow either a top-down approach or a bottom-up approach, with the initial rows being the first two or the last two respectively.
#should work for arbitrarily long sub list
list_of_list = [["abc", "def", "ghi"],
["111", "222", "333", "444"],
["xxx", "yyy", "zzz"]]
c = 0
while True:
try:
line = "".join([line[c] for line in list_of_list])
except:
break
else:
print line
c += 1
public class TwoDimensionMerge {
public static void main(String asd[]) {
String[][] input = {{"abc", "def", "gh"},
{"f", "g"},
{"qrt", "xyz", "pqr"},
{"ugur","1"}};
for (int i = 0 ; i < input.length-1 ; i++ ) {
input[i+1] = merge(input[i], input[i+1]);
}
for ( int i = 0 ; i < input[input.length-1].length ; i++ ) {
System.out.println(input[input.length-1][i]);
}
}
public static String [] merge (String [] input1, String [] input2) {
String [] output = new String[input1.length * input2.length];
int i = 0;
for (int j = 0 ; j < input1.length ; j++ ) {
for (int k = 0 ; k < input2.length ; k++ ) {
output[i++] = input1[j] + input2[k];
}
}
return output;
}
}
void convert_from_one_form_to_another(std::vector<std::vector<std::string>> &s,int row,int max_row,std::string &new_string)
{
if(row==max_row)
{
std::cout<<"\n"<<new_string;
}
else
{
for(int i=0;i<s[row].size();i++)
{
new_string.append(s[row][i]);
int pos=new_string.size()-s[row][i].size();
convert_from_one_form_to_another(s,row+1,max_row,new_string);
new_string.erase(pos,s[row][i].size());
}
}
return;
}
Although the question says print, you'd probably want a usable return value...
Here's a c# recursion sample
class Program
{
public static void Main(string[] args)
{
var classifications
= new List<List<String>>{
new List<String> {"1","2","3","4"},
new List<String> {"1","2","3"},
new List<String> {"1","2","3"}
};
IList<String> combinations = getPermutations(classifications);
foreach (var element in combinations)
{
Console.WriteLine(element.ToString());
}
Console.Write("Press any key to continue . . . ");
Console.ReadKey(true);
}
public static IList<String> getPermutations(List<List<String>> classifications)
{
if(classifications ==null || classifications.Count == 0)
return null;
if(classifications.Count == 1)
return classifications[0];
var broaderClassification = classifications[0];
var finerClassifications = classifications.Skip(1)
.Take(classifications.Count-1).ToList();
return getPermutations(broaderClassification, finerClassifications);
}
private static IList<String> getPermutations (IList<String> broaderClassification,
List<List<String>> finerClassifications)
{
if(finerClassifications.Count==1)
{
return combine(broaderClassification, finerClassifications[0]);
}
else
{
return combine(broaderClassification,
getPermutations(finerClassifications[0],
finerClassifications.Skip(1)
.Take(finerClassifications.Count-1).ToList()));
}
}
private static IList<String> combine(IList<String> list1,
IList<String> list2)
{
IList<String> result = new List<String> (list1.Count * list2.Count);
foreach(var item1 in list1)
foreach(var item2 in list2)
result.Add(item1 + " " + item2);
return result;
}
}
shared my super clean C++ code:
void func(vector<vector<string>>& dict, vector<string>& row,
vector<vector<string>>& matrix, string result, int ind){
if(ind == dict.size()) {
row.push_back(result);
return;
}
for(int i=0; i<dict[ind].size(); ++i) {
func(dict,row,matrix, result+dict[ind][i], ind+1);
if(ind == 0){
matrix.push_back(row);
row.clear();
result="";
}
}
}
vector<vector<string>> func(vector<vector<string>>& dic) {
vector<string> row;
vector<vector<string>> matrix;
func(dic, row, matrix, "",0);
return matrix;
}
- Anonymous January 30, 2014