4 ms·

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 y

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.

iudqnolq 7y ago
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.
- dominotw 7y ago
  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
  - Cpoll 7y ago
    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.
    - dominotw 7y ago
      ah yea, sorry i misread the question.
  - senderista 7y ago
    That only works up to permutations.
- stiglitz 7y ago
  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).
  - iudqnolq 7y ago
    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.

iudqnolq 7y ago

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.

dominotw 7y ago
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
- Cpoll 7y ago
  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.
  - dominotw 7y ago
    ah yea, sorry i misread the question.
- senderista 7y ago
  That only works up to permutations.
stiglitz 7y ago
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).
- iudqnolq 7y ago
  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.