Google工程师解决编程问题的方法 [译]

本文是Google工程师 Steve Merritt 介绍他日常工作、学习过程中解决编程问题的思路和方法。

原文地址:https://blog.usejournal.com/how-a-googler-solves-coding-problems-ec5d59e73ec5

在本文中,我将向你介绍我在Google日常工作时解决编程问题的策略,这个策略也同时帮助各个级别的程序员(新手、大学生和实习生)学习和成长。通过这个策略,可以减少令人沮丧的调试,并在较短时间内写出更干净、正确的代码。

策略步骤

我将用一个编程问题的例子,来一步一步解释我解决问题的策略。

问题:

有两个字符串:sourceString 和 searchString,返回searchString在sourceString中的第一个位置。如果sourceString不包含searchString,则返回 -1。

第一步:画出来

上来就写代码,是愚蠢和懒惰的方法。

我们平时在开始写作之前,首先要弄清楚论点和论据,并保证论点和论据是有意义的。如果没有这么做的话,你会发现写的文章不顺畅、前言不搭后语,就会浪费时间重头再来一遍。

编程亦是如此,而且会更糟糕。就像,眼睛里弄进了洗发水一样糟糕。

大多数情况,即使问题乍一看很简单,问题的解决方法仍然十分重要。在写代码之前,先在纸上理出方案并验证方案在各种情况下是否正确。

别着急去写任何代码,甚至都不要去想写代码的事,因为你后面会有足够的时间去写代码的那些字符和符号。开始的时候,你仅仅需要像人类正常思考一样,去思考如何解决问题即可。

画一些图表、箭头、方框等,把数字、字符放到图表里面,任何可以帮助你直观分析问题的图表都可以使用。可以任意发挥你的想象,不受键盘、代码的限制,目的是解决问题。

我们可以先虚构一些简单的输入,比如:

  1. ”abc” 作为searchString,
  2. ”1234abcdyesefgh” 作为sourceString,

理出正确的结果应该是什么。然后,回味一下你是怎么理出这个结果的,思考的过程有哪些。

我的思考过程:

我可以一眼看出searchString “abc“在sourceString “1234abcdyesefgh“里。我的脑袋里具体的过程是怎么样的呢?首先从sourceString开始一直扫到结尾,看每个连续的三个字符是不是和”abc”相匹配。比如: “123“, “234“, “34a“, “4ab“, “abc“, …。当到第五个的时候,发现匹配!因此得出结果,searchString在sourceString里,并且在第五个位置。

当我们在写下我们的算法时,我们同时也要确保我们考虑到所有可能的场景。不仅在字符串匹配时返回正确的结果,也要在不匹配时返回正确的结果(如本例是:-1)。

让我们尝试以下场景:

  1. ”yes” 作为searchString,
  2. ”abcdyefg” 作为sourceString,

这里,我们从sourceString的开头一直寻找到结尾,看看每三个连续字符是否和searchString匹配。当我们寻找到五个位置时,找到”yef”,但差一个字符才完全匹配searchString “yes”;因此我们继续往下找,知道sourceString结束;最终我们没能找到相匹配的子串,所以最终结果返回 -1。

以上的思考过程,在编程术语中便是 算法。通过以上的思考过程,我们不仅考虑匹配到的场景,而且考虑了没有子串匹配的场景;因此,我们有信心我们的算法是工作的,这个时候我们可以继续下一步:把我们的算法形式化下来。

第二步:用自然语言写下来

这一步,我们思考我在第一步总结的算法思路,并尝试用自然语言(英文或中文)写下来。这样可以使算法步骤更精炼一点,方便我们在写具体代码的时候回过头来参考。

  1. 从sourceString字符串的最开始字符查找;
  2. 查找每三个字符(这个决定于 searchString的长度);
  3. 如果查找的子串(每三个字符),则返回当前的位置;
  4. 如果到sourceString结束,都没有匹配的子串,则返回 -1。

看起来,很不错哦!

第三步:用伪代码写下来

伪代码不是真正的代码,伪代码是模拟代码的结构。下面是我对上面的算法写的伪代码:

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

伪代码更靠近实际的代码,取决于你自己(比如你工作用的编程语言);伪代码越靠近实际的代码,后面写代码的时候就会越方便。

第四步:翻译为真正代码

备注:对于简单的问题,这一步可以并到上一步。

到这一步,我们才开始真正的关系代码语法,方法的参数已经编程语言的各种规则。

或许你不能一下子写出所有的代码,没有关系!写下你能写的代码。

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

注意,我故意留下了一行没有写的代码<the LENGTH chars starting at index i>。因为我不确定在Javascript里如何获取字符串子串,所以我会在下一步骤里解决这个问题。

第五步:不要猜,不要YY

我发现新手程序员经常容易犯一个错误:在互联网上搜一些代码片段,心想 “这个应该可以工作”,然后就把不理解的代码、不做测试的代码放到程序里了。程序里放入越多你不理解的代码,你就越不会找到正确的解决方法。

程序里的错误是你不确定代码的两倍或数倍之多。如果只有一处不确定的代码,罪魁祸首可能就是这一块。但如果有更多不确定、不理解的代码?两处,三处,四处,造成的错误可能就有七八处,渐渐的程序就不可控了。

备注:程序错误和不确定代码的公式(梅森序列:):a(n) = (2^n) – 1

首先要测试你的代码。在互联网上查询一些方案是很好的,但是在放入你的程序之前,最好先在小范围、特定空间下测试你所查到的代码是按照你的期望工作的。

在上一步中,我不确定Javascript里是如何获取字符串的子串,所以我就先google了一下 ”how to select part of a string in javascript“。第一个找到的结果是w3schools的 (https://www.w3schools.com/jsref/jsref_substr.asp),有点过时,但通常还是可靠的。

根据查到的结果,我推断可以使用:

substr(index, searchString.length)

来每次获取sourceString里的一部分。但这只是我的推断。因此,我首先要创建一段小程序来验证我的推断,即验证这个方法是否真的和我想的一样能工作:

>> 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"

现在,我很确定这个方法的行为。因此我很放心的在我上面的程序里使用这个方法。我最终的代码如下:

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

结论

如果你都读到这里了,我想说的是:”还等什么,撸起袖子尝试一下吧!”。按照上面的策略,再回去看下那个令你苦恼的问题吧,我可以保证你会有所改善的。

祝你好运!开始愉快的编程吧!

发表评论

您的电子邮箱地址不会被公开。