Facebook Interview Question
SDE1sCountry: United States
I can think of a O(n^2) algorithm where N = number of words
1. sort the list of words in increasing order of words length.
2. Take the first word and remove it from the list and add it to a new list representing a group.
3. start from the first word and search this substring in all the words bigger than this. If a substring match occurs then remove it from the list and add to the group list.
4. go back to step 2 and repeat with next word in the list.
5. When the last word of the list is scanned then return the groups of words created so far
This is not perfect, but is something and works ok
def sublists(list):
exit = []
container = []
for elem in list:
tmp_list=[]
for tmp in list:
if elem in tmp:
tmp_list.append(tmp)
container.append(tmp_list)
for elem in container:
add = True
for other in container:
if set(elem) < set(other):
add = False
if add:
exit.append(elem)
return exit
class TrieNode {
public:
TrieNode()
{
terminal_ = false;
}
~TrieNode()
{
for (auto it = children_.begin(); it != children_.end(); ++it) {
delete it->second;
}
children_.clear();
}
TrieNode *InsertChild(char c)
{
TrieNode *n = GetChild(c);
if (n == NULL) {
n = new TrieNode();
children_[c] = n;
}
return n;
}
TrieNode *GetChild(char c)
{
auto it = children_.find(c);
return it == children_.end() ? NULL : it->second;
}
bool terminal_;
private:
unordered_map<char, TrieNode *> children_;
};
class Trie {
public:
void Insert(string const &s)
{
TrieNode *n = &root_;
for (char c : s) {
n = n->InsertChild(c);
}
n->terminal_ = true;
}
TrieNode *GetRoot()
{
return &root_;
}
private:
TrieNode root_;
};
vector<vector<string>> Group(vector<string> const &words)
{
Trie trie;
for (auto const &w : words) {
trie.Insert(w);
}
unordered_map<string, vector<int>> groups;
for (int idx = 0; idx < words.size(); ++idx) {
string const &w = words[idx];
for (int i = 0; i < w.size(); ++i) {
TrieNode *n = trie.GetRoot();
for (int j = i; j < w.size() && n; ++j) {
n = n->GetChild(w[j]);
if (n &&
n->terminal_)
{
int size = j - i + 1;
if (size < w.size()) {
groups[w.substr(i, size)].push_back(idx);
}
}
}
}
}
vector<vector<string>> out;
for (auto const &g : groups) {
if (!g.second.empty()) {
vector<string> v;
v.push_back(g.first);
for (int i : g.second) {
v.push_back(words[i]);
}
out.push_back(v);
}
}
return out;
}
Build a trie for the words. Traverse the trie and add words to each list depending on the root of the trie.
- SK May 04, 2017