Ebay Interview Question
Software Engineer / DevelopersCountry: 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