Interview Question
Country: India
Hey nice approach.
Your o/p works if we take input in the sorted order.
abc,def,yz
Anyways, We can sort the strings before calling the PrintSorted func.
Can you suggest me a good algo which can sort strings( in general) and also in this case where only the first char in each string is sufficient to sort the strings.
e.g.
I/P: DEFG YZ ABC
O/P: ABC DEFG YZ
Hi vikdp01,
This is question is not sufficient to understand. Is it compulsory to take only one character from each strings.
I am writing the algo for this
Take a hash which will look like this [Assuming the input given in in sorted order]
A->B->C->D
D->E->F
Y->Z
Now we can take the first element of every row
ADY
Increment last row by one and carry on like
ADZ
AEY
AEZ
Please let me know if I am doing something wrong here
vector<string> get_sorted(vector<vector<int>>& lists)
{
vector<string> vec;
vector<int> index;
for(size_t i = 0; i < lists.size(); ++i)
{
if(lists[i].size() == 0)
{
return vec;
}
int elt = list[i][0];
vector<int>::iterator it = list[i].begin();
while(it != list[i].end() && elt >= list[*it][0])
{
++it;
}
index.insert(it, elt);
}
string str;
for(size_t i = 0; i < index.size(); ++i)
{
str += list[index[i]].pop();
}
vec.push_back(str);
vector<string> strs = get_sorted(lists);
for(size_t i = 0; i < strs.size(); ++i)
{
vec.push_back(strs[i]);
}
return vec;
}
// question is nothing but printing the cross-products
void cross_product(vector<string>& strs)
{
int p = 1;
for (int i=0; i < strs.size(); i++) p *= strs[i];
for (int i=0; i < p ; i++)
{
int j = p;
for (int k=0; k < strs.size(); k++)
{
int s = strs[k].size();
j /= s;
cout << strs[j][ (i/j)%s ] << endl;
}
}
}
// question is nothing but printing the cross-products
void cross_product(vector<string>& strs)
{
int p = 1;
for (int i=0; i < strs.size(); i++) p *= strs[i];
for (int i=0; i < p ; i++)
{
int j = p;
for (int k=0; k < strs.size(); k++)
{
int s = strs[k].size();
j /= s;
cout << strs[j][ (i/j)%s ] << endl;
}
}
}
- Anonymous March 23, 2012