Comment by anon9001 | Hacker News Reader

Comment by anon9001 | Hacker News Reader

Parent Full thread

> 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

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.

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.

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.

That only works up to permutations.

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.

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.

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.

I don't think it is a proxy to how smart someone is. I will take point (2) tho.

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.

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.

Reply on news.ycombinator.com