Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

Map<String, Integer> memo = new HashMap<String, Integer>();

boolean isValidString (String s, Map<String, Integer> dictionary) {
  if (s.length == 0)
      return false;
  wordBreak(s, words);
}

boolean wordBreak(String s) {
  for (int i=1; i < s.length; i++) {
      if (memo.contains(s.substring(i+1, s.length)))
              continue;
      if (dictionary.contains(s.substring(0, i)) && wordBreak(s.substring(i+1, s.length))) {
           return true;
      }
      memo.put(s.substring(i+1, s.length), 1);
                        
   }
  return false;
}

- Anon April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 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_;
};

bool Composite(Trie &trie, vector<int> &memo, string const &s, int idx = 0)
{
	if (idx == 0) {
		memo.clear();
		memo.resize(s.size(), -1);
	}
	if (idx >= s.size()) {
		return idx != 0;
	}
	if (memo[idx] != -1) {
		return memo[idx];
	}
	bool result = false;
	TrieNode *n = trie.GetRoot();
	for (int i = idx; i < s.size() && n; ++i) {
		n = n->GetChild(s[i]);
		if (n &&
			n->terminal_ &&
			Composite(trie, memo, s, i + 1))
		{
			result = true;
			break;
		}
	}
	memo[idx] = result;
	return memo[idx];
}

- Alex May 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package Strings;

import java.util.HashSet;
import java.util.Set;

public class FindWords {

public static void main(String[] args) {
// TODO Auto-generated method stub
dictionary.add("beyond");
dictionary.add("and");
dictionary.add("bath");
dictionary.add("bed");
//dictionary.add("be");
String str = "bedbathandbeyond";
System.out.println(isValidString(str));
}
static Set<String> dictionary = new HashSet<String>();

static boolean isValidString (String s) {
if (s.length() == 0)
return false;
return wordBreak(s);
}

static boolean wordBreak(String s) {
for (int i=1; i <= s.length(); i++) {
String sub = s.substring(i, s.length());
if (dictionary.contains(s.substring(0, i)) && (sub.length()>0?wordBreak(sub):true)) {
return true;
}
}
return false;
}
}

- nvprhanumantharao May 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;

public class StringToWords {

	
	public static void main(String[] args) {
		
		String str = "bedbathandbeyond";
		String[] words = {"bed","bath", "and","beyond"};	
		
		ArrayList<String> aList = new ArrayList<String>();
		
		String temp;
		
		for(int i=0;i<str.length();i++){
			
			for(int j=i;j<str.length();j++){
				
				temp=str.substring(i, j+1);
				
				for(int k=0;k<words.length;k++){
					
					if(temp.equals(words[k])){
						
						aList.add(str.substring(i,j+1));
					}
				}
				
			}	
			
		}
		

		for(String s: aList){
			System.out.print(s+" " );
		}
			
		
	}

	
}

Output : bed bath and beyond

- Yash May 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;

public class StringSeperateToWords {

	
	public static void main(String[] args) {
		
		String str = "bedbathandbeyond";
		String[] words = {"bed","bath", "and","beyond"};	
		
		ArrayList<String> aList = new ArrayList<String>();
		
		String temp;
		
		for(int i=0;i<str.length();i++){
			
			for(int j=i;j<str.length();j++){
				
				temp=str.substring(i, j+1);
				
				for(int k=0;k<words.length;k++){
					
					if(temp.equals(words[k])){
						
						aList.add(str.substring(i,j+1));
					}
				}
				
			}	
			
		}
		

		for(String s: aList){
			System.out.print(s+" " );
		}
			
		
	}

	
}

- Yash May 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If I get this right this is an O(n*log(d)) solution, where d is the size of dictionary.

typedef std::vector<std::string> dict_t;

int lower_bound(const dict_t& d, int b, int e, int c, int p)
{
    while( b < e ){
        int m = (b+e)/2;
        if ( d[m].length() < p || d[m][p] < c )
            b = m+1;
        else
            e = m;
    }
    return b;
}
int upper_bound(const dict_t& d, int b, int e, int c, int p)
{
    while( b < e ){
        int m = (b+e)/2;
        if ( d[m].length() < p || d[m][p] <= c )
            b = m+1;
        else
            e = m;
    }
    return b;
}

std::unordered_set<int> memo;
bool word_search( const dict_t& d, const std::string& s, int w =0 )
{
    if ( memo.find(w) != memo.end() )
        return false;

    int l = s.length();
    int b = 0;
    int e = d.size();

    for ( int i = w; i < l; ++i ) {
        b = lower_bound(d, b, e, s[i], i-w);
        e = upper_bound(d, b, e, s[i], i-w);

        if ( b >= e ) {
            memo.insert(w);
            return false;
        }
        else if ( d[b].length() == i-w+1
                  && ( i+1 >= l
                       || word_search( d, s, i+1 ) ) ) {
            return true;
        }
    }
    memo.insert(w);
    return false;
}

- Vishap June 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

stuct hash_func {
  size_t operator()(const entry &a) const {
      return std::hash<char>(entry.c);
  }  
    
};
stuct equal_func {
  bool operator()(const entry &a, const entry &b) const {
      return a.c == b.c;
  }  
    
};

struct entry {
  char c;
  unordered_set<entry, hash_func, equal_func> children;
};

typedef unordered_set<entry, hash_func, equal_func>::iterator it_t;
typedef unordered_set<entry, hash_func, equal_func> mp_t;
class trie{
    unordered_set<entry, hash_func, equal_func> root;
    mp_t & find_next(mp_t &it, char a) {
        it_t ret_it;  
        if (it == mp_t()) {
            // trying new 
            ret_it = root.find(a);
        } else {
            ret_it = it.find(a);
        }
        if (ret_it == root.end()) {
            // not found then report error
            throw bad_exception("Not found");
        }
        return ret_it->second.children;
    }        
};

- ali.kheam July 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

See this -

public void findWord(String string) 
	{
		List<String> dictionary = createDictionary();
		StringBuilder words= new StringBuilder();
		StringBuilder word= new StringBuilder();
		
		char[] characters = string.toCharArray();
		for (int i = 0; i < characters.length; i++) {
			word.append(characters[i]);
			if(dictionary.contains(word.toString()))
			{
				words.append(word+" ");
				word=new StringBuilder();
			}
		}
		System.out.println("words found in dictionary>"+words);

}

- Gerrard September 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void findWord(String string) 
	{
		List<String> dictionary = createDictionary();
		StringBuilder words= new StringBuilder();
		StringBuilder word= new StringBuilder();
		
		char[] characters = string.toCharArray();
		for (int i = 0; i < characters.length; i++) {
			word.append(characters[i]);
			if(dictionary.contains(word.toString()))
			{
				words.append(word+" ");
				word=new StringBuilder();
			}
		}
		System.out.println("words found in dictionary>"+words);
	}

- Gerrard September 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void findWord(String string) 
	{
		List<String> dictionary = createDictionary();
		StringBuilder words= new StringBuilder();
		StringBuilder word= new StringBuilder();
		
		char[] characters = string.toCharArray();
		for (int i = 0; i < characters.length; i++) {
			word.append(characters[i]);
			if(dictionary.contains(word.toString()))
			{
				words.append(word+" ");
				word=new StringBuilder();
			}
		}
		System.out.println("words found in dictionary>"+words);
	}

- Gerrard September 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Code. Works for below input :
s = "bedbathandbeyond"
list1 = ['bed','bath','and','beyond']
Output = true

s = "bedbathandbeyond"
list1 = ['and','bath','and','beyond']
Output = false

s = "bedbathandbeyond"
list1 = ['beyond','bath','and','bed']
Output = False

def check(s,dict1):
	len1 = len(s)
	len2 = len(list1)

	if len1 == 0 or len2 == 0:
		return False
	sum1 = 0
	for items in list1:
		sum1 = sum1 + len(items)

	if sum1 != len1:
		return False

	s1 = s

	for items in list1:
		#print "1st step"
		#print items,s1
		s2,flag = subs(items,s1)
		#print "2nd step"
		print items, flag, s2
		s1 = s2

		if flag == False:
			return False

	if len(s2) == 0:
		return True


def subs(items,s1):
	len1 = len(items)
	len2 = len(s1)
	print items, s1
	for i in range(0,len2):
		if s1[i] == items[0]:
			if i+len1 <= len2:
				temp = ''
				for j in range (i,i+len1):
					temp = temp + s1[j]
				if temp == items:
					s2 = ''
					#print i+len1, len2
					if i != 0:
						for l in range (0,i):
							s2 = s2+s1[l]
					for k in range (i+len1, len2):
						#print s2, s1[k]
						s2 = s2+s1[k]
					return s2, True
					

	return s1,False


flag = check (s,list1)

print flag

- koolkhush February 09, 2018 | 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