This is from an interview question, see how do you guys think of it: Given a Enlgish word, how to find these words that pronounce similar to it?
You can have some reasonable assumptions, such as: you have an dictionary which tells you how each word pronounce (such as its phonetic symbols), there is an existing function that can give you the similarity of two words' pronunciation (for example, double d = checkSimilarity(WordA, WordB), where d is between 0.0 to 1.0). You are allowed to have other assumptions, if you think it is reasonable and will help. A straight way is to compare the given word with all the words in the dictionary, and order the d values, then return the top ranking ones. This will take N comparisons for each given word. Plus the time to sort the result (N*logN). Since this supposed to be a data structure and algorithm question, any better ideas? I am thinking we can precompute a NxN similarity matrix, but even with that, it is still N*logN for each word since we need to sort/rank it. Another method, of course, is to use the above method to precompute and pre-ranking for every word --- but this sounds not an interesting idea as for an interview question. :-) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
