谷歌笔试题（Google十二岁生日晚）

2010-9-27日是Google十二岁生日，就在生日当天，Google进行了一场宣讲会加笔试。Google果然不一般，宣讲会门外都站满了人，也可见竞争之激烈，据说只需要40个人参加面试，而笔试的人有1000之多，汗……

polaris 也赶去凑凑热闹，完全是打酱油的，就是想见见Google的题目。下面polaris给大家分享一个题目吧。

这次笔试一共10道选择题，3道问答题。选择题不是很难，问答题对polaris来说就有点难了，因为polaris一直头疼算法，哎，只适合做应用了……好了，考试时特意记下几道题（有点难度的，对polaris来说），现在开始吧！

1、选择题

第一题：

书架上有编号为1-19的19本书，从中拿5本，问5本编号都不相邻的拿法有多少种？

呵呵，又是数学中的排列组合问题。学数学转计算机的人还是很有优势的。可惜polaris不是。这道题当年高三的时候说不定会做，现在……

第二题：
这道选择题讲到了买房，polaris的同学写了一篇文章。题目本身不难。您可以点击此处进去 看看。

2、问答题

问答题似乎题目都蛮长的。最后一道讲的是KOF哦。题目大概是：

玩过KOF（拳皇）的人都知道，玩的时候会连招是比较强的（polaris也玩过，不过不会连招，呵呵）。题目的大概意思是：每招用一个大写字母表 示，如ABC...Z，现给定n个连招公式：S→T，其中S长度为m，T的长度为1。在前m招的时候可以随便连，但m+1招后就必须遵循连招公式。现在要 写一个算法，计算最长连招的长度；如果可以无限连招，则返回def。1≤n,m≤100

给了一个例子：n=4，m=3，连招公式为：ABC→C，ABC→D，CCA→A，BCA→B(最后一个连招公式忘了，记在纸上落在住处了，晚上改 改，不过应该不影响理解)。连招公式的意思是：A、B、C可以连出C，也可连出D，C、C、A可以连出A，B、C、A、可以连出B。这时候可以得到最长连 招公式：ABC→C→A→A，即最长连招公式长度为6。

题目要求给出算法思想并结合一定的伪码。

最后，polaris祝Google生日快乐，不能进入Google，但一直在用Google的服务，喜欢Google。

 

了解更多……

评论

33 楼 lonelybug 2010-10-06  

连招公式可以用suffix tree计算出来

32 楼 leon_a 2010-10-05  

第二题，先转换成邻接矩阵的图表示。然后求图是否有反向边（DFS），如果有反向边，证明可以无限连，返回def
求最常连招这个就很简单了，找到矩阵中全0行，逆向递推。国庆假期回来我写具体算法

31 楼 EJLeo 2010-10-01  

第一道题弄懂了，但是第二道题连题目都没看懂

30 楼 chenjianjx 2010-09-30  

Google确实是聪明人才能去的地方。

29 楼 IcedCoffee 2010-09-29  

重脚+重拳+前轻拳+葵花2段+八稚女....

28 楼 homoclinic 2010-09-29  

luckytwo 写道

yangguo 写道

第一题：根据yangguo的复杂问题简单化方法论，转成，5本书取2本。

可以假设2本书已经取出来，桌上剩3本书,如图：

|b1| b2| b3|

现在要把取出的两本书重新插入带竖条的地方。所以是 C(4,2).

则m取n问题的通解是： C(m-n+1,n)

回到原问题，19取5 即为  C(15,5)

这个有点不明白

取出的2本，与桌上的3本是任意取的吗？

把2本书插入到间隔中，但怎样能保证编号都不会相邻呢？

例如：

已经取出 2,5

桌上： | 1 | 3 | 4 |

插入第2、4个间隔会有：1,2,3,4,5

这不就连续了吗

我觉着不是用数字来找组合，而是用组合来确定数字，即：先出现的是1-14个隔断，因此有15个位置，放入5个新的对象，然后对放入之后的新对象和隔断排序，重新成为1-19，这样既不相邻也可以遍历所有的情况。

27 楼 luckytwo 2010-09-29  

yangguo 写道

第一题：根据yangguo的复杂问题简单化方法论，转成，5本书取2本。

可以假设2本书已经取出来，桌上剩3本书,如图：

|b1| b2| b3|

现在要把取出的两本书重新插入带竖条的地方。所以是 C(4,2).

则m取n问题的通解是： C(m-n+1,n)

回到原问题，19取5 即为  C(15,5)

这个有点不明白

取出的2本，与桌上的3本是任意取的吗？

把2本书插入到间隔中，但怎样能保证编号都不会相邻呢？

例如：

已经取出 2,5

桌上： | 1 | 3 | 4 |

插入第2、4个间隔会有：1,2,3,4,5

这不就连续了吗

26 楼 luckytwo 2010-09-29  

xiyf2046 写道

第一题选择题

我的结果是：C(19,5) - 18*C(17,3)

思路：19中拿5本的拿法（不论编号是否连续） - 拿5本有相邻编号的拿法，剩下的就是不相邻的拿法数


19中拿5本的拿法 ： C(19,5)


拿5本有相邻编号的拿法：

5本书中有编号相邻，最少需要两本书的编号相邻。两本书编号相邻的取法有19 -1 = 18种（1:2,2:3,3:4...18:19）

19本已经拿走了2本剩下17本，17本中取3本的取法是：C(17,3)

根据乘法法则知,拿5本有相邻编号的拿法为：18*C(17,3)


所以题目的结果是：C(19,5) - 18*C(17,3)


1:2  3 4 5
3:4  1 2 5
？？？

晕有重复

好久没有去面试了，现在都考这个？

回去补下组合数学，定要把这个问题弄清楚。

25 楼 280511772 2010-09-29  

算法很菜。。数学全都忘记光了。用SQL解的

24 楼 polaris1119 2010-09-29  

280511772 写道

第一题是3003个吗

应该是的。

23 楼 polaris1119 2010-09-29  

xiyf2046 写道

第一题选择题

我的结果是：C(19,5) - 18*C(17,3)

思路：19中拿5本的拿法（不论编号是否连续） - 拿5本有相邻编号的拿法，剩下的就是不相邻的拿法数


19中拿5本的拿法 ： C(19,5)


拿5本有相邻编号的拿法：

5本书中有编号相邻，最少需要两本书的编号相邻。两本书编号相邻的取法有19 -1 = 18种（1:2,2:3,3:4...18:19）

19本已经拿走了2本剩下17本，17本中取3本的取法是：C(17,3)

根据乘法法则知,拿5本有相邻编号的拿法为：18*C(17,3)


所以题目的结果是：C(19,5) - 18*C(17,3)


1:2  3 4 5
3:4  1 2 5
？？？

怎么算了一下，C(19,5) - 18*C(17,3) 的结果是负数啊。

22 楼 shensuqiao 2010-09-29  

yangguo 写道

第一题：根据yangguo的复杂问题简单化方法论，转成，5本书取2本。

可以假设2本书已经取出来，桌上剩3本书,如图：

|b1| b2| b3|

现在要把取出的两本书重新插入带竖条的地方。所以是 C(4,2).

则m取n问题的通解是： C(m-n+1,n)

回到原问题，19取5 即为  C(15,5)

我咋觉得有点问题啊，“把取出的两本书重新插入带竖条的地方”，应该要排除掉相邻的情况吧

21 楼 xiyf2046 2010-09-29  

第一题选择题

我的结果是：C(19,5) - 18*C(17,3)

思路：19中拿5本的拿法（不论编号是否连续） - 拿5本有相邻编号的拿法，剩下的就是不相邻的拿法数


19中拿5本的拿法 ： C(19,5)


拿5本有相邻编号的拿法：

5本书中有编号相邻，最少需要两本书的编号相邻。两本书编号相邻的取法有19 -1 = 18种（1:2,2:3,3:4...18:19）

19本已经拿走了2本剩下17本，17本中取3本的取法是：C(17,3)

根据乘法法则知,拿5本有相邻编号的拿法为：18*C(17,3)


所以题目的结果是：C(19,5) - 18*C(17,3)


1:2  3 4 5
3:4  1 2 5
？？？

20 楼 sd252319571 2010-09-29  

easy_light 写道

yangguo 写道

第一题：根据yangguo的复杂问题简单化方法论，转成，5本书取2本。

可以假设2本书已经取出来，桌上剩3本书,如图：

|b1| b2| b3|

现在要把取出的两本书重新插入带竖条的地方。所以是 C(4,2).

则m取n问题的通解是： C(m-n+1,n)

回到原问题，19取5 即为  C(15,5)

应该是A（15，5）吧

那个复杂问题简化方法论 佩服。第一次见。鄙人无知。

19 楼 luckytwo 2010-09-29  

第一题选择题

我的结果是：C(19,5) - 18*C(17,3)

思路：19中拿5本的拿法（不论编号是否连续） - 拿5本有相邻编号的拿法，剩下的就是不相邻的拿法数


19中拿5本的拿法 ： C(19,5)


拿5本有相邻编号的拿法：

5本书中有编号相邻，最少需要两本书的编号相邻。两本书编号相邻的取法有19 -1 = 18种（1:2,2:3,3:4...18:19）

19本已经拿走了2本剩下17本，17本中取3本的取法是：C(17,3)

根据乘法法则知,拿5本有相邻编号的拿法为：18*C(17,3)


所以题目的结果是：C(19,5) - 18*C(17,3)

18 楼 280511772 2010-09-29  

第一题是3003个吗

17 楼 zhao103804 2010-09-29  

love_ai87 写道

double house = 160;
        double in = 40;
        for (int i = 1; i < 100; i++) {
            if (i == 1) {
                house = 160;
            } else {
                house = house * 1.1 - in;
            }
            System.out.println("第" + i + "年剩余房款："
                    + new DecimalFormat(".##").format(house) + "w");
        }

大错特错，你把房价减少了再乘以1.1有什么用，你这样相当于房价在降

16 楼 citybuster_one 2010-09-28  

相邻问题插空法，不错！

15 楼 polaris1119 2010-09-28  

yangguo 写道

第一题：根据yangguo的复杂问题简单化方法论，转成，5本书取2本。

可以假设2本书已经取出来，桌上剩3本书,如图：

|b1| b2| b3|

现在要把取出的两本书重新插入带竖条的地方。所以是 C(4,2).

则m取n问题的通解是： C(m-n+1,n)

回到原问题，19取5 即为  C(15,5)

yangguo厉害，想你学习！

14 楼 polaris1119 2010-09-28  

gorymt 写道

第一题 插空法
ps：广告真多。。

理解一下了，博客需要宣传嘛。谢谢了。