⬆️ ⬇️

How to solve typical problems programmer google

image



From the translator : we publish for you a translation of the article by Steve Merritt , a Google employee who talks about how he solves typical programming problems. The post will be useful, first of all, for novice programmers.



In this article I will talk about my strategy for solving problems arising 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 any level (colleagues, alumni bootcamps, university students). The 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 with large tech corporations. Three years ago, I got a job at Google thanks to her.



We remind: for all readers of "Habr" - a discount of 10,000 rubles when recording for any Skillbox course on the promotional code "Habr".



Skillbox recommends: Online Profession Java Developer Educational Course.


Step by step



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



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



1. Draw it



Getting started writing code is not a good idea. First you need to plan a way to solve the problem. Start by forming a hypothesis and proof of your point of view. And get to work only when you already have a clear plan. If you do not do this, then when the work has already begun, you may encounter the fact that separate code fragments will not match each other.



The solution can often be non-trivial, 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 know all this before the first line of code is written.



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



Apply the solution algorithm to the 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 data. If the function "passes a 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 the 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 counted it to the end, looking through 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 we decided that there is a coincidence, and it begins with index 4.



At the institute I had a teacher who set the task to come up with instructions for creating a peanut butter sandwich. For detailed and understandable instructions, we were promised a top grade.



I wrote the following:



“Open the peanut butter, spread it over the bread. Put another piece of bread on top and everything is ready. ”



I thought that I did it until the teacher took the butter and did not spread it on bread, which was still in plastic packaging.



Programs, like my teacher, require very detailed instructions to make the task possible. Therefore, when we create an algorithm, we are convinced that we have foreseen everything — all possible scenarios. Returning the correct answer when a match is FOUND is great, but it is necessary to return an answer also if a 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 through 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, because the third character was different. So we continued to read until we reached the end of the line, and then we decided that there was no coincidence, so we returned -1.



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



2. Write the algorithm in words



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





3. We write pseudocode



Pseudocode is not exactly code, but it "pretends" to be code. An example of what I'm talking about, taking into account our algorithm:



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 can make it even more like the real code like this:



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, the parameters of the functions and the rules of the language. Maybe you can't write everything, and that's fine. Write in the code that you know for sure!



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


Please note that I left part of this piece of code empty. This is intentional! I was not sure of the syntax for handling strings in javascript, but more on that later.



5. Do not rely on luck



A common mistake, especially among 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 parts of your program you do not understand, the more unrealistic the successful completion of the work.



The likelihood of an error doubles when adding any item that you are not sure about. As a result, the process just goes out of control.



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


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



In the previous step, I said that I don’t know how to select a specific part of a string using JavaScript. Let's look in google.



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



The first result is from w3schools. A bit out of date, but will work:



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



I suppose I should use substr (index, searchString.length) to select the sourceString part each time. But so far this is an assumption and nothing more. Therefore, I will first check it out.



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 feature works. So 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 to use the advice. Find a problem you can't handle. I guarantee that everything will work out now.



Good luck and happy coding!



Skillbox recommends:



Source: https://habr.com/ru/post/442048/



All Articles