Facebook Interview Question


Country: United States




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

Time complexity O(n);
Space complexity O(n);
Solution using Trie data structure:

import java.util.*;

class Main {
    public static void main(String[] args) {
        TrieNode root = new TrieNode('*');
        String[] dictionary = {"i","like","face","book","facebook"} ;
        String input = "ilikefacebook";
        for(String s:dictionary){
            root.addString(s);
        }

        findans(root,input);

    }
    public static void findans(TrieNode root,String inp){
        int counter=0;
        TrieNode itr = root;
        int i=0;
        while(i<inp.length()-1){
            if((itr.children).get(inp.charAt(i))!=null){
                itr=(itr.children).get(inp.charAt(i));
                i++;
            }else{
                counter++;
                itr=root;
            }
        }
        System.out.println("ans:"+counter);

    }
}


class TrieNode {
    HashMap<Character,TrieNode> children = new HashMap<>();
    Character c;
    boolean terminates;

    public TrieNode(Character cc){
        c=cc;
    }

    public void addString(String s){
        if(s==null || s.length()==0)return;
        Character nextchar = s.charAt(0);
        if(children.get(nextchar)==null){
            TrieNode n = new TrieNode(nextchar);
            children.put(nextchar,n);
        }
        (children.get(nextchar)).addString(s.substring(1));
    }

}

Output:

ans:2

- krupen.ghetiya July 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SplitStringInMinSpace {

public static void main(String[] args) {
String str = "ilikefacebook";
String[] words = { "i", "like", "face", "book", "facebook" };
System.out
.println(splitString(new HashSet<>(Arrays.asList(words)), str));
}

public static String splitString(HashSet<String> words, String inputString) {
StringBuffer result = new StringBuffer();
if (inputString == null || inputString.trim().length() == 0) {
return result.toString();
}

int inputLength = inputString.length();
for (int i = 1; i <= inputLength; i++) {

if (words.contains(inputString.substring(0, i))){
result.append(inputString.substring(0, i));
result.append(" ");
}
for (int j = i + 1; j <= inputLength; j++) {
if (words.contains(inputString.substring(i, j))){
result.append(inputString.substring(i, j));
i=j;
result.append(" ");
}
}
}
return result.toString();
}
}

- Anonymous July 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When I run this I get "i like face book"

- kredible July 15, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the first iteration.

I store the dictionary as a hash set for faster lookup and use recursion to find all possible words.

public class WordBreakByDictionary {
    public static void main(String[] args) {
        Set<String> dictionary = new HashSet<>(Arrays.asList("i", "like", "face", "book", "facebook"));
        System.out.println(findMinimumWordCount("ilikefacebook", dictionary));
    }

    private static int findMinimumWordCount(String input, Set<String> dictionary) {
        if (input.length() == 0)
            return 0;

        int min = Integer.MAX_VALUE;
        for(int i=1; i <= input.length(); i++) {
            if (dictionary.contains(input.substring(0, i))) {
                int subCount = findMinimumWordCount(input.substring(i), dictionary);
                if (min > subCount+1) {
                    min = subCount + 1;
                }
            }
        }
        return min;
    }
}

- kredible July 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My second attempt. This time, I managed to get O(N) time using O(logN) space by using a *Trie* data structure.

*Step 1: Build the Trie*
This is a custom Trie implementation which also keeps track of the number of potential words starting at the given character.
For example, if the dictionary has both "face" and "facebook". The node representing "f" has a word count of 2. Actually, even nodes "a", "c" and "e" have the same word count of 2. Nodes "b", "o", "o", "k" have word count of 1.

*Step 2: Find the combination of the longest possible words*
Starting at the beginning of the input, find the longest possible word that starts here. Then jump that many characters and look for the longest possible word at the next point, etc.

*Step 3: Join the words found into a sentence*
Simply join the words found to form a sentence with spaces

public class WordBreakByDictionary {
    public static void main(String[] args) {
        Trie trie = buildTrie(new String[] { "i", "like", "face", "book", "facebook" });
        System.out.println(findMinimumSentence("ilikefacebook", trie));
    }

    private static Trie buildTrie(String[] dictionary) {
        Trie root = new Trie();
        for(String word : dictionary) {
            Trie parent = root;
            for(int i=0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                Trie curr = parent.children[index];
                if (curr == null)
                    parent.children[index] = curr = new Trie();
                curr.wordCount++;
                if (i == word.length()-1)
                    curr.isWord = true;
                parent = curr;
            }
        }
        return root;
    }

    private static String findMinimumSentence(String input, Trie trie) {
        int index = 0;
        List<String> words = new ArrayList<>();
        while(index < input.length()) {
            String nextWord = findLongestWord(input.substring(index), trie);
            if (nextWord.length() > 0) {
                words.add(nextWord);
                index += nextWord.length();
            } else {
                return null;
            }
        }
        return String.join(" ", words);
    }

    private static String findLongestWord(String input, Trie trie) {
        Trie parent = trie;
        String longestSoFar = "";
        for(int i=0; i < input.length(); i++) {
            int index = input.charAt(i) - 'a';
            Trie curr = parent.children[index];
            if (curr == null)
                return longestSoFar;

            if (curr.isWord) {
                longestSoFar = input.substring(0, i + 1);
                if (curr.wordCount == 1)
                    return longestSoFar;
            }
            parent = curr;
        }
        return longestSoFar;
    }

    private static class Trie {
        Trie[] children = new Trie[26];
        boolean isWord;
        int wordCount;
    }
}

- kredible July 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I do not think it works. Let us cook up the dictionary to be 'i', 'like', 'face', 'ac', 'e', 'if', 'book', 'facebook', 'ok'. Search for minimum spacing sentence from the string ifacelikebook. The answer is going to if ac e like book. It should be I face like book. Looking for the longest word is not the right strategy. In some cases, short beginnings may lead to the right answer. The first version is correct, I think.

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

Here's a trivial solution. It's a simple solution, but the runtime performance is poor O(n2). There must be better ways of doing this.

/**
* Created by nishkumar on 7/24/17.
*/
public class FaceBook {

public static void main(String[] args) {

String input = "IloveFacebook";

HashSet<String> dict = new HashSet<String>();
dict.add("i");
dict.add("love");
dict.add("face");
dict.add("book");
dict.add("facebook");
dict.add("colors");

int left = 0;
int right = input.length();
int count = -1;

boolean[] status = new boolean[input.length()];

while (left < right) {
for (int i = 0; i <= right; i++) {
String word = input.substring(i, right);
word = word.toLowerCase();
if (dict.contains(word)) {
count++;
right = i;
System.out.println(" -> " + word);
}
}

}
System.out.println(" Space count " + count);
}

}

- Nish July 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Trivial solution.
Performance: O(n2)

/**
 * Created by nishkumar on 7/24/17.
 */
public class FaceBook {

    public static void main(String[] args) {

        String input = "IloveFacebook";

        HashSet<String> dict = new HashSet<String>();
        dict.add("i");
        dict.add("love");
        dict.add("face");
        dict.add("book");
        dict.add("facebook");
        dict.add("colors");

        int left = 0;
        int right = input.length();
        int count = -1;

        boolean[] status = new boolean[input.length()];

        while (left < right) {
            for (int i = 0; i <= right; i++) {
                String word = input.substring(i, right);
                word = word.toLowerCase();
                if (dict.contains(word)) {
                    count++;
                    right = i;
                    System.out.println(" -> " + word);
                }
            }

        }
        System.out.println(" Space count " + count);
    }

}

- Nish July 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Its a variation of word break problem. Solve it via DP. Time complexity: O(n^3)
spaces[i] : minimum spaces achieved for string ending at i. Then,

spaces[i] 	= 0 if string from 0 to i is a valid dictionary word
		= min(spaces[k] + 1) for k from 0 to i-1 and string from k+1 to i is a valid dict word

Based on the min k you can set the parent location to find the best break point in the string.

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

public static void main(String[] args) {
        String str = "ilikefacebook";
        String[] words = { "i", "like", "face", "book", "facebook" };
        List<String> stringList = Arrays.asList(words);
        List<String> minimumWords = new ArrayList<String>();
        split(stringList, str, minimumWords);
        System.out.println(minimumWords);
    }

    public static void split(List<String> dictionary, String inputString, List<String> minimumWords){
        for(int i=0; i<dictionary.size(); i++){
            String word = dictionary.get(i);
            List<String> wordsContaining = getWordsContaining(word, dictionary);
            String longestWord = null;
            for (int j=0;j<wordsContaining.size();j++){
                String temp = wordsContaining.get(j);
                if(inputString.startsWith(temp)){
                    if(longestWord ==null||longestWord.length()<temp.length()){
                        longestWord = temp;
                    }
                }
            }
            if(longestWord!=null) {
                String newInputString = inputString.substring(longestWord.length(), inputString.length());
                minimumWords.add(longestWord);
                if(newInputString.isEmpty()){
                    return;
                }
                else {
                    List<String> copyDictionary = new ArrayList<String>(dictionary);
                    copyDictionary.remove(longestWord);
                    split(copyDictionary, newInputString, minimumWords);
                }
            }
        }

    }

    public static List<String> getWordsContaining(String word, List<String>  dictionary){
        List<String> list= new ArrayList<String>();
        for(int i =0; i<dictionary.size(); i++){
            String w = dictionary.get(i);
            if(w.startsWith(word)){
                list.add(w);
            }
        }
        return list;

}

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

public static void main(String[] args) {
String str = "ilikefacebook";
String[] words = { "i", "like", "face", "book", "facebook" };
List<String> stringList = Arrays.asList(words);
List<String> minimumWords = new ArrayList<String>();
split(stringList, str, minimumWords);
System.out.println(minimumWords);
}

public static void split(List<String> dictionary, String inputString, List<String> minimumWords){
for(int i=0; i<dictionary.size(); i++){
String word = dictionary.get(i);
List<String> wordsContaining = getWordsContaining(word, dictionary);
String longestWord = null;
for (int j=0;j<wordsContaining.size();j++){
String temp = wordsContaining.get(j);
if(inputString.startsWith(temp)){
if(longestWord ==null||longestWord.length()<temp.length()){
longestWord = temp;
}
}
}
if(longestWord!=null) {
String newInputString = inputString.substring(longestWord.length(), inputString.length());
minimumWords.add(longestWord);
if(newInputString.isEmpty()){
return;
}
else {
List<String> copyDictionary = new ArrayList<String>(dictionary);
copyDictionary.remove(longestWord);
split(copyDictionary, newInputString, minimumWords);
}
}
}

}

public static List<String> getWordsContaining(String word, List<String> dictionary){
List<String> list= new ArrayList<String>();
for(int i =0; i<dictionary.size(); i++){
String w = dictionary.get(i);
if(w.startsWith(word)){
list.add(w);
}
}
return list;
}

- Jose Luis Larraz August 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class BreakSentence {
  
        public static void main(String[] args) {
                String in = "ilikefacebook";
                String[] dict = {"i","like","face","book","facebook"};

                System.out.println(process(dict,in,0));
        }

        private static String process(String[] dict, String in, int start) {

                if(start > in.length()-1) return null;

                for(int i=dict.length-1; i> -1; i--)
                        if(in.indexOf(dict[i],start)==start) {
                                String out = process(dict,in,start+dict[i].length());
                                return out != null ? dict[i]+ " " + out: dict[i];

                        }
                return "word not found";
        }
}

- thatfernando@yahoo.com November 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function getValidWord($string) {
	$map = ["i","like","face","book","facebook"] ;
	if(in_array($string,$map)) {
		return [$string,NULL];
	}
	$len = strlen($string)-1;
	$residualString = '';

	while($len) {
		
		$residualString = $string[$len].$residualString;
		if(in_array(substr($string,0,$len),$map)) {
			return [substr($string,0,$len),$residualString];
		}
		$len--;
	}
	


}

$string = 'ilikefacebook';

while($string) {
	$result = getValidWord($string);
	$string = $result[1];
	$finalResult = $finalResult?$finalResult." ":"";
	$finalResult = $finalResult.$result[0];
}

- rahul November 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# prefix solution
Trie = set()
for i in w:
for j in range(len(i)):
Trie.add(i[:j + 1])
print(Trie, S)

i = 0
for j in range(1, len(S)):
if S[i:j] in Trie:
continue
else:
print(S[i:j - 1])
i = j - 1
if S[i:j + 1] not in Trie:
print(False)
else:
print(S[i:j + 1])

- Anonymous May 21, 2020 | 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