Amazon Interview Question Interns
Country: United States
Interview Type: Phone Interview
Greedily solving 1D subproblem will not work. See counter example below.
dadzzzz
dadzzzz
dadzzzz
azzzzzz
dzzzzzz
dzzzzzz
yzzzzzz
if i do row first
i will get 3 dad = 9
but i could get 2 dad and daddy vertical
= 11
In 1D array you can find all strings in O(n) time - e.g. by Aho-Corrasic automaton. Via dynamic programming this is O(n^2). This is not the "hard part", the optimization problem will be interesting..
who can write the algorithm for 1D array, and mark which letter has been used to compose a word? Use as many letters as you can?
this algorithm seems correct to me, for a 1-d array
1. scan the string and find the first word
2. split the string into the first word and letters preceding it and letters following the first word
3. then the longest word is either the first longest word found or recursively solve the other two subproblems.
4. repeat this procedure for the next word and so on (hence dynamic)
take the 2-d array and parse it completely and store all the characters in an unordered multimap, say if a occurs at row 2 and row 5 then store {a,2}, {a,5} in the map. Now start from first row, 'check' all the rows that have common characters with this row and then proceed to the next 'unchecked' row and do the same. O(n^2) space and O(n^2) time
How do you check if a word is valid or not ?? meaning how to validated if "dad" , "daddy" is valid word ?
- Mr.karthik.p March 06, 2013