Skip to content

Instantly share code, notes, and snippets.

@andrewfinnell

andrewfinnell/README.MD

Last active May 14, 2019 02:18
Show Gist options
  • Save andrewfinnell/2ab63c2a154c410189e39e1eee0a0b48 to your computer and use it in GitHub Desktop.
Save andrewfinnell/2ab63c2a154c410189e39e1eee0a0b48 to your computer and use it in GitHub Desktop.
Download ZIP
Largest Common Subsequence (Google Interview Question)
Raw
README.MD

I saw this interview question at https://www.youtube.com/watch?v=10WnvBk9sZc and wanted to see if I was able to solve it. The code is not pretty but it does work. No maps are needed. No state tracking is needed, except for storing the current largest subsequence. Once a larger one is found, the previous one is no longer needed.

The basic concept is to start with the smallest string first as the string which is the largest cannot possibly be completely found in the smaller string. i.e. ABCDE could not ever completely match ABCD. But ABCD can sub match ABCDE.

If this calculation was to be done by a human, we would start at the first letter in the string and then start searching the second string until we found a match. Once we found a match, we would go back to the first string and grab the next letter and then continue searching the second string again; skipping any non-matching letters along the way. We would need to make sure to pick up where we left off in the second string as to not get the matches out of order. This is where str2Index comes into play.

Because the first letter of the first string may not even be in the second string, we will need to eventually skip it. The same applies to the n-th letter of the first string. This is why there are two loops. The first loop tells the second loop where to start when picking the letter to check between the strings.

For example: "AGGTAB", "GXTXAYB" => "GTAB"

Start with A and begin searching "GXTXAYB". "A" is not found until the fourth index is reached. And then another match does not occur until "B" is matched with the 6th index of the second string. This results in a match of "AB" which happens to be the largest match so far.

The next step is to then start at the 1st index of "AGGTAB", which is "G". We've already processed starting with "A" and that resulted in "AB". Starting with "G" results in a match at index 0 of the second string. The next "G" does not match anything. "T" matches the 2nd index. "A" matches the 4th index. and finally "B" matches the 6th index. match equals "GTAB".

I did the work using jsfiddle.net as it's really easy to execute javascript and see the results.

Raw
fiddle.css
body {
background-color: #20262E;
color: white;
}
input {
background-color: #FFFFFF;
border: 0px;
padding: 5px;
}
input[type=submit] {
background-color: #FFFFFF;
border: 0px;
padding-left: 10px;
padding-right: 10px;
}
Raw
fiddle.html
<div class="container">
<form name="test">
<input type=text id="input1" value="ABADC">
<input type=text id="input2" value="BACBAD">
<input type="submit" value="Do it" onclick="javascript:calc()">
</form>
</div>
<div class="container">
<div id="output">
</div>
</div>
Raw
index.js
var input1 = document.getElementById("input1");
var input2 = document.getElementById("input2");
/**
* Find the longest non-consecutive run of characters
* between two strings.
*/
function longestCommon(str1, str2) {
// Want the shortest to be str1
if (str1.length > str2.length) {
var tmp = str2;
str2 = str1;
str1 = tmp;
}
// The one and only longest match thus far.
var longestMatch = "";
// Loop through the string n-number of times where
// n is the length of the string. Each loop will result
// in the next loop _starting_ at the next character
// in the string. The first iteration of "ABBA" will
// start with "A" and the next iteration will start with
// "B" and so on.
for (var i1 = 0; i1 < str1.length; ++i1) {
var match = "";
var str2Index = 0;
// The first iteration of the loop from above
// means this loop starts at index 0. The idea
// is to take the first character and find the first
// match in the second string.
//
// If there is a match then then advance the second
// strings index by 1 and add the matched character to the
// current result string.
//
// If there is not a match, then advance the first string index by 1.
// Once the end of either string is met end the loop.
for (var i2 = i1; i2 < str1.length; ) {
var char = str1[i2];
var str2Char = str2[str2Index];
if (char === str2Char) {
match = match + char;
i2++;
} else if (str2Index >= str2.length) {
i2 = str1.length;
}
str2Index++;
}
// If the current match is longer than the latest match,
// set the new longest match to the current result.
if (match.length > longestMatch.length) {
longestMatch = match;
}
}
return longestMatch;
}
function writeLine(str) {
var output = document.getElementById("output").innerHTML;
document.getElementById("output").innerHTML = output + "<br>" + str;
}
// Calculate the longest match between the two input fields.
function calc() {
event.preventDefault();
var str1 = input1.value;
var str2 = input2.value;
writeLine(longestCommon(str1, str2));
return false;
}
// Expose the calc() function to the window object to make
// the onclick handler easier to use.
window.calc = calc;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment