Facebook Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
/* 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();
}
}
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)
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.
But is it ok to guess random characters? if i understand the q, you have to guess a valid word
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')
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".
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;
}
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;
}
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.
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.
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.
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.
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);
}
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();
}
}
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);
}
}
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
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
Here for each iteration of outer loop we complete two alphabets, hence it runs 13 time max.
- Pragalathan M September 24, 2015The inner loop runs N times in worst case.
Hence the word can be guess in 13*N trials