Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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];
}
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;
}
}
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
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+" " );
}
}
}
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;
}
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;
}
};
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);
}
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);
}
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);
}
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
public class putSpacesInString {
static public void main(String[] args){
Set<String> dic=new HashSet<>( );
dic.add( "bed" );
dic.add( "bath" );
dic.add( "and" );
dic.add( "beyond" );
dic.add( "bend" );
Boolean re=separateStringWords( "bedbathandbeyond",dic );
System.out.println( re );
}
static Boolean separateStringWords(String s, Set<String> dict){
int sumOfChars=0;
Boolean valid=false;
for(String w:dict){
if(s.indexOf(w) > -1)
sumOfChars=sumOfChars+w.length();
if(sumOfChars == s.length()){
valid=true;
break;
}
}
return valid;
}
}
import java.util.LinkedList;
public class ContainString {
public static void main(String[] argv) {
System.out.println(checkSt());
}
public static boolean checkSt() {
String s1 = "BedBathAndBeyond";
LinkedList<String> l = new LinkedList<>();
l.add("Bed");
l.add("Bath");
l.add("And");
l.add("Beyond");
for (String s : l) {
String s2 = s1.substring(0, s.length());
if (s.compareTo(s2) != 0) {
return false;
}
s1 = s1.substring(s.length());
}
return true;
}
}
public class Dynamic {
private static Set<String> words = new HashSet<>();
private static Set<String> wordsFromString = new LinkedHashSet<>();
private static void SeparateWords(String input){
String temp = "";
int len = input.length();
for(int i = 1; i <= len; i++){
temp = input.substring(0,i);
if(words.contains(temp)){
wordsFromString.add(temp);
SeparateWords(input.substring(i, len));
}
}
public static void main(String[] args){
words.add("Bed");
words.add("Bath");
words.add("and");
words.add("Beyond");
String test = "BedBathandBeyond";
SeparateWords(test);
for(String s : wordsFromString){
System.out.print(s + " ");
}
}
}
- Anon April 29, 2017