## Ebay Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**In-Person

Hash all the symbols from Chemistry Periodic table. For any given words, use DP to test whether the word can be formed by the hash table. dp[i][j]: whether the sub sequence word[0,...,i-1] can be created.

dp[i][j] = dp[i][j-1] word[i] in the hash table or

dp[i][j-2] word[i-1,i] in the hash table.

I could not assert - will this algo consider combining more than 2 symbols and in every possible order, also?

We can do this by hashing all the words of periodic table,

for comparing [AKBaBr] we can make a bool array(exist) of size 6 , with each exist[i] denotes word from 0 to i exist or not.

Suppose at time t, we arrive at [true,true,false,true,unknown,unknown] , now to fill exist[4] check (exist[3]==true and word[4] is in hash table) Or (exist[2]==true and word[4,5] is in hash table.) ... as both are false so exist[5]=false.

for exist[6] check (exist[4]==true and word[5] is in hash table) Or (exist[3]==true and word[5,6] is in hash table.) as 2nd condition is true .. therefore exist[6] is also true. return(exist[6]);

- ksjeyabarani December 25, 2013