How a Googler solves coding problems

Well, 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".

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.

I once had a teacher in high school who challenged the class to write down the instructions for making a peanut-butter sandwich.

If anyone created a fool-proof set of instructions, he’d give them an A for the course.

I wrote down:“Open the peanut butter, spread it on the bread, take the jelly, spread it on top of the peanut butter.

Put another piece of bread on top and you’re done.

”I thought I had done fine, until my teacher took a scoop of peanut butter and started spreading it on the sliced loaf of bread — without taking it out of the plastic bag it came in.

Programs (like my teacher) 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 the 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".

When we got to index 4, we found "yef", which was almost a match, but it wasn’t completely a match, since the third character was different.

So we kept going until we reached 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, we call this 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.

At this point, we can have some confidence that our algorithm works, and so now it’s time to formalize the algorithm, bringing us to the next step:2) Write it in English.

Here, we think about the algorithm I 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.

Start at the beginning of the string.

Look at each set of 3 characters (or however many characters there are in searchString).

If any of them are equal to searchString, return the current index.

If we get to the end of the string without anything matching, return -1.

Seems good!3) Write pseudocode.

Pseudocode isn’t really code, but it mimics the structure of code.

Here’s how I would write a pseudocode version of my algorithm above: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 indexat the end, if we haven't found a match yet, return -1.

I could go a bit closer to code by writing it this way:for each index in sourceString, N = searchString.

length POSSIBLE_MATCH = sourceString[index to index+N] if POSSIBLE_MATCH === searchString: return indexreturn -1How much your pseudocode resembles code is up to you, and over time you’ll discover the way that works best for you!4) Translate what you can to code.

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

This is the first time in the process that we have to worry about syntax, function parameters and language rules.

Maybe you can’t write everything out, and that’s okay.

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.

5) Don’t guess.

A common mistake I see in new coders is the practice of finding 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.

The number of ways that your program can be incorrect DOUBLES with every new thing you are not sure about.

Not sure about 1 thing?.Great — if your code doesn’t work, only 1 thing can be the culprit.

But 2 things?.3 possibilities (thing A is broken, or thing B is broken, or both are broken!).

3 things?.7 possibilities.

It quickly spirals out of control.

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

a(n) = (2^n) — 1Test your new code first.

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

In the previous step, I wasn’t sure of the way to select a certain part of a string in JavaScript.

So off I go to Google:https://www.


com/search?q=how+to+select+part+of+a+string+in+javascriptThe first result is from w3schools.

A bit dated, but usually dependable.




aspBased on this, 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 I am sure of how this function behaves.

So when I plug this 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;}ConclusionIf you’ve read to the end, all I can say now is: try it.

Go back to that programming problem that you set aside last week in frustration.

I guarantee you’ll see immediate improvement.

Good luck, and happy coding!.. More details

Leave a Reply