TrashPanda Wiki
Register
Advertisement

These are the notes I have taken while reading through the medium article How a Googler solves coding problems by Steve Merritt. We will be working through a practice problem in these steps. The problem given is this :

"Given two strings, sourceString and searchString, return the fist index at which searchString occurs within sourceString. If searchString does not occur within sourceString, return -1.

Step 1: Draw it[]

Never immediatley start writing code when working on a problem. Often the solution to a problem is not trivial, even if it appears simple at first glance. Working it out on paper allows you to figure out a solution and verify that the solution works in a few different situations, all before even writing a single line of code.

In this fist step we are just trying to figure out how you, as a human computer, solve the problem.

Draw pictures. Use arrows. Put numbers into little boxes. Whatever helps you visualize the problem. The goal here is to problem-solve.

Start by inventing some simple inputs. If the function "takes a string", "abc" makes a great first example. Figure out what the correct result should be, then try to think *how* you figured out the problem, and the steps that were involved.

Let's imagine the strings have these values :
sourceString: "abcdyesefgh"
searchString: "yes"
We can see that searchString is inside sourceString. But how did we do that? 
We started at the beginning of sourceString and read through is until we reached the end, looking at every 3-character piece to see if it matced the word "yes". 
For example, "abc", "bcd", "cde", and so on. When we got to index 4, we found "yes", and so we decided that there is a match, and it starts at index 4.

Programs need very specific rules or they'll do the wrong thing. So when we write down our algorithm, we need to make sure we express everything and handle all possible scenarios. Returning the right answer when we DO find a match is nice, but we also need to return the right answer when we DON'T find a match.

Let's try again with another pair of strings :
sourceString: "abcdyefg"
searchString: "yes"
Here, we started at the beginning of sourceString and read through it until we reached the end, looking at every 3-character piece to see if it matched the word "yes". We keep going till we reach the end of the string, and then decided there wasn't a match, so we returned -1.

We've identified the series of steps (in programming, this is called an algorithm) that we take to solve the problem, and we've tried it in a couple of different scenarios, getting the correct result each time.

Step 2: Write it in English[]

Here, we think about the algorithm we identified in step 1, and try to write it out in English. This makes the steps concrete, so that we can refer back to it later when writing the code.

  1. Start at the beginning of the string
  2. Look at each set of 3 characters (or however many characters there are in searchString)
  3. If any of them are equal to searchString, return the current index
  4. If we get to the end of the string without anything matching, return -1.

Step 3: Write pseudocode[]

Pseudocode mimics the structure of code without it really being code.

for each index in sourceString,
    there are N characters in searchString
    let N chars from index onward be called POSSIBLE_MATCH
    if POSSIBLE_MATCH is equal to searchString, return index
at the end, if we haven't found a match yet, return -1
I could go a bit closer to actual code by writing:
for each index in sourceString,
    N = searchString.length
    POSSIBLE_MATCH = sourceString[index to index+N]
    if POSSIBLE_MATCH === searchString:
        return index
return -1

Step 4: Translate what you can to code[]

Note: For easier problems, this can be combined with the step above.

Here is where we worry about syntax, function parameters and language rules. Maybe you can't write everything out, and that's ok. Write in the pieces that you know!

function findFirstMatch(searchString, sourceString) {
    let length = searchString.length;
    for (let index = 0; index < sourceString.length; index++) {
        let possibleMatch = <the LENGTH chars starting at index i>
        if (possibleMatch === searchString) {
            return index;
        }
    }
    return -1;
}

Notice that I left part of this code blank. This is intentional! I wasn't sure of the syntax for slicing strings in JavaScript, so I'll go look it up in the next step.

Step 5: Don't guess[]

A common mistake here is to find something on the internet, saying "maybe this will work", and plugging it into your program without testing it.

The more pieces of your program you don't understand, the less likely you are to end up with the right solution.

Side note: The formula for ways in which your program can be wrong follows the Mersenne sequence :

a(n) = (2^n) - 1

Test your new code first. Finding something on the internet is great, but before you plug it into your program, test it in a small, seperate space to make sure it works in the way that you think it does.

Based on my google search for "how to select part of a string in javascript", I assume that I should use
substr(index, searchString.length)
to extract the portion of sourceString each time. But it's an assumption, nothing more. So first, I create a small example to test the behavior.
>> let testStr = "abcdefghi"
>> let subStr = testStr.substr(3, 4); // simple, easy usage
>> console.log(subStr);
"defg"
>> subStr = testStr.substr(8, 5); // ask for more chars than exist
"i"
Now that I am sure of how this function behaves I can plug it into my program, I know that if my program doesn't work, it's not the new piece I added that's misbehaving.
And with that, I can plug in the final piece of my program:
function findFirstMatch(searchString, sourceString) {
    let length = searchString.length;
    for (let index = 0; index < sourceString.length; index++) {
        let possibleMatch = (
            sourceString.substr(index, searchString.length));
        if (possibleMatch === searchString) {
            return index;
        }
    }
    return -1;
}
Advertisement