Facebook Interview Question
SDE1sCountry: United States
public boolean exist(List<Node> nodes, String word) {
return exist(nodes, word, 0);
}
public boolean exist(List<Node> nodes, String word, int index) {
if (index >= word.length()) {
return true;
}
for (Node node : nodes) {
if (node.label == word.charAt(index)) {
if (exist(node.neighbors, word, index + 1)) {
return true;
}
}
}
return false;
}
public boolean exist(List<Node> nodes, String word) {
return exist(nodes, word, 0);
}
public boolean exist(List<Node> nodes, String word, int index) {
if (index >= word.length()) {
return true;
}
for (Node node : nodes) {
if (node.label == word.charAt(index)) {
if (exist(node.neighbors, word, index + 1)) {
return true;
}
}
}
return false;
}
public boolean exist(List<Node> nodes, String word) {
return exist(nodes, word, 0);
}
public boolean exist(List<Node> nodes, String word, int index) {
if (index >= word.length()) {
return true;
}
for (Node node : nodes) {
if (node.label == word.charAt(index)) {
if (exist(node.neighbors, word, index + 1)) {
return true;
}
}
}
return false;
}
class Node {
public:
Node(char val)
{
val_ = val;
}
void AddAdjacentNode(int n)
{
adjacent_nodes_.push_back(n);
}
char val_;
vector<int> adjacent_nodes_;
};
class Graph {
public:
void AddLink(char val1, char val2)
{
int n1 = AddNode(val1);
int n2 = AddNode(val2);
nodes_[n1].AddAdjacentNode(n2);
nodes_[n2].AddAdjacentNode(n1);
}
Node const *GetNode(char val) const
{
auto it = val_to_node_.find(val);
if (it != val_to_node_.end()) {
return &nodes_[it->second];
}
return NULL;
}
Node const *GetNode(int idx) const
{
return idx > 0 && idx < nodes_.size() ? &nodes_[idx] : NULL;
}
private:
int AddNode(char val)
{
auto it = val_to_node_.find(val);
if (it != val_to_node_.end()) {
return it->second;
}
nodes_.push_back(Node(val));
int node_idx = nodes_.size() - 1;
return val_to_node_[val] = node_idx;
}
vector<Node> nodes_;
unordered_map<char, int> val_to_node_;
};
bool WordMatchesPath(Graph const &g, string const &word)
{
int i = 0;
for (; i < word.size(); ++i) {
Node const *n = g.GetNode(word[i]);
if (!n) {
break;
}
if (i + 1 < word.size()) {
bool link_found = false;
for (int j : n->adjacent_nodes_) {
Node const *adjacent_node = g.GetNode(j);
if (adjacent_node->val_ == word[i + 1]) {
link_found = true;
break;
}
}
if (!link_found) {
break;
}
}
}
return i == word.size() &&
!word.empty();
}
Here is how we will go
Complexity
- sonesh May 01, 2017Time: O(N + V), where N is number of nodes in the tree and V is number of edges in the graph.
Space: O(N) for nonreuse method, O(1) for resume method.