谷歌Kick Start线上编程第一课

谷歌的校招活动已经开始了。如果对Google的校招途径不是很了解的话，大家可千万不要错过这个千载难逢的机会。一般来说，可以参与谷歌校招的途径有两种：一种是个人发送简历给谷歌校招邮箱；另外一种方式就是通过参加Google官方的Kick Start线上编程测试。有些朋友可能觉得线上编程测试会很难，而且参加的人会很多，获得面试的机会渺茫。其实此言差矣，相对于直接发送简历给谷歌校招邮箱，参加Kick Start线上测试可以算是非常高效且成功率更高的途径。并且，谷歌官方也是非常鼓励大家参加Kick Start线上编程测试。本文不对Kick Start和谷歌校招做过多的介绍了，有兴趣的朋友建议微信扫描文末二维码加老船长微信获得更多相关谷歌校招的内容。

谷歌Kick Start线上编程需要讲的内容非常多。关于Kick Start线上编程系列课程，计划将包括10篇文章以上，主要是介绍和讲解历年历届的Kick Start线上真题和解题思路，为大家排忧解惑。本文是整个系列的第一篇，希望对大家有所帮助。

Kick Start交互式问题

本篇文章将介绍Kick Start中的一个交互式问题。具体问题如下图：

上图为一道Kick Start交互式问题的实例。如图中所示，要求我们在A和B区间内猜一个数字，最多可以猜n次。每次猜完之后，系统会告诉我们猜测结果。是猜对了，还是猜大了或者猜小了。然后需要交互式地进一步的和系统进行猜测。看起来有点类似我们初学代码时都做过的“猜大小”游戏的自动化版本（“猜大小”游戏为代码随机生成一个数字，然后人输入猜测数字，系统回应我们猜测结果，然后人根据提示继续猜）。这是和往常我们遇到一些判题系统不同的一种模式，以往的判题系统多要求我们写一个函数留出接口，判题系统将不同的测试用例传入函数，判断输出是否与预期相同。而Kick Start线上编程在2019年加入了这种新的交互式问题，让比赛更加富有趣味性了一些。

此题会有T个测试用例，如果你猜对了，得到的回答为“CORRECT”，如果猜小了得到的回答是“TOO_SMALL”，如果猜大了得到的回答是“TOO_BIG”。由于和系统进行了交互，就要求我们在代码中对输入进行判定。

答题条件

在题目限制条件里我们可以看到对变量的一个约束范围。这道题里，约束了1<=T<=20,也就是有20个测试用例。A=0，即起始区间为0。N=30，即可猜30次。还有时间限制，要求在每个测试集内10秒跑完结果。对于存储的限制为1GB。

此外，也会明确地写出大数据和小数据的数据范围。如图所示，小数据的数据范围是30，大数据的数据范围是10^9。

注: Kick Start线上测试的每道题包含多个数据集（即测试用例集），一般是分为小数据集和大数据集两种。在比赛过程中，我们只能看到在小数据集上的运行结果。当比赛完成后我们才能知道自己的代码在大数据集上的运行结果。在比赛结束后，我们可以回到我们参加过的轮次，查看每一道题的得分，以及全球的得分的排名情况，还可以看到每道题的具体分析和答题思路。

数据集和得分

之前提到过，每道题包含多个数据集（即测试用例集），一般是分为小数据集和大数据集。在题目页面我们可以明确看到它在小数据集上和大数据集上的分值。比如这道题，在小数据集上的分值为5分，在大数据集上的分值为10分。

答题思路

这道猜大小的游戏，在小数据集的情况下，解题思路可以非常简单。我们发现小数据的数据范围是30，而题目中的猜测次数也为30次，也就是说，我遍历一次数组进行猜测其实是能通过小数据集的，也就是说能拿到5分。

然而，以上方法显然是通不过大数据集的测试的。如果想要拿到本题完整的15分的话，我们还需要有更加高效的方案。我们看大数据的范围是10^9，算一下用二分查找需要比较的次数为以2为底10^9的对数取floor后再加1，计算出来恰为30。那这道题就是可以用二分查找的方法来解的，下面给出代码示例：

public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int B = sc.nextInt();
            int count = 0;
            int l = 1;
            int r = B;
            while(l > 1;
                System.out.println(mid);
                count ++;
                String s = sc.nextLine();
                if(s.length() == 0){
                    s = sc.nextLine();
                }
                switch (s){
                    case "TOO_SMALL":
                        l = mid + 1;break;
                    case "TOO_BIG":
                        r = mid - 1;break;
                    case "CORRECT":
                        System.out.println("finished! " + count + " times");
                        flag = true;
                        break;
                }
                if(flag){
                    break;
                }
            }
        }
        sc.close();
    }

其实本题大体就是测试二分算法的，如果对二分法比较敏感的同学，看题以后应该可以立即想到的。这里可以讨论一个解题决策，就是在短时间内无法找到合适的对应大数据集的解题思路，那么就先把小数据集的5分拿下。

小建议

最后对于大家参加Kick Start线上测试给出以下5点建议：

• 建议大家登陆Kick Start线上测试的官网去熟悉此平台，实际地体验一下它究竟是怎样运作的。由于交互式题目的输入输出与我们平时遇到的题目有些出入，所以熟悉一下平台是很有必要的。
• 扎实数据结构和算法的知识，包括：栈、队列、线性表、背包。数据结构和算法书籍永远不需要收起来，每次都都会有新体会。
• 至少要熟悉一门编程语言。空谈误国，实干兴邦，一个程序员最差也要能用一门语言清晰地表达自己地解题思路。
• 需要提高测试技能，由于大数据集无法在比赛过程中得知结果，所以需要我们自己有捕捉缺陷、设计用例和边界值分析的能力。而个人认为，一个程序员若不具备基本的测试能力，是无法在实战中写出正确、健壮、易读、高效的代码的。
• 在往年题目上进行训练。毛爷爷说的好，“实践是检验真理的唯一标准！”。