February 28, 2019 at 12:39

How Google Programmer Solves Common Problems

    image

    From a translator : We are publishing for you a translation of an article by Steve Merrit , a Google employee who talks about how he solves typical programming problems. The post will be useful primarily to novice programmers.

    In this article I will talk about my strategy for solving problems that arise during the work on a project, from start to finish. I use it in the daily workflow at Google, as well as when working with coders of all levels (colleagues, bootcamps graduates, university students). A structured technique minimizes the time spent on debugging and at the same time leads to the creation of better code.

    By the way, the same strategy often works during interviews in large technology corporations. Three years ago I got a job at Google thanks to her.

    We remind you: for all readers of “Habr” - a discount of 10,000 rubles when registering for any Skillbox course using the “Habr” promo code.

    Skillbox recommends: The on-line educational course "Profession Java-developer" .

    Step by step


    I will show examples in the form of typical problems to reveal the topic.

    Problem: “Given two lines, sourceString and searchString, you need to return the first index when sourceString appears in searchString. If searchString is not in sourceString, return -1. "

    1. Draw it


    Starting to write code right away is not a good idea. First you need to outline a way to solve the problem. Begin by forming a hypothesis and evidence of your point of view. And get to work only when you already have a clear plan. If this is not done, then when the work has already begun, you may encounter the fact that individual pieces of code will not correspond to each other.

    The solution can often be nontrivial, even if the task looks simple. Paper planning helps you find the right approach and make sure it works in other situations. And you will learn all this even before the first line of code is written.

    So don’t start writing code, don’t even think about it. You will have a lot of time to work. You are a human computer, and you solve the problem.

    Put the solution algorithm on paper. If something helps you visualize your plan, do it. The task is to solve the problem with a pencil and paper, without a keyboard.

    Come up with simple input. If the function “passes the string”, then “abc” is the first excellent example. Try to understand what the correct result should be. Then think about how you understood the problem, what steps were taken.

    Imagine that strings have the following values:

    sourceString: "abcdyesefgh"
    searchString: "yes"

    So we can see that searchString is inside sourceString. But how did we come to this? We started from the beginning of sourceString and read it to the end, looking at each three-character fragment to see if it matches the word “yes”. For example, “abc”, “bcd”, “cde” and so on. When we got to index 4, we found “yes” and therefore decided that there was a coincidence, and it starts at index 4.

    I had a teacher at the institute who asked me to come up with instructions for creating a peanut butter sandwich. For a detailed and understandable instruction, they promised us the highest rating.

    I wrote the following:

    “Open the peanut butter, spread it over the bread. Put another piece of bread on top and you're done. ”

    I thought I managed it until the teacher took the butter and spread on the bread, which was still in a plastic bag.

    Programs, like my teacher, require very detailed instructions to make the task possible. Therefore, when we create the algorithm, we make sure that we provide for everything - all possible scenarios. Returning the correct answer when the match is FOUND is excellent, but it is necessary to return the answer even if the match is NOT FOUND.

    Let's try again with another pair of lines:

    sourceString: "abcdyefg"
    searchString: "yes"

    Here, we started from the beginning of sourceString and read it to the end, looking at each three-character fragment to see if it matches the word “yes”. When we got to index 4, we found yef, which was almost a coincidence, but incomplete, as the third character was different. Thus, we continued to read until we reached the end of the line, and then decided that there was no match, so we returned -1.

    We created a series of steps (in programming this is called an algorithm) that we perform to solve the problem, and we tried to execute several scenarios, each time getting the correct result. At the moment, we can be sure that our algorithm works, and now it's time to formalize it, which will lead us to the next step.

    2. We write the algorithm in words


    This makes the steps real, which means we can refer to them later when writing the code.

    • Start at the beginning of the line.
    • We look through all three-character combinations (or how many characters there are indicated in searchString).
    • If any of them are equal to searchString, we return the current index.
    • If we get to the end of the line without finding a match, return -1.

    3. We write a pseudocode


    Pseudocode is not really a code, but it pretends to be a code. An example of what I'm talking about, given our algorithm: I can make it even more like real code as follows:

    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.



    for each index in sourceString,
    N = searchString.length
    POSSIBLE_MATCH = sourceString[index to index+N]
    if POSSIBLE_MATCH === searchString:
    return index
    return -1

    4. We translate everything we can into the code


    Now we have to take care of the syntax, function parameters and language rules. Maybe you cannot write everything, and that’s normal. Write in the code what you know for sure!

    function findFirstMatch (searchString, sourceString) {
    let length = searchString.length;
    for (let index = 0; index < sourceString.length; index++) {
        let possibleMatch = 
        if (possibleMatch === searchString) {
            return index;
        }
    }
    return -1;
}

    Note that I left part of this piece of code blank. This is intentional! I was not sure of the syntax for processing strings in JavaScript, but more on that later.

    5. Do not rely on luck


    A fairly common mistake, especially for novice programmers, is to use something found on the network with the hope that it will just work. The found fragment is simply inserted into your own project without testing. The more sections of your program you will not understand, the more unrealistic the successful completion of the work.

    The likelihood of an error doubles when you add any item you are not sure about. As a result, the process just gets out of hand.

    Comment: the probability of an error can be calculated using the Mersenne sequence: a (n) = (2 ^ n) - 1

    Test your code. Finding something online is cool, but before you add a snippet to your program, try this section separately from everything.

    In the previous step, I said that I did not know how to select a certain part of the string using JavaScript. Let's google it.

    https://www.google.com/search?q=how+to+select+part+of+a+string+in+javascript

    The first result is from w3schools. A bit outdated, but it will work:

    http://www.w3schools.com/jsref/jsref_substr.asp

    I assume that I should use substr (index, searchString.length) to highlight the sourceString part each time. But so far this is an assumption and nothing more. So I will check it first.

    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 know exactly how this function works. Therefore, when I add this fragment to my program, I will already know that if it does not work, the problem is not in the added section.

    And finally, I add the last part of the code.

    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;
}

    Conclusion


    If you have read to the end, try the tip. Find a problem that you cannot handle. I guarantee that everything will work out now.

    Good luck and happy coding!

    Skillbox recommends:

    Tags:

    Also popular now: