## Ebay Interview Question for Software Engineer / Developers

Country: United States

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

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.

Let 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 )

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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;
}``````

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

just plain answer - i am new here, caution needed :)
ok lets start

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 :)

Comment hidden because of low score. Click to expand.
0

I pseudo - explained my solution below let me know what you think of the logic. It's under B.Z

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

(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 :)

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

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.
}``````

Comment hidden because of low score. Click to expand.
0

Yeah, they are kind of a similar :) I was going with parallelism since in interviews most big questions end up talking about it. Cheers!

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

Didnt quite get the question yet. Should the word be made up of all symbols or is it just that the starting letter(s) should be a symbol? Example in the question is confusing: O=> Oxygen other than O, n, not sure if any other alphabets are symbols

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.

### 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.