Google Coding Mock Interview: Buddy Strings

[@tryexponent]

Did you enjoy this mock interview about buddy strings? Get access to hundreds more mock questions just like this in Exponent's Software Engineer Interview Prep Course: bit.ly/3rkqsaW

[@joeindia1647]

I am afraid that this is not a Google level interview problem. A better problem would be, given two strings, what the minimum swap operation to make them the same.

[@your_name96]

This min swap is a well known dp problem so not an on-site problem

[@sinank7032]

split both strings into character arrays and convert to their ascii numerical values. create 3rd array which is the difference between the two word's characters. if 2 characters can be swapped, you should get an array like [ 0 0 N 0 0 -N 0 0 ] So then just check that only 2 entries are non-zero and that the two non-zero ones add up to 0. O(N) solution, good if you expect the result to be TRUE often, otherwise can check character by character to exit earlier. Oh yea and check they are the same length at first.

[@ranavital9046]

That solution will work for most of the cases, but for the specific case where indeed there are 2 diffs, but the subtraction between them will be abs equal, for example: s = abcdf goal = accde diffs_arr = [0, -1, 0, 0, 1]

[@richardujadughele6329]

I don’t think the interviewer fully understood why Derek was using a set. And Derek didn’t do a good job explaining his case. If start and goal are the same word, then you return true if the word has any duplicate characters. For instance, if the start and goal are both “hello”, you would return true because you can swap the first L with the second L to get the same word. But if the start and goal are both “abcde”, you would return false because you couldn’t swap any letters to get the same word. Derek’s use of a set was to determine if there are any duplicate characters in the word. By putting the characters in the set, the duplicates would be filtered out and the length of the set would be less than the length of the string. This is a linear time algorithm. If you just iterated through the string without the set, you would have to check whether each character was seen prior, which would be a quadratic runtime. But also, ultimately Derek heard the correction the interviewer gave, and (even though his solution was better), he agreed with her correction but didn’t change his code to reflect the correction. Which makes it look like either he didn’t understand what she was saying, or he was ignoring her feedback.

[@Muntazir-Ali]

Nice explanation..

[@kartikprakash5179]

Great video. However if I heard the question correctly at the beginning the objective was to return true if ‘start’ string after swapping can be equal to the ‘goal’ string or not but throughout the video it was assumed the opposite. It doesn’t make a huge difference but something I noticed.

[@Asemco]

Derek uses I -> J for his iterators. Everyone knows it's I -> D, followed by E since we code in one. 😉 In all seriousness, this question shows that the value of clarifying questions is unreal. We got a couple, but Derek spending a little more time with questions may smoothen out the rest of the process. That being said, getting into the actual solution can help bring more questions to light (and is exactly what I'd do), so it is what it is. It would have been nice for Exponent to provide the test cases for this type of question. A dev will have to go for a more robust solution if they can't bring their own test cases to the table.