Facebook Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

This can be solved in O(N), where N is the length of the word.

Lets assume,
- that the length of the word, N is given
- the machine returns 1 for each letter in test string matching the letter in dictionary word in the same index

private void findWord(int n) {
        Character[] result = new Character[n];
        char[] sample = new char[n];
        int prevCount = 0;
        for (int c = 'a'; c <= 'z'; c++) {
            fillAll(sample, result, (char)c);
            int count1 = checkWord(sample);
            if (prevCount == count1) {
                // the alphabet c never appeared in result; so skip and go to the next alphabet
                continue;
            }
            c++; // go to next char
            for (int i = 0; i < n; i++) {
                char old = sample[i];
                if (result[i] != null) {
                    // this index already has a valid char
                    continue;
                } else {
                    sample[i] = (char) c;
                }
                int count2 = checkWord(sample);
                if (count2 > count1) {
                    // c belongs to index i
                    count1++;
                    result[i] = (char)c;
                } else if(count2<count1 ) {
                    // old char belongs to this index;
                    result[i] = old;
                    sample[i] = old;
                }
            }
            prevCount = count1;
        }
    }

    private void fillAll(char[] sample, Character[] result, char c) {
        // file the index i of sample with char c where result[c] is null;
    }

    private int checkWord(char[] sample) {
        // return the count of chars in sample, matching the corresponding index in the dictionary word
    }

Here for each iteration of outer loop we complete two alphabets, hence it runs 13 time max.
The inner loop runs N times in worst case.
Hence the word can be guess in 13*N trials

- Pragalathan M September 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

/* Algo:
 * 1. Start constructing the seed string such that each char in seed matches the char in dict and that too at the right position.
 *    Assuming the  machine function(matchStr) tells the count  of chars in given string which are at the right index of dict word.
 *    If char at 0th index is matched , try for the 1st index. To know if the char is matched, matchedCount > matchedSoFar
 * 2. If mactchedSoFar == dictWordLengt. We have guessed the word 
 */
public class WordGameMachine2 {

	static String dictWord = "daddy";
	
	public static int matchStr(String str){
		int cnt=0;
		for(int i=0;i<=str.length()-1;i++){
			if(dictWord.charAt(i) == str.charAt(i)){
				cnt++;
			}
		}
		return cnt;
	}
	
	public static void guessWord(){
		int guessWordLen = dictWord.length();
		// Find a seed of chars containing same chars in the same order as in the dict string
		String seed="";
		int maxMatchedSoFar=0;
		for(char c='a';c<='z';c++){
			if(maxMatchedSoFar==guessWordLen){
				System.out.println("Guessed word : " + seed);
				break;
			}
			String tmpSeed = seed+c;
			int matchedCount = matchStr(tmpSeed); // get no of times character c is present in the dict word 
			if(matchedCount > maxMatchedSoFar ){
				maxMatchedSoFar=matchedCount;
				seed = tmpSeed;
				c='a'-1; // so that c= 'a' in next iteration
			}
		}
	}
	
	public static void main(String[] args) {	
		guessWord();
	}
}

- Mayank Jain August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let's assume we don't know the order at which the characters are arranged in the word.

We first do a pass through of the alphabet O(26), to see what letters we "hit", so we know which letters are in the word and how many of that specific letter there is.

Now, we will have a string of unorganized letters, so we will sort these letters into (let's call it) string S. You will see why in a little bit.

We know that the dictionary could be interpreted as a list. To match strings, we can check their hashcodes. But there are so many different ways of arranging strings that this can be very cumbersome. Luckily, we can sort a string's letters by ascii value (for example), to get a hashcode that applies to all combinations of strings. We simply sort every word in the dictionary and compare its hash value to that of S. When we get a match, we will have found the word we're looking for.


If N = # of words in dictionary and k = length of target word and m = length of longest word in dictionary, our system runs in:

O(26) + O(klogk) + O(Nmlogm) + O(n), for a big O of O(Nmlogm)

- SK April 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The match will not be unique, say I'm looking for 'cat', this approach will match with 'act' as the first match. You need to consider permutations of string once you know it's constituents. Also, first steps complexity is O(k) as words like 'aaaaaaa' will require multiple passes for same alphabet.
Let me know if I've missed something.

- Anil April 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

But is it ok to guess random characters? if i understand the q, you have to guess a valid word

- mithya April 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

If guessing non words is allowed, then the problem becomes simple:

Start with all 26 alphabets in collection
Make 26 guesses for each character one by one.
If machine replies 0, then remove that letter from the collection
Otherwise, machine may return 1 or a larger value (e.g. for 'miss', when you query 's', it will return 2), maintain alphabet => frequency information

At the end, you will have total length L of the word (which is summation of the frequency) and alphabet => frequency information

Now just go through each word from the dictionary of length L and match the frequency of characters.
Repeat till all the words have been explored (we need to handle anagrams- 'cat' and 'act')

- mithya April 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

You have to pick up from dictionary otherwise you could experience a wrong answer, so it won't work "We first do a pass through of the alphabet".

- undefined April 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cant this be improved using a trie

- codewarrior April 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sample Code With Trie in constant complexity

public int wordGuesser(String str) {
			int i = 0;
			TrieNode root = this.getRoot();
			for (char ch : str.toCharArray()) {
				TrieNode data = root.getTrieNodes()[atoi(ch)];
				if (data != null) {
					i++;
					root = data;

				} else {
					return i;
				}
			}
			return i;
		}

- Sheetal April 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sample Code with trie (it counts number of matching charcters in constant complexity)

public int wordGuesser(String str) {
			int i = 0;
			TrieNode root = this.getRoot();
			for (char ch : str.toCharArray()) {
				TrieNode data = root.getTrieNodes()[atoi(ch)];
				if (data != null) {
					i++;
					root = data;

				} else {
					return i;
				}
			}
			return i;
		}

- Sheetal April 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is, do we now how long the word is or is that what we need to guess also?

If we know, simply firstly ask about "aaaaaaaaa" and get the answer N. Then slowly try "baaaaaa", "abaaaaa", "aabaaaa" ... and everytime N goes up it means there is b, if it goes down it means there goes a. Then you can shift to 'c' (or 'c' vs 'd'). The complexity is k.N where k is the number of possible letters.

code

public static void main(String[] args) {
		String start = "aaaaaaaaaa";
		char[] startArray = start.toCharArray();
		;
		Character[] result = new Character[10];
		int startNumber = checkWord(startArray);
		for (int charCounter = (int) 'a'; charCounter <= (int) 'z'; charCounter++) {
			for (int i = 0; i < result.length; i++) {
				Character c = startArray[i];
				startArray[i] = (char) charCounter;
				int changedNumber = checkWord(startArray);
				startArray[i] = c;
				if (changedNumber > startNumber) {
					result[i] = (char) charCounter;
				}
				if (changedNumber < startNumber) {
					result[i] = c;
				}

			}
		}
		for (int i = 0; i < result.length; i++) {
			System.out.print(result[i] + ", ");
		}
		System.out.println();
	}

	public static int checkWord(char[] s) {
		String result = "resultqard";
		int resultInt = 0;
		for (int i = 0; i < result.length(); i++) {
			if (result.charAt(i) == s[i]) {
				resultInt++;
			}
		}
		return resultInt;
	}

I think it may be done easier using binary search for 'b's like that:
firstly need to find a String that returns 0, assume it is "aaaaaaaa". Then you can ask for "bbbbaaaa" and "aaaabbbb" and go deeper if any of them returned bigger number than 0 again by halves.

- Demo April 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

According to the task we need to guess a word from the dictionary - fixed amount of words. I guess we should try to minimize calls to the Machine with our word candidate. Lets say method MatchedCharsAnswer(Word) does that: returns how many characters our Word matched with Answer. I also assume that if answer is "AA" MatchedCharsAnswer("A") and MatchedCharsAnswer("ABC") return 1 as we matched first character "A" of the Answer.

Note: for any pair of the words their matched characters are fixed and known(can be calculated by us in our method MatchedChars(word1, word2) by simply comparing characters on the same positions). Also MatchedChars(word1, word2)==MathedChars(word2, word1).

For ex. for "cat" and "pet" it is 1. MatchedChars("cat", "pet")==1 as character at position number 3 is same - "t".

How do we know the word W we just checked is the answer? According to the task Answer is one of words from the Dictionary. If MatchedCharsAnswer(W) == W.length and there is no word (W+) which starts from W in the dictionary and MatchedCharsAnswer(W)<MatchedCharsAnswer(W+). For example W="great" and W+ is "greatest".

1. Guess some random word W1 from the dictionary (or longest one): M1 = MatchedCharsAnswer(W1)
2. Check W1 is not answer
3. If word is not guessed search for the word W2 in the dictionary so that MathedChars(W1, W2)==M1 as we know that the Answer can be only among such words.
3. M2 = MatchedCharsAnswer(W2).
4. Check if W2 is the answer
5. If answer is not found, find word W3 in the dictionary so that
MathedChars(W1, W3)==M1 and
MathedChars(W2, W3)==M2
...
6. If answer is not found, find word Wx in the dictionary so that
MathedChars(W1, Wx)==M1
MathedChars(W2, Wx)==M2
MathedChars(W3, Wx)==M3
...
5. Continue till answer is found.

- geraskov April 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain a bit more clearly? What does MathedChars() do?

- codewarrior April 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I tried to add details to my answer. hope this help to understand the solution.

- geraskov April 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do we really require to check all the previous matches when we select a new word. It follows transitive closure. I mean...when MatchedCharsAnswer(W1)=M1, then we should search for a word W2, whose MatchedChars(W1, W2) >=M1 then MatchedCharsAnswer(W2)>=M1.

- bharat April 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Build a index of the dictionary:
for each letter 'ch'
(ch,i) points to the words containing 'ch' i times, and each word also points to all (ch, i) applies to it.
You need O(n) space/time to build the index, and O(1) to find the answer.

- nanny April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

?

- nanny April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

?

- nanny April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming the machine returns matches means matches anywhere in the target string (ex. if you enter "b", and target is "barb", machine will return 2), loop through alphabet which gives you the count of each character in the target string.

Now create all permutations of the characters you know are in the target string. There number of permutations will be: n! / (n1!*n2!*...*nr!) where n1, n2,...nr are the counts of each character 1...r.

This is a perhaps overly simple algorithm that quickly becomes heavy to run for large target strings. However, it works nicely for short ones.

- JW April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the way i feel this can be solved assuming we know the maximum length of all words in the dictionary (assume k for now)

STEP 1.
1. try aaaa...aaa # = k to find # of a's in the word
2. try bbbb...bbb # = k to find # of b's in the word
...
26. try zzzz...zzz # = k to find # of z's in the word

we can terminate early if we have found k letters.

STEP 2.
build a trie out of all words' permutations, e.g. for car we need to use acr, arc, rac, rca, cra, car to build the trie.
Index all the letters found in step 1 into the trie. NOTE. order does not matter here as we the trie contains all the possible ways in which the letter can be arranged.

we could get multiple words. this is an artifact of missing ordering from the machine.

- trent.tong May 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assumption I made in this problem is that machine tells how many characters matched given query string. For example, if the word to guess is "daddy", the machine will returns 3 when the query string is "b".
Based on that assumption, the following would solve the problem

Step 1: for all alphabet letters, find out how many each alphabet exists in the target word and add the alphabet letter to the seed as many as it exists.

Step 2: previous steps will produce unordered string with the same size with the target words with correct number of alphabet letters.

Recursively, create the possible permutation with same length as the target word and find the matching string.

string tryPermutation(string seed, string left)
{
	string found = "";
string tryPermutation(string seed, string left)
{
	string found = "";
	if (left.length() == 0 && IsCorrectWord(seed) == true)
		return seed;

	for (int i = 0; i < left.length(); i++)
	{
		string newSeed(seed);
		newSeed.push_back(left.at(i));
		string newLeft = left.substr(0, i);
		newLeft.append(left.substr(i+1, left.length()-(i+1)));
		found = tryPermutation(newSeed, newLeft);
		if (!found.empty())
			break;
	}
	return found;
}
		return seed;

	for (int i = 0; i < left.length(); i++)
	{
		string newSeed(seed);
		newSeed.push_back(left.at(i));
		string newLeft = left.substr(0, i);
		newLeft.append(left.substr(i+1, left.length()-(i+1)));
		found = tryPermutation(newSeed, newLeft);
		if (!found.empty())
			break;
	}
	return found;
}

//assumption: countMatched returns number of characters matching from given string. e.g. for "bobby", countMatched("b") will return 3.
string GuessWord()
{
	string seed = "";

	for(int i = 'a'; i<= 'z'; i++)
	{
		int nMatched = 0;
		if (nMatched = countMatched((char)i))
		{
			for (int j = 0; j < nMatched; j++)
				seed.push_back((char)i);
		}
	}
	//we now have correct number of characters for the target word.
	string found = tryPermutation("", seed);
}

- hankm2004 June 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I like this approach, re-written in a simple code

/*
 * 1. For each alphabet find how many occurrences of it are present in the word by calling machine function
 * 2. Now we have an jumbles characters word of same length and containing same no of charaters as in the target word
 * 3. Try all the permutations to see if its the right word
 * 
 */
public class WordGameMachine {

	static String dictWord = "daddy";
	
	public static int matchChar(Character c){
		int cnt=0;
		for(int i=0;i<=dictWord.length()-1;i++){
			if(dictWord.charAt(i) == c){
				cnt++;
			}
		}
		return cnt;
	}
	
	public static boolean isCorrectWord(String str){
		return dictWord.equals(str) ? true:false;
	}
	
	public static void permuteSeed(String str, String result){
		if(str.length()==0){
			if(isCorrectWord(result) == true){
				System.out.println("Guessed word : " + result);
				return;
			}
		}
		
		for(int i=0;i<=str.length()-1;i++){
			permuteSeed(str.substring(0,i)+str.substring(i+1,str.length()) , result+str.charAt(i));
		}		
	}
	
	public static void guessWord(){
		
		// Find a seed of chars containing same number of chars as in the dict string
		String seed="";
		for(char c='a';c<='z';c++){
			int matchedCount = matchChar(c); // get no of times character c is present in the dict word 
			while(matchedCount > 0){
				seed = seed + c;
				matchedCount--;
			}
		}
		
		System.out.println("seed="+ seed);		
		//For all permutations of this seed and check if its the right word
		permuteSeed(seed,"");
	}
	
	public static void main(String[] args) {	
		guessWord();
	}
}

- Mayank Jain August 14, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my solution. I build a Trie out of the dictionary and crack one character at a time.

import java.*;
import java.util.*;
import java.util.function.*;
class DictCracker
{
  static class TrieNode
  {
    public HashMap<Character,TrieNode> childs=new HashMap<Character,TrieNode>();
  }
  static class DictTrie
  {
    public TrieNode root=new TrieNode();
    public DictTrie(ArrayList<String> dict)
    {
      for(String w:dict)
        addWord(root,w);
    }
    void addWord(TrieNode n,String w)
    {
      int l=w.length();
      for(int i=0;i<l;i++)
      {
        char ch=w.charAt(i);
        TrieNode chld=n.childs.get(ch);
        if(chld==null)
        {
          chld=new TrieNode();
          n.childs.put(ch,chld);
        }
        n=chld;
      }
    }
  }
  static String crack(ArrayList<String> dict,Function<String,Integer> machine)
  {
    DictTrie t=new DictTrie(dict);
    TrieNode n=t.root;
    boolean found;
    String ret="";
    do
    {
      found=false;
      for(Map.Entry<Character,TrieNode> ch:n.childs.entrySet())
      {
        String test=ret+ch.getKey();
        if(machine.apply(test)==test.length())
        {
          found=true;
          n=ch.getValue();
          ret=test;
          break;
        }
      }
    }while(found);
    return ret;
  }
  public static void main(String[] args)
  {
    ArrayList<String> dict=new ArrayList<String>(Arrays.asList( new String[]{"ab","zc","zr"}));
    String word="zr";
    String c=crack(dict,new Function<String,Integer>()
                                         {
      public Integer apply(String test)
      {
        int wl=word.length();
        int tl=test.length();
        if(tl>wl)
          return -1;
        int i;
        for(i=0;i<tl;i++)
        {
          if(test.charAt(i)!=word.charAt(i))
            break;
        }
        return i;
      }
    });
    System.out.format("word=%s%n",c);
  }
}

- Tewelde November 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would go a different path
Define 3 sets, one for characters that aren't in the word N, one for characters that are in the word I and one of partial words P. In P we will put partial words and how many characters were matched
Take a word - if you get full match, put each character in M. If you get a match less then the number of characters of the word put it in P.
However if you get zero matches, take each character and put it in N. Then scan each word in P and remove each character that is in the word with zero matches. If by removing a character you get to a length of the previously matched ones, remove it from P and put the characters in M


Repeat until you get out of words or the elements of N and M are 26.
Now take all characters in M and start permutate them with length of M.length and increasing until we guess..

I would guess that duplicates won't play otherwise there is no way to properly code on a whiteboard a proper solution

It worth asking questions like are there duplicates like in paraLLeL which can significantly decrease the time to crack the final solution

- nikolay.ivanchev March 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

chutie sale

- loru June 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

chutie sale , lund question

- loru June 13, 2015 | 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