Facebook Interview Question


Country: United States




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

Its not clear from your examples and description what is the real problem. How is the answer to your first example Yes, it should be No since you can't words "ab":2. Something is missing here or I am not following your question/description.

- Mukul July 20, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I solved this problem in varies ways [ we can also use trie to solve this ]

public class BuildStringWordsInDictionary {

    public static void main(String args[]) {
        test1();
        test2();
        test3();
        test4();
        test5();


    }

    //false
    private static void test5() {
        String s = "abcabab";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 1);


        System.out.println("\nGiven String : " + s + " Expected output :" + false);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));

    }

    //true
    private static void test4() {
        String s = "abcabab";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 2);

        System.out.println("\nGiven String : " + s + " Expected output :" + true);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
    }

    //false
    private static void test3() {
        String s = "abcx";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 2);
        wordCount.put("abca", 1);

        System.out.println("\nGiven String : " + s + " Expected output :" + false);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
    }

    //true
    private static void test1() {

        String s = "abcabcabcabca";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 2);
        wordCount.put("abca", 1);

        System.out.println("\nGiven String : " + s + " Expected output :" + true);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
    }


    //true
    private static void test2() {

        String s = "abcabcaabbc";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 1);
        wordCount.put("abca", 1);

        System.out.println("\nGiven String : " + s + " Expected output :" + true);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));


    }


}


/**
 * NOTE: Not working
 */
class SolutionBFSByStringWords {


    public static boolean canBreak(String str, Map<String, Integer> wordCount) {

        if (str.isEmpty())
            return true;

        return canBreakBFS(str, wordCount);


    }

    private static boolean canBreakBFS(String str, Map<String, Integer> wordCount) {

        int n = str.length();
        final Queue<Integer> queue = new LinkedList<>();

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

        queue.offer(0);

        while (!queue.isEmpty()) {

            int start = queue.poll();

            for (int i = start ; i < str.length(); i++) {

                //Try this word : forward ->
                String temp = str.substring(start, i + 1);

                if (!visited.containsKey(temp))
                    visited.put(temp, 0);

                //Check is this possible ?
                if (wordCount.containsKey(temp) && wordCount.get(temp) > visited.get(temp)) {

                    visited.put(temp, visited.get(temp) + 1);

                    //if possible,the remove this string and recurse for rest of the string;
                    wordCount.put(temp, wordCount.get(temp) - 1);

                    //recurse for rest of the string;
                    queue.offer(i);

                    if (i == str.length())
                        return true;


                }
            }

        }


        return false;
    }
}

/**
 * This solution won't handle the cases when you can remove the word in-between and form a new workd by ends
 * Example:
 * s = "abcabcaabbc";
 * {"abc": 3, "ab": 1, "abca": 1}
 * <p>
 * Your code produce False where it is possible ;
 * abcabcaabbc -> aabbc [remove two "abc"] {"abc": 1, "ab": 1, "abca": 1}
 * aabbc -> abc [remove one "ab" ] {"abc": 1, "ab": 0, "abca": 1} [**** This is not supported ***]
 * abc -> "" [ remove one "abc" ] {"abc": 0, "ab": 1, "abca": 1}
 */
class SolutionDFSByStringWords {


    /**
     * DFS 1:
     * By keeping the index of recursion
     *
     * @param str
     * @param wordCount
     * @return
     */
    public static boolean canBreak(String str, Map<String, Integer> wordCount) {

        if (str.isEmpty())
            return true;

        return canBreakRec(str, wordCount, 0);


    }

    /**
     * Keep taking a sub-string from given string specified by "start" index and keep checking does this is possible break
     * which leads to a solution
     *
     * @param str
     * @param wordCount
     * @param start
     * @return
     */
    private static boolean canBreakRec(String str, Map<String, Integer> wordCount, int start) {

        //If we have remove all the chars, then success
        if (start == str.length())
            return true;

        for (int i = start; i < str.length(); i++) {

            //Try this word : forward ->
            String temp = str.substring(start, i + 1);

            //Check is this possible ?
            if (wordCount.getOrDefault(temp, -1) > 0) {

                //if possible,the remove this string and recurse for rest of the string;
                wordCount.put(temp, wordCount.get(temp) - 1);

                //recurse for rest of the string;
                if (canBreakRec(str, wordCount, i + 1)) {
                    return true;
                }
                //Couldn't find the solution, backtrack
                wordCount.put(temp, wordCount.get(temp) + 1);

            }


        }

        return false;
    }


    /**
     * DFS 2
     * By breaking string into sub-strings
     *
     * @param word
     * @param map
     * @return
     */

    public static boolean wordBreak(String word, Map<String, Integer> map) {
        int len = word.length();
        if (len <= 0) return true;
        for (int i = 1; i < len + 1; i++) {
            String a = word.substring(0, i);
            Integer I = map.get(a);
            if (I == null || I <= 0)
                continue;

            map.put(a, I - 1);

            if (i <= len && wordBreak(word.substring(i, len), map))
                return true;

            map.put(a, I);
        }
        return false;
    }
}


class SolutionDFSByMapWords {


    public static boolean canBreak(String str, Map<String, Integer> wordCount) {

        if (str.isEmpty())
            return true;

        return canBreakRec(str, wordCount);


    }

    /**
     * DFS the tree.
     * check using current count in map of a word, does string can be broken ?
     * if yes, then decrease the number of counts and recurse for further. Try all
     *
     * @param str
     * @param wordCount
     * @return
     */
    private static boolean canBreakRec(String str, Map<String, Integer> wordCount) {
        if (str.isEmpty())
            return true;

        /**
         * find all the keys present in str and remove them as many times as said
         */
        for (String key : wordCount.keySet()) {


            int count = wordCount.get(key);

            //Can we still use this word from dict?
            if (count > 0) {

                int oldCount = count;

                String oldString = str;

                //Find and remove the occurrence
                while (str.contains(key) && count > 0) {
                    str = str.replaceFirst(key, "");
                    count--;
                }

                //if we tried to remove but no occurrence found for given key in string, then continue to next word in map
                if (count == wordCount.get(key))
                    continue;
                else {

                    //decrease the count of occurrence
                    wordCount.put(key, count);

                    //Recurse
                    if (canBreakRec(str, wordCount)) {
                        return true;
                    }

                    //Put back: Backtrack
                    str = oldString;
                    wordCount.put(key, oldCount);

                }


            }

        }
        return false;
    }

}

- nitinguptaiit July 18, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test and show how is this working

- Anonymous July 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

asdf

- Anonymous July 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Your second example is incorrect (abcabab : ['abc', 'ab', 'ab']). You did
not mention that not all words/occurencies need to be exhausted.

def SplitSubstring(s, n, word_fr, curr_split):
    if n == len(s):
        print("%s : %s" % (s, curr_split))
        return
    for i in range(n, len(s)):
        ss = s[n:i+1] 
        if ss in word_fr and word_fr[ss] > 0:
            word_fr[ss] -= 1
            curr_split.append(ss)
            SplitSubstring(s, i + 1, word_fr, curr_split)
            curr_split.pop()
            word_fr[ss] += 1
    
word_fr = {"abc":3, "ab":2, "abca":1}
SplitSubstring("abcabcabcabca", 0, word_fr, [])
SplitSubstring("abcx", 0, word_fr, [])

word_fr =  {"abc":3, "ab":2}
SplitSubstring("abcabab", 0, word_fr, [])

- hb July 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class BreakWord{
    static boolean ans = false;
    public static void main(String[] args){
        Map<String, Integer> map = new HashMap<>();
        //map.put("abc", 3);
        //map.put("ab", 2);
        //map.put("abca", 1);
        map.put("abc", 3);
        map.put("ab", 2);
        String str = "abcabcabcabca";
        //String str = "abcabab";

        Set<String> set = new HashSet<>();
        for(String s : map.keySet()){
            set.add(s);
        }

        dfs(map, set, str, 0);
        System.out.println(ans);
    }

    public static void  dfs(Map<String, Integer> map, Set<String> set, String str, int start){
        if(start == str.length()){
            ans = true;
            return;
        }
        for(int i=start; i<str.length(); i++){
            String ss = str.substring(start, i+1);
            if(!set.contains(ss))
                continue;
            if(map.get(ss) == 0){
                continue;
            }
            map.put(ss, map.get(ss)-1);
            dfs(map, set, str, i+1);
            map.put(ss, map.get(ss)+1);
        }
    }
}

- xzhan211@binghamton.edu July 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Given { "abc": 3, "ab": 2, "abca": 1 }
// abcabcabcabca => [abc, abc, abc, abca]
// abcabab => [abc, ab, ab]
// abcx => []


function findLongestPrefix(str, index, dict, maxPrefixLen) {
  
  var dictCopy = Object.assign({}, dict);
  
  if (index >= str.length)
    return [];
  
  for (var i = maxPrefixLen; i > 0; i--) {
    var candidate = str.substr(index, i);
    
    if (dictCopy[candidate]) {
      dictCopy[candidate]--;
      
      try {
        var rest = findLongestPrefix(str, index + candidate.length, dictCopy, maxPrefixLen);
        return [candidate].concat(rest);
      } catch(err) {
        dictCopy[candidate]++;
      }
    }
  }

  throw error('E_INVALID_CHARS')
  
}

function breakWords(str, dict) {
  // Get the max lengths of keys
  var keys = Object.keys(dict);
  var maxPrefixLen = 1;
  for (var i = 0; i < keys.length; i++ ) {
    if (keys[i].length > maxPrefixLen) {
      maxPrefixLen = keys[i].length;
    }
  }
  
  try {
    return findLongestPrefix(str, 0, dict, maxPrefixLen)
  } catch(error) {
    return []
  }
}

var words = breakWords("abcabcabcabca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)


words = breakWords("abcabab", { "abc": 3, "ab": 2 })
console.log( words)

words = breakWords("abcx", { "abc": 3, "ab": 2, "abca": 1 })
console.log( words)

words = breakWords("abca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)

- Anonymous August 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Given { "abc": 3, "ab": 2, "abca": 1 }
// abcabcabcabca => [abc, abc, abc, abca]
// abcabab => [abc, ab, ab]
// abcx => []


function findLongestPrefix(str, index, dict, maxPrefixLen) {
  
  var dictCopy = Object.assign({}, dict);
  
  if (index >= str.length)
    return [];
  
  for (var i = maxPrefixLen; i > 0; i--) {
    var candidate = str.substr(index, i);
    
    if (dictCopy[candidate]) {
      dictCopy[candidate]--;
      
      try {
        var rest = findLongestPrefix(str, index + candidate.length, dictCopy, maxPrefixLen);
        return [candidate].concat(rest);
      } catch(err) {
        dictCopy[candidate]++;
      }
    }
  }

  throw error('E_INVALID_CHARS')
  
}

function breakWords(str, dict) {
  // Get the max lengths of keys
  var keys = Object.keys(dict);
  var maxPrefixLen = 1;
  for (var i = 0; i < keys.length; i++ ) {
    if (keys[i].length > maxPrefixLen) {
      maxPrefixLen = keys[i].length;
    }
  }
  
  try {
    return findLongestPrefix(str, 0, dict, maxPrefixLen)
  } catch(error) {
    return []
  }
}

var words = breakWords("abcabcabcabca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)


words = breakWords("abcabab", { "abc": 3, "ab": 2 })
console.log( words)

words = breakWords("abcx", { "abc": 3, "ab": 2, "abca": 1 })
console.log( words)

words = breakWords("abca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)

- my thought August 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Given { "abc": 3, "ab": 2, "abca": 1 }
// abcabcabcabca => [abc, abc, abc, abca]
// abcabab => [abc, ab, ab]
// abcx => []


function findLongestPrefix(str, index, dict, maxPrefixLen) {
  
  var dictCopy = Object.assign({}, dict);
  
  if (index >= str.length)
    return [];
  
  for (var i = maxPrefixLen; i > 0; i--) {
    var candidate = str.substr(index, i);
    
    if (dictCopy[candidate]) {
      dictCopy[candidate]--;
      
      try {
        var rest = findLongestPrefix(str, index + candidate.length, dictCopy, maxPrefixLen);
        return [candidate].concat(rest);
      } catch(err) {
        dictCopy[candidate]++;
      }
    }
  }

  throw error('E_INVALID_CHARS')
  
}

function breakWords(str, dict) {
  // Get the max lengths of keys
  var keys = Object.keys(dict);
  var maxPrefixLen = 1;
  for (var i = 0; i < keys.length; i++ ) {
    if (keys[i].length > maxPrefixLen) {
      maxPrefixLen = keys[i].length;
    }
  }
  
  try {
    return findLongestPrefix(str, 0, dict, maxPrefixLen)
  } catch(error) {
    return []
  }
}

var words = breakWords("abcabcabcabca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)


words = breakWords("abcabab", { "abc": 3, "ab": 2 })
console.log( words)

words = breakWords("abcx", { "abc": 3, "ab": 2, "abca": 1 })
console.log( words)

words = breakWords("abca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)

- sheng August 21, 2019 | 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