谷歌笔试题（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。

 

了解更多……

评论

13 楼 pkuoliver 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)

正解！！！

12 楼 mxswl 2010-09-28  

正解的确是 c(15,5) 嘻嘻

11 楼 yangguo 2010-09-28  

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）吧

世界上没有什么A（15，5）。

连招题应该是用 状态机 吧。

10 楼 love_ai87 2010-09-28  

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

9 楼 gorymt 2010-09-28  

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）吧

都是有编号的，所以那五本书只要按顺序（就不考虑顺序了）放进去就行了

8 楼 love_ai87 2010-09-28  

明明第7年就付清房款了

7 楼 easy_light 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)

应该是A（15，5）吧

6 楼 gorymt 2010-09-28  

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

5 楼 yangguo 2010-09-28  

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

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

|b1| b2| b3|

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

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

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

4 楼 melody3 2010-09-28  

生日快乐，Google

3 楼 yqlt 2010-09-28  

第一道题的答案是不是:19!/(19-5)!-18!/(18-5)!

2 楼 polaris1119 2010-09-28  

cesul 写道

有搞头。
想问下，BCC不能连出 A？还是BCA可以“跳着”连出A？

他给的例子就是这样的。

1 楼 cesul 2010-09-28  

有搞头。
想问下，BCC不能连出 A？还是BCA可以“跳着”连出A？