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

This is an initial phone screen and in this context this a valuable approach. This is one level past fizzbuzz. 'Can you code something past "hello world"?' is what they're looking for. There's nothing worse than an onsite with somebody who just cannot code at all.

The particular example is bad, though, because there’s room for a massive algorithmic insight. There’s an obvious-enough but terribly inefficient way to do it, and a fancy efficient algorithm that either you know or you don’t. If given this question I would middle through the inefficient way, aware that there must be a better algorithm out there that’s eluding me, and I’d probably get a “vaguely pass” mark, but the kid fresh out of college who has spent the last three months doing leetcode study will regurgitate the correct solution and pass with flying colours.

(Once in a while maybe a complete genius takes the test and reinvents the good algorithm on the spot, but only gets the same grade as the diligent student, for his effort.)

Too many basic coding screens seem to rely on some algorithmic insight. I would rather give a candidate a complicated-but-straightforward problem (like a super-fizzbuzz that takes half a page to describe,with a bunch of complicated rules and exceptions to those rules) because that’s closer to what a real world programming task looks like. No room for a clever insight, just translate the problem statement, carefully, into code, and test whether it runs correctly.

> because that’s closer to what a real world programming task looks like

To make it even closer, you'd have to have people coming in at various points with contradictory updates to the task, impossible requests, an overbearing managerial diktat, etc.

Actual questions in phonescreen i got were these

https://leetcode.com/problems/powx-n/

https://leetcode.com/problems/product-of-array-except-self/

For the second one:

> Please solve it without division

This is just an absurd constraint…

That's good, they're trying to put everyone in a level play field given the system they use.