## Facebook Interview Question for SDE1s

Country: United States

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

Build a trie for the words. Traverse the trie and add words to each list depending on the root of the trie.

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

rsrs3

for {"an","dan", "c"}, your codes return [[an], [c], [dan]]
but it should be [[c], [an, dan]]

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

Can anyone provide the answer for below test case?

[c ca can ba ban b bb 12mn 12mnc]

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

Can anyone provide the correct answer for below test case:

[c ca can ba ban b bb 12mn 12mnc]

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

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

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

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``````

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

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

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