Re:The Lesson to Unlearn
by coffeemug on Saturday December 07, 2019 @07:22PM
(#21733597)
You don’t need edit distance. The solution is literally a for loop and three if statements. The fact that you can’t stop and think for a few seconds about how you might solve this means you’ve been on autopilot for many years now. This is a proxy test to weed out people who work on autopilot and never think.
[ Parent
| on HN ]
Are you proposing brute forcing it? Depending on requirements that might be fine, but I doubt FB would like that kind of solution. If they did, they'd have a different kind of question.
This isn't "brute force." It's solving the specific problem posed rather than a generalization, which in this case is both easier and more efficient (since there are cases in which you could terminate the loop early).
Thanks! I completely misunderstood what the commentator I replied to was saying. Not understanding how to solve it well I assumed they were referring the first option with loops and tests that popped into my head: make every one-edit possible and see if it's one of them.
1st for loop with first word with charecter counts map and second for loop subtracting counts from frist map. See whats remaining in the end, either a map with 1 char left or 1 char left in second. so O(m + n).
abc , adc
a - 1
b - 1
c - 1
after second word loop
b - 1, d
I might be misunderstanding, but doesn't that treat 'abc' and 'cba' as distance 0?
Regardless, I was also thinking Levenshtein is sub-optimal, and that you can probably solve it in O(n+m).
Even if you go for Levenshtein first, you should identify a simple modification to stop calculating the matrix early if the distance is necessarily greater than 1. Get a bit fancier and you can just 'go down the diagonal' and greatly optimize the algorithm.
ah yea, sorry i misread the question.
Re:The Lesson to Unlearn
by senderista on Sunday December 08, 2019 @12:26AM
(#21734474)
That only works up to permutations.