I was once asked in an interview how I'd find a row in a relational database where the value in one column was the shortest levenshtein distance away from a search key, and I was absolutely stumped when I realized I didn't really know a sort/search that optimized that way. Of course, by the time I realized I could email the interviewer for the answer an awkward amount of time had passed.
So now I ask HN: is there any "good" way to do this short of some kind of answer like "find a database that natively offers levenshtein distance search"? Are there actually sorting algorithms for sorting by levenshtein distance (other than just using L as a sort function in a traditional sort function)? Are there search algorithms that work well for searching by L distance?
So now I ask HN: is there any "good" way to do this short of some kind of answer like "find a database that natively offers levenshtein distance search"? Are there actually sorting algorithms for sorting by levenshtein distance (other than just using L as a sort function in a traditional sort function)? Are there search algorithms that work well for searching by L distance?