## Facebook Interview Question for SDE1s

Country: United States

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

Here is how we will go

``````public class Node
{
public char label;
public List<Node> neighbors;
public Node(char x)
{
label = x;
neighbors = new List<Node>();
}
}

public class Solution
{
// we are assuming that the whole graph is given to us in list of nodes, not just the root nodes.
public boolean Exists(List<Node> nodes, string word)
{
if(String.IsNullOrWhiteSpace(word))
{
return false;
}
bool found = false;
foreach(Node node in nodes)
{
if(node.label == word[0] && IsExistsReuseLabel(node, word))
{
return true;
}
}
return false;
}
/// Lets assume we can use same label more then once.
private boolean IsExistsReuseLabel(Node node, string word)
{
if(String.IsNullOrWhiteSpace(word))
{
return true;
}
if(node.label == word[0])
{
string remainingWord = word.Remove(0,1);
foreach(Node neighbor in node.neighbors)
{

if(IsExists(neighbor, remainingWord))
{
return true;
break;
}
}
}
return false;
}
/// Lets assume, we can't use same label more then once.
private boolean IsExistsNoReuseLabel(Node node, string word)
{
Dictionary<Node, bool> usedNodeMap = new Dictionary<Node, bool>();
return IsExistsDFS(Node node, word, usedNodeMap);
}

private boolean IsExistsDFS(Node node, string word, Dictionary<Node, bool> usedNodeMap)
{
if(!usedNodeMap.ContainsKey(node))
{
}
else if(usedNodeMap.ContainsKey(node) && !usedNodeMap[node])
{
usedNodeMap[node] = true;
}
else
{
return false;
}
string remainingWord = word.Remove(0,1);
if(remainingWord.Length > 0)
{
foreach(Node neighbor in node.neighbors)
{
if(neighbor.label == remainingWord[0] && IsExistsDFS(neighbor, remainingWord, usedNodeMap))
{
return true;
}
}
}
else
{
return true;
}
usedNodeMap[node] = false;
return false;
}
}``````

Complexity
Time: 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.

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

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

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

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

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

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

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

``````class Node {
public:
Node(char val)
{
val_ = val;
}
{
}
char val_;
};

class Graph {
public:
{
}
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:
{
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()) {
for (int j : n->adjacent_nodes_) {
if (adjacent_node->val_ == word[i + 1]) {
break;
}
}
break;
}
}
}
return i == word.size() &&
!word.empty();
}``````

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.

### 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.