Hacker News Reader

Comment by coffeemug | Hacker News Reader

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.

View 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.

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.

That only works up to permutations.

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.

Reply on news.ycombinator.com