6 ms·

> Write a function to return if two words are exactly "one edit" away, where an edit is: Inserting one character anywhere in the word (including at the beginnin

> Write a function to return if two words are exactly "one edit" away, where an edit is: Inserting one character anywhere in the word (including at the beginning and end) Removing one character Replacing exactly one character I've been writing code my entire life, and I've been employed as a software developer for longer than I'd care to admit. I don't have a quick answer to that problem. I know there's an algorithm for computing the "distance" between two strings, so this is probably about that. I have no idea how to write it, and it would never come up in my job, and if it did I'm sure I'd import a library to do it. After searching it, this is what they're talking about https://en.m.wikipedia.org/wiki/Levenshtein_distance https://en.m.wikipedia.org/wiki/Levenshtein_distance That means my only chance of getting this problem correct was either: 1) I prepared for it by studying the bank of questions and memorized the formula for Levenshtein distance. or 2) I considered this problem for the first time during the interview, was immediately struck by the same insight that mathematician Vladimir Levenshtein had in 1965, and developed the algorithm on a white board in real-time. At least they're transparent that if I do lots of HackerRank, LeetCode, and CodeLab then I'll be able to pass their test. I suppose that's better than only those "in the know" realizing how to be employed at FB. I really hope I never have to do another job interview again.

arman_ashrafian 7y ago
Look up "edit distance"... it is one of the first problems an Algorithms course will discuss that can be solved by dynamic programming. But ya, no way anyone is coming up with that unless they have seen it before.
- quantdev 7y ago
  I 100% would be able to solve this problem without seeing it before. Yes, this is because I've practiced a lot of algorithm problems (and I enjoy them, frankly). Yes, this is hackable, but relying on resumes like every other industry (which is implicitly relying on hoop-jumping and college prestige and GPA) is a much worse form of hackable. This levels the playing field and is a signal for (1) how smart someone is and (2) how much they prepared for the interview, both of which are weakly related to the job. Further, people who excel at algorithm are very unlikely to be bad at the kind of work at big tech. It's not perfect, but finding something better at scale is hard.
  - aprdm 7y ago
    I don't think it is a proxy to how smart someone is. I will take point (2) tho.
- pjscott 7y ago
  An algorithm for "do these strings differ by an edit distance of at most 1?" is much simpler, and should be easy to figure out. No dynamic programming required.
  - sn9 7y ago
    This is something I would expect a freshman CS major to be able to solve. It only requires knowledge of looping, conditionals, and how to work with strings in your language (e.g, indexing, finding length, maybe substrings, etc.). This is like a less insulting version of fizzbuzz. People are way overcomplicating this. Any professional programmer could solve this.
coffeemug 7y ago
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.
deleted 7y ago
[deleted]
cellularmitosis 7y ago
Many of these sorts of problems seem intimidating at first, but if you’ve had any training / exposure to implementing recursive solutions (i.e. a bit of SICP), the solutions come much easier because you are trained to think in terms of “what is the tiniest amount of work I can do to advance the problem by one step?” In this case, all we need at each step is to look at one character plus one lookahead character from each string. We’ll call them a and b for string 1 and c and d for string 2. If a and c are equal, advance. If a and d are equal, delete c and advance. If b and c are equal, delete a and advance. If b and d are equal, change one of a or c so they match, then advance. Once you use up an edit, the algo changes to “a and c must match” for the rest of the string. Edit: terminate the algo when one of a or c is a NULL char. If they are both NULL, the string passes. If only one is NULL, then your one edit allowance was not enough to make the strings equal. Also, rather than “deleting” a char, it is sufficient to simply advance that pointer an extra step.

arman_ashrafian 7y ago

Look up "edit distance"... it is one of the first problems an Algorithms course will discuss that can be solved by dynamic programming. But ya, no way anyone is coming up with that unless they have seen it before.

quantdev 7y ago
I 100% would be able to solve this problem without seeing it before. Yes, this is because I've practiced a lot of algorithm problems (and I enjoy them, frankly). Yes, this is hackable, but relying on resumes like every other industry (which is implicitly relying on hoop-jumping and college prestige and GPA) is a much worse form of hackable. This levels the playing field and is a signal for (1) how smart someone is and (2) how much they prepared for the interview, both of which are weakly related to the job. Further, people who excel at algorithm are very unlikely to be bad at the kind of work at big tech. It's not perfect, but finding something better at scale is hard.
- aprdm 7y ago
  I don't think it is a proxy to how smart someone is. I will take point (2) tho.
pjscott 7y ago
An algorithm for "do these strings differ by an edit distance of at most 1?" is much simpler, and should be easy to figure out. No dynamic programming required.
- sn9 7y ago
  This is something I would expect a freshman CS major to be able to solve. It only requires knowledge of looping, conditionals, and how to work with strings in your language (e.g, indexing, finding length, maybe substrings, etc.). This is like a less insulting version of fizzbuzz. People are way overcomplicating this. Any professional programmer could solve this.

coffeemug 7y ago

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.

deleted 7y ago

[deleted]

cellularmitosis 7y ago

Many of these sorts of problems seem intimidating at first, but if you’ve had any training / exposure to implementing recursive solutions (i.e. a bit of SICP), the solutions come much easier because you are trained to think in terms of “what is the tiniest amount of work I can do to advance the problem by one step?” In this case, all we need at each step is to look at one character plus one lookahead character from each string. We’ll call them a and b for string 1 and c and d for string 2. If a and c are equal, advance. If a and d are equal, delete c and advance. If b and c are equal, delete a and advance. If b and d are equal, change one of a or c so they match, then advance. Once you use up an edit, the algo changes to “a and c must match” for the rest of the string. Edit: terminate the algo when one of a or c is a NULL char. If they are both NULL, the string passes. If only one is NULL, then your one edit allowance was not enough to make the strings equal. Also, rather than “deleting” a char, it is sufficient to simply advance that pointer an extra step.