Ebay Interview Question Software Engineer / Developers
Country: United States
I forgot to add when i said hash all letter / letter combinations I just mean hash O (oxygen), Fe( Iron) etc... not all the possible combinations made up of all the elements
Thanks for the explanation! I was struggling with this problem but this post helped me out. I wrote some code(C#) for a part of the problem. I did test this with a couple of use cases but was hoping to get your thoughts on the code below/if you see any bugs with it
static bool IsWordMadeOfSymbols(string word)
{
int i = 0;
while(i < word.Length)
{
string twoLetteredPrefix = null;
string oneLetteredPrefix = null;
if ((i + 1) < word.Length)
{
twoLetteredPrefix = word.Substring(i, 2);
}
oneLetteredPrefix = word[i].ToString();
if (!string.IsNullOrEmpty(twoLetteredPrefix) && symbolSet.Contains(twoLetteredPrefix))
{
i += 2;
}
else if (symbolSet.Contains(oneLetteredPrefix))
{
i += 1;
}
else
{
// since the current character didnt match, just check if current + previous works
// for example 'afg' when 'af' and 'fg' are symbols but g alone is not and 'i' currently points to 'g'
twoLetteredPrefix = word.Substring(i - 1, 2);
return symbolSet.Contains(twoLetteredPrefix);
}
}
return true;
}
just plain answer - i am new here, caution needed :)
ok lets start
elements -112 in list already
dictory words in list already
112 factorial ways these elements can be arranged (ways 1.974507e+182)
and comparing it with each dictory word starting from longest word.(414,800 words)
just by looking at these numbers i feel it will take ones life time to complete.
any body with good knowlede on time complexties kindly give the excat time taken for this logic to produce the required logic :)
(complicated)There is a better way. Construct a Trie with the words in dictionary. Use parallel search for each element in the periodic table. If you find one, remove it from the beginning list and continue. If bigger than the biggess, set it as the biggest
(better)however we can improve it using bitwise representation of words and periodic table elements. we also need a lot of memory(for dictionary 4B*size_of_dict. ~ 0.6MB) Then, use XOR and shifting to find the difference and remember it somewhere(diff. bits and biggest word). This is very rough explanation, but i think you may get the idea. Will try to code it soon :)
I like the trie approach as well, but my logic is slightly diff than Mr. Yoda's.
Create a trie with all the words in the dictionary (from the list)
For each letter from A->Z {
Walk the trie for current letter (say A)
Check if the next valid letter in the trie has a match in the periodic table.
If matches, then descend down the trie.
If not matches && we are at the leaf node in the trie, found a string
Check for biggest string.
}
I think I figured out a way to do this... I'm not going to code it out, but it doesn't seem too bad to code it otherwise.
- B.Z November 11, 2013Let m = size of period table (elements wise), Let n = size of dictionary (elements wise)
Every periodic table element is either (1 letter or 2 letters), so I would hash all letter / letter combinations within the periodic table first. O(m) time O(m) space
Now I'm assuming the dictionary is already stored in some sort of structure, so lets sort that structure based on word length. I'm not sure if merge sort would work because of size but lets assume it does for this case. Sorting time O(nlogn)
Now we start with the longest word in the dictionary and work our way down... once we find a word that matches the current word we have our answer.
To find if the current word can be made up of letter combinations from the periodic table since we have hashed it... we recursively substring the current dictionary word checking if the first letter or first two letters are in the hash table. If either of them are we repeat this process until we go through the entire word. Once we go through an entire word and we have returned true for that word, than that word is the longest word possible.
Best case would be O(1) (first word) Average case O(LogMLogN) worse case (NLogM)
So the computational complexity at the end should be on average O(m + nLogn + LogmLogn) with space complexity O(m), with worst case O(m + nLogn + nLogm )