to find the top k words (after computing d), u dont have to fully sort it. u can use the linear selection algorithm to find k and sort those d of those k words if u need the order by "order of closeness" ( O(n +klgk)) or u can use a B-tree and once the B-tree u just have to start from the leftmost leaf node(which has lowest d value) and traverse k nodes. dont quite reber the order for construction of B-tree. after that its O(k) to get the k words, as its been already ordered.
if you know wat the function is doing maybe u can do somewat better. or u can use some heuristics like for example if a threshold (say d=0.25) means that anything greater that threshold is not a good candidate, u can just drop it in any furhter ranking considerations. or some machine learning? but i think pre-computing is the best solution On 3/28/07, Kevin <[EMAIL PROTECTED]> wrote: > > > 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 -~----------~----~----~----~------~----~------~--~---
