Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

JavaScript implementation. Add method is iterative, O(L) time and search is recursive, exponential time.

class TrieNode {
  constructor(){
    this.isWord = false;
    this.children = new Array(26);
  }
}

class Trie {
  constructor(){
    this.root = new TrieNode();
    this.baseCharCode = 'a'.charCodeAt(0);
  }

  add(word){
    let node = this.root;
    for (let c of word){
      const index = c.charCodeAt(0) - this.baseCharCode;
      if (!node.children[index]){
        node.children[index] = new TrieNode();
      }
      node = node.children[index];
    }
    node.isWord = true;
  }

  search(pattern){
    return this.recursiveSearch(this.root, pattern, 0);
  }

  recursiveSearch(node, pattern, i){
    if (!node){
      return false;
    }
    if (i === pattern.length){
      return node.isWord;
    }
    const c = pattern.charAt(i);
    if (c === '*'){
      for (let child of node.children){
        if (this.recursiveSearch(child, pattern, i + 1)){
          return true;
        }
      }
      return false;
    }
    const childIndex = c.charCodeAt(0) - this.baseCharCode;
    const child = node.children[childIndex];
    return this.recursiveSearch(child, pattern, i + 1);
  }
}

const trie = new Trie();
trie.add('cat');
trie.add('mat');
trie.add('dog');
trie.add('catwoman');
trie.add('do');
trie.add('category');
trie.add('cut');

console.log(trie);

// it's a word
console.log('cat', trie.search('cat'));

// it's a node but not a word
console.log('ca', trie.search('ca'));

console.log('category', trie.search('category'));

console.log('done', trie.search('done'));

// matches 'cat' and 'cut'
console.log('c*t', trie.search('c*t'));

// matches 'catwoman'
console.log('********', trie.search('********'));

- Anonymous November 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Posting simple trie solution:
+ Replace '*' with all possible valid characters in trie.

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

const int TOTAL_LENGTH = 26;
class trieNode
{
public:
	bool isKey;
	vector<trieNode*> children;
	trieNode():isKey(false), children( vector<trieNode*>( TOTAL_LENGTH, nullptr))
	{}
};

class wordDict
{
private:
	trieNode* root;
	
	bool findWordHelper( trieNode* curr, const string& word )
	{
		if( word.size() == 0 ) return false;
		
		for( size_t i=0; i<word.size();  ++i)
		{
			// either a regualer character
			if( curr && word[i] != '*')
			{
				curr = curr->children[ word[i]-'a'];
			}
			else if( curr && word[i] == '*')
			{				
				// Go over all the characters
				for( int j=0; j< TOTAL_LENGTH; ++j)
				{
					if( curr->children[j] != NULL &&
					    findWordHelper( curr->children[j], word.substr(i)) )
					{
						return true;
					}
				}
			}
			else
			{
				break;
			}
		}
		return curr && curr->isKey;
	}
	
public:
	wordDict(): root( new trieNode() )
	{}
	
	void addWord( const string& word )
	{
		if( word.size() == 0) return;
		
		trieNode* curr = root;
		for( size_t i=0; i< word.size(); ++i )
		{
			if( curr->children[ word[i]-'a'] == NULL)
			{
				curr->children[ word[i]-'a'] = new trieNode();
			}
			curr = curr->children[ word[i]-'a'];
		}
		
		//after loop set the flag to indicate valid word
		
		curr->isKey = true;
	}
	
	// Word could contain a '*' charactrer to map to any charcter 
	bool findWord( const string& word )
	{
		return findWordHelper( root, word );
	}
	
	
};

int main()
{
	
	wordDict dict;
	
	dict.addWord("hello");
	dict.addWord("one");
	dict.addWord("two");

	cout << dict.findWord("one") << endl;
	cout << dict.findWord("two") << endl;
 	cout << dict.findWord("****e") << endl;

	return 0;
}

- mr.robot.fun.society November 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node(object):
  def __init__(self):
    self.children = {}

class Trie(object):
  def __init__(self):
    self.sentinel = Node()

  def add_word(self, word):
    curr_node = self.sentinel
    for c in word:
      if c in curr_node.children:
        curr_node = curr_node.children[c]
      else:
        new_node = Node()
        curr_node.children[c] = new_node
        curr_node = new_node

  def _search(self, tokens, i, curr_node):
    # Base case: No tokens, default True
    if i == len(tokens):
      return True

    # Wildcard
    if tokens[i][-1] == '*':
      # Wildcard matches with nothing
      if self._search(tokens, i + 1, curr_node):
        return True

      # '.*' encountered
      if tokens[i][0] == '.':
        # Return False if we need to match with something
        # but there's nothing left in the string.
        # 
        # Otherwise, recurse with the same token
        # and the next character in the string.
        return (len(curr_node.children) != 0
                and any(self._search(tokens, i, child)
                        for child in curr_node.children.values()))
      # 'w*' encountered, where w is any non-. character
      else:
        # Return False if we need to match with something
        # but there's nothing left in the string.
        # 
        # Otherwise, recurse with the same token
        # and the next character in the string.
        return (tokens[i][0] in curr_node.children
                and self._search(tokens, i, curr_node.children[tokens[i][0]]))
    # Single character match
    else:
      if tokens[i] == '.':
        # Return False if we need to match with something
        # but there's nothing left in the string.
        # 
        # Otherwise, recurse with the next token
        # and the next character in the string.
        return (len(curr_node.children) != 0
                and any(self._search(tokens, i, child)
                        for child in curr_node.children.values()))
      else:
        # Return False if we need to match with something
        # but there's nothing left in the string.
        # 
        # Otherwise, recurse with the next token
        # and the next character in the string.
        return (tokens[i] in curr_node.children
          and self._search(tokens, i + 1, curr_node.children[tokens[i]]))


  def search(self, regex):
    # Assuming valid regex, tokenize
    tokens = []
    n = len(regex)
    i = 0
    while i < n:
      if i == n - 1 or regex[i + 1] != '*':
        tokens.append(regex[i])
        i += 1
      else:
        tokens.append(regex[i : i + 2])
        i += 2
    return self._search(tokens, 0, self.sentinel)

t = Trie()
t.add_word('mad')
t.add_word('bag')
t.add_word('fad')
t.search('.*d')

- vlchen91 November 13, 2017 | Flag Reply


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