[今天我们思考24]从张志强的阅微堂转载来的一堆题目

[pongba]

来源：http://zhiqiang.org/bbs/forum/1
整理如下。有很多面试题。没见过的可以试试。想出来的请说说你的思维过程:)

1. 比如输入字符串"abcda"，输出b。
微软面试题

2. 给链表某节点指针，如何删除此节点？
百度面试题

3. 给一个数n和一个二分搜索树，打印树上所有其和等于n的路径。路径不需要从根节点开始。
Yahoo面试题

4. 有n个人，其中超过半数是好人，剩下的是坏人
好人只说真话，坏人可能说真话也可能说假话
这n个人互相都知道对方是好人还是坏人

现在要你从这n个人当中找出一个好人来，只能通过以下方式：
每次挑出两个人，让这两个人互相说出对方的身份，
你根具两个人的话进行判断。

问通过何种方法才能最快的找出所有人的身份(最坏的情况下)

5. 有一个矩阵，每个元素是一个数，要求，从左上角出发到达右下角，每次只能向右或向下，要求全路线经过的元

素和最小，求出路径及这个和的值。要求分别用递归和非递归方法实现之。
微软面试题

6. 设矩阵为A[m][n]现从A[0][0]进，从A[m-1][0]出，要求经历所有矩阵中的点，且不重复访问任何点，问总共有多

少种路径？给出算法思想，最好有程序实现！！

7. There is a circular track. There are n gas stations of capacity ci. To go from one station to the next

station it takes certain amount of gas gi. For any station the gas available may not be enough to get to

the next station. Write a linear time algorithm to find the correct station in which we must start in order to

complete one round around the track.

8. 1): How to find a second largest number within an array without using any loop 2):How to find a

missing element in an array in the most optimised way.

9. 很多情况下,判定不一定要比求解容易,但是对于一个n位二进制整数,请问有无判断它是否为平方数的O(n)算法(仅

用到二进制加,减和移位)?

10.  1). Given 2D Matrix of characters; find whether a word is there in this array. It can start at any position

and can be present horizontally, vertically and diogonally both in forward and reverse order.

2). Whats the most efficient datastructure to represent a dictionary and its operations like add, probe.

3). Extending the question above..Given a string "str" and a dictionary, one can substitute one character

in the string at a time to get another string; this string should be a part of the dictionary. Start from the

source string and reach the destination string "str1" in minimum number of steps.

11. 怎么在同一个数组里面实现３个stack，并且最有效率？
微软面试题

12. 你有10亿张网页地址, 如何检查它们之中的重复网页?
Yahoo面试题

13. 算法题一：Given 1 GB memory, input a file which contians 4 billion integers,
output one integer that is not in the file. What if you have only 10 MB
memory?

算法题二：There are 100 hundred sorted arrays, and each of them contains 100
numbers. Give an algorithm to merge them into a single sorted array, using
only one temporary array in the middle steps.

编程题：Input an integer array of size n and an integer k (k<=n), output all
subsets of size k.

Google电面

14. 数组中元素有正有负，如何求元素和最接近于0的子数组

15. 找缺失的数：An array A[1...n] contains all the integers from 0 to n except one. In this problem, we

cannot access an entire integer in A with a single operation. The elements of A are represented in binary,

and the only operation we can use to access them is "fetch the jth bit of A[i]", which takes constant time.

Find the missing integer in O(n) time.

16. Given two arrays A [1..n] and B[1..m], find the smallest window in A that contains all elements of B.

That is, find a pair <l,k> such that A[l..k] contains B[1..m] For example, given A = 3,1,5,7,3,5,2 and B = 5,3

then the smallest window is [3,5].
Amazon面试题

17. 一个n*n的矩阵数列，若此序列每一列都是增序的，求这n^2个数的中位数。

18. 给一个数组，将它们分为两部分，平均值相等。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[windstorm]

第一题什么意思？

第二题只有指针地址没有其他信息？如果有next，那么把point->next的所有项复制到point下，然后让point->next =
point->next->next，等于把下一节点移到这里来。

第四题，我们比如随机挑选两个人出来，让他们说对方身份，这时有这几种情况

1 都说对方是好人：此时两人可能都是好人可能都是坏人
2 都说对方是坏人：两人都是坏人
3 一个说对方是好人，一个说对方是坏人：肯定是一个好人，一个坏人

这样发现，1，2判断出来的人是一个属性，不管好坏，3则是相反属性

好，现在假设分两个组，1组表示好，0组表示坏，开始随机配对。只要属于2的，先都扔到0组去。

然后，我们随机挑一个人（用a表示）出来，问剩下所有的人，他是好人还是坏人？此时有两种情况

1 如果"好人"的答案超过半数，那么此人归类为1组，所有说他是"坏人"的人归类为0组。
2 如果"好人"的答案没有超过半数"，那么此人归类为0组，所有说他是"好人"的人归类为0组。

最后一定能找出所有好人。

最坏情况是坏人都说实话，这样算法貌似比较复杂，是n平方的复杂度。

晚上要出行，目前只能想到这里，期待更好的答案。

顺便给pongba提一个意见，一次最好不要太多题，首先答案不集中，其次让人丧失想的欲望......也许是个人感觉吧，比如20道题，分四次，5道5道出比较好。

2008/5/27 pongba <pon...@gmail.com>:

--
Yours Sincerely

Kun

[pongba]

2008/5/27 windstorm <likunar...@gmail.com>:

第一题什么意思？

忘记抄标题了，输出第一个只出现一次的字母。

本来打算分几次的，想想还是算了，都是从那里摘抄过来的，干脆集中在一个帖子里了。而且我也没有做过，所以无从挑选啊:)

[Concrete Vitamin]

5. 有一个矩阵，每个元素是一个数，要求，从左上角出发到达右下角

，每次只能向右或向下，要求全路线经过的元

素和最小，求出路径及这个和的值。要求分别用递归和非递归方法实现之。
微软面试题

递归方法:
记忆化搜索
非递归方法:
DP

2008/5/27 pongba <pon...@gmail.com>:

[翁翊成]

第四题的分析有些问题：）
1.都说对方是好人：此时两人都是好人或者都是坏人人。
2.都说对方是坏人：两人不可能全为好人，即至少有一人为坏人。
3.一个人说对方是好人，一个人说对方是坏人：两人不可能全为好人，即至少有一人为坏人（被说为坏人的那个肯定为坏人）。

刚刚自己按照这个思路大概写了个算法，粗略估计了下，时间复杂度应该小于n平方。
gmail怎么贴code格式比较好看。。。哪位兄弟告诉下，我把CODE贴上来大家给评价一下。

2008/5/27 windstorm <likunar...@gmail.com>:

[windstorm]

哦，这个意思阿

第一题，我的想法是用hash做，表中顺着下来第一个只出现一次的就是题目所要求的，貌似这样不算复杂吧。

2008/5/27 pongba <pon...@gmail.com>:

--
Yours Sincerely

Kun

[alai]

可以用 realfun 前段时间推介的代码发芽网 www.fayaa.com/code 嘛

2008/5/28 翁翊成 <wen...@gmail.com>:

[windstorm]

哦，对，第三种情况是有问题，呵呵。不过不影响后面的分析:)

代码在gmail里面不好发，发到发芽网上去吧。

2008/5/28 翁翊成 <wen...@gmail.com>:

--
Yours Sincerely

Kun

[翁翊成]

http://www.fayaa.com/code/view/43/
发上去了:)
这个发芽还真是个很棒的idea.
我最近再重温数据结构和算法方面的东西，看来回头写的测试程序都丢上去显臭+浪费他的空间好了:-P

2008/5/28 windstorm <likunar...@gmail.com>:

[翁翊成]

这个是最后一次思考写下的。
之前按照一般思路的一个改进大概是这样：
首先找到第一个好人，
然后让这个好人指出剩下的人。

2008/5/28 翁翊成 <wen...@gmail.com>:

[啊拉飞仔]

第四题:

找一个人出来,让其他人说他是好人还是坏人.

A.如果挑出来的是好人,
1.如果剩下的还是好人多,那么得出的结论中一定是好人的结果多.之后断定他是好人,让这个人说其他人的身份即可.
2.如果刚好剩下的好人和坏人一般多,而且坏人都说真话(既总体上好人比坏人多一个,且坏人都说真话的时候)...那么换一个出来吧....

B.如果挑出来的是坏人,
那么得出的结论一定是说他是坏人的多,确定他是坏人,排除出比较队列即可.

重复以上步骤,只到找到好人...

[啊拉飞仔]

2.如果刚好剩下的好人和坏人一般多,而且坏人都说假话(既总体上好人比坏人多一个,且坏人都说假话的时候)...那么换一个出来吧....

...上面写错了...

On 5月28日, 下午5时44分, 啊拉飞仔 <jjymhkx0...@gmail.com> wrote:
> 第四题:
>
> 找一个人出来,让其他人说他是好人还是坏人.
>
> A.如果挑出来的是好人,
> 1.如果剩下的还是好人多,那么得出的结论中一定是好人的结果多.之后断定他是好人,让这个人说其他人的身份即可.
> 2.如果刚好剩下的好人和坏人一般多,而且坏人都说假话(既总体上好人比坏人多一个,且坏人都说真话的时候)...那么换一个出来吧....

> > TopLanguagehttp://groups.google.com/group/pongba- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[windstorm]

啊拉飞仔的第一种情况不应该在考虑范围之列吧，因为题目说了是最坏情况下，第一种情况太过于理想了。

2008/5/28 啊拉飞仔 <jjymh...@gmail.com>:

--
Yours Sincerely

Kun

[翁翊成]

最坏情况确实比较难分析出来.
不过个人感觉,这道题是带着逻辑分析一起考察的.

2008/5/28 windstorm <likunar...@gmail.com>:

[啊拉飞仔]

2.如果刚好剩下的好人和坏人一般多,而且坏人都说真话(既总体上好人比坏人多一个,且坏人都说真话的时候)...那么换一个出来吧....

其实不用换的,如果得到好人和坏人一样多,那么可以得到挑出的一定是好人,因为如果挑出的是坏人,那么一定不会出现说好人和说坏人数量一样多的情况.

所以可以得出:


A.如果挑出来的是好人,
1.如果剩下的还是好人多,那么得出的结论中一定是好人的结果多.之后断定他是好人,让这个人说其他人的身份即可.
2.如果刚好剩下的好人和坏人一般多,而且坏人都说假话,这样得到的说是好人的数量和说坏人的数量相等,那么也可以断定挑出的是好人,因为如果
是挑出坏人的情况下,说是坏人的数量一定比说是好人的数量多,不可能相等.


B.如果挑出来的是坏人,
那么得出的结论一定是说他是坏人的多,确定他是坏人,排除出比较队列即可.


重复以上步骤,最坏情况下,所有的坏人都排除后,再随便找一个既是好人...

On 5月28日, 下午8时20分, windstorm <likunarmstr...@gmail.com> wrote:
> 啊拉飞仔的第一种情况不应该在考虑范围之列吧，因为题目说了是最坏情况下，第一种情况太过于理想了。
>

> 2008/5/28 啊拉飞仔 <jjymhkx0...@gmail.com>:

> >> > TopLanguagehttp://groups.google.com/group/pongba-隐藏被引用文字 -

>
> >> - 显示引用的文字 -
>
> --
> Yours Sincerely
>

> Kun- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[翁翊成]

完全没看懂你的意思...

2008/5/29 啊拉飞仔 <jjymh...@gmail.com>:

[郑海涛]

用一个map, 然后顺序遍历该字符串，添加元素到map中，最后只要取得map中第一个value为1的key 的值，有点麻烦，但很实用

在08-5-28，windstorm <likunar...@gmail.com> 写道：

[翁翊成]

问题的前提是，我们根本不知道谁是好人，不能直接去拿value，而是要通过其他的人嘴来说谁是好人.

2008/5/29 郑海涛 <zht...@gmail.com>:

[翁翊成]

这个还是用hash实用些.

2008/5/29 郑海涛 <zht...@gmail.com>:

[啊拉飞仔]

设所有的好人为序列A1，A2，A3。。。。。An，所有的坏人为序列B1，B2，B3。。。。Bn，由题意知道 n>m 。

从A1，A2，A3。。。An，B1，B2。。。Bm中，随机选取一个人X，之后让剩下的所有人都和X互相指认，统计其他人评论X的结果：

如选择的X是一个坏人，那么剩余的人中好人比坏人多，即使所有的坏人都说谎话，得出的结果中，也是"他是坏人"的结果占多数，所以得到结果中"他是坏
人"占多数的情况下，这个X是坏人，且所有说他是好人的也是坏人，可以排除出比较对列；

如果选择的X是一个好人，那么结果中"他是好人"的数量 >= "他是坏人"的数量，因为
{
如果剩余的人中好人还是比坏人多（即 n-1 > m），那么会得到"他是好人"的结果多，于是断定这个人是好人；
如果剩余的人中好人和坏人一般多（n-1 = m），且所有坏人都说X是坏人，那么也可以断定X是好人，因为如果X是坏人的话，那么得出的结论中
坏人一定占多数，不可能相等。
}
这样直接可以得到X是好人结论。

遇到坏人的情况，把可以确定的坏人都排除，剩下的人重新进行上面的过程既可。


最坏的情况是，每次挑出来的都是坏人，而且剩下的坏人都说真话，这样的话，我们每次只能断定挑出来的X是坏人，但是无法知道剩下的那个是坏蛋，这种情况
下，只有挑到一个好人，即挑出所有的坏人后才能找到一个好人。根据题意，最坏的情况就是好人比坏人多一，即 n-1 = m 的时候，这种情况下要挑
出将近一半的人才能找到





On 5月29日, 上午1时03分, "翁翊成" <weng...@gmail.com> wrote:
> 完全没看懂你的意思...
>
> 2008/5/29 啊拉飞仔 <jjymhkx0...@gmail.com>:

> > > >> > TopLanguagehttp://groups.google.com/group/pongba-隐藏被引用文字<http://groups.google.com/group/pongba-%E9%9A%90%E8%97%8F%E8%A2%AB%E5%...>-

>
> > > >> - 显示引用的文字 -
>
> > > --
> > > Yours Sincerely
>
> > > Kun- 隐藏被引用文字 -
>

> > > - 显示引用的文字 -- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[翁翊成]

这种情况的复杂度 n^2/2 +n

2008/5/29 啊拉飞仔 <jjymh...@gmail.com>:

[windstorm]

8(1):不用loop，难道用递归？

定义两个变量，large1和large2，然后

Process( array,i )
{

if(array[i]>large1)
{
large2 = large1;
large1 = array[i];
}
else if(array[i]>large2){
large2 = array[i];
}
Process( array, ++i )

}

想得比较简单，不过这道题怎么说也要遍历一遍吧。.

8(2) 没理解这个missing，难道这个array里面的数是递增或者递减的？必然是有规律的吧？

2008/5/29 翁翊成 <wen...@gmail.com>:

--
Yours Sincerely

Kun

[Justin L]

好人坏人这个题，我的思路是这样的。
首先我理解题目是这个意思：好人说真话。坏人可能说真话，可能说假话。
然后题目还有个重要条件，就是好人比坏人多。

那么随机调一个人出来，让他被其他人评价。如果这个人被人说是好人，则加一分，被人说坏人，则减一分。
由于好人比坏人多，那么肯定这个人的得分肯定会偏向于他是好人（得正分或0分）还是坏人（得负分）。

下面是题外话：
这个思路，现实中有一个概括，叫做：群众的眼睛是雪亮的（这里潜台词是：群众中还是好人占大多数啊）。


下面的最坏情况的分析，我还没拿定主意：
现在我们就是怕不断的挑出坏人来：每次都挑出坏人来，则至少需要把坏人挑完，才能挑到好人。

[啊拉飞仔]

8(1)的问题，如果保存最大值和次大值的话，那么最坏的情况下，比较的次数是2N次。

我的看法是先通过锦标赛算法找到最大值，之后找到和最大值比较过的所有数字，从中找到次大。

这种方法的比较次数是 N+log(N) 次。

On 5月29日, 上午10时37分, windstorm <likunarmstr...@gmail.com> wrote:
> 8(1):不用loop，难道用递归？
>
> 定义两个变量，large1和large2，然后
>
> Process( array,i )
> {
>
> if(array[i]>large1)
> {
> large2 = large1;
> large1 = array[i];}
>
> else if(array[i]>large2){
> large2 = array[i];}
>
> Process( array, ++i )
>
> }
>
> 想得比较简单，不过这道题怎么说也要遍历一遍吧。.
>
> 8(2) 没理解这个missing，难道这个array里面的数是递增或者递减的？必然是有规律的吧？
>

> 2008/5/29 翁翊成 <weng...@gmail.com>:
>
>
>
> > 这种情况的复杂度 n^2/2 +n
>
> > 2008/5/29 啊拉飞仔 <jjymhkx0...@gmail.com>:

> ...
>
> 阅读更多 >>- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[nextRainbow]

感觉你说的第四题好像不完善
如果 随机挑选出两个人了，让他们说对方的身份，

类型1，都是对方是好人，则两个人可能都是好人，也可能都是坏人，
类型2，都说对方是坏人，情况一：两个人可能一个是好人，一个是坏人。情况二，都是坏人。
类型3，一个说对方是好人，一个说对方是坏人，情况一，一个是好人，一个是坏人。情况二，都是坏人。

现在随机找出两个人，如果是类型2，或者类型3，直接踢回人群。
如果是 类型1，把他们先 扣留，编号a,b。 直到再次找到类型1的情况,编号c,d。让a与c指认身份，得到结果1，让b和d指认身份，得到结果
2.
情况分析如下：
都是好人 结果1=结果2= 类型1
都是坏人 结果1=结果2=类型1 类型2，类型3，类型1. 中的任意一个
两个好人，两个坏人。 结果1和结果2 为类型2或类型3中的一种

好难，进行不下去，回头再 分析，吃饭去了

[pongba]

有人搞定16题吗？复杂度多少？

2008/5/27 pongba <pon...@gmail.com>:

[windstorm]

应该就是O(n)吧，我没仔细想，感觉用KMP算法就能搞定吧。

2008/5/31 pongba <pon...@gmail.com>:

--
Yours Sincerely
Kun

blog: www.forwind.cn

[pongba]

2008/5/31 windstorm <likunar...@gmail.com>:

应该就是O(n)吧，我没仔细想，感觉用KMP算法就能搞定吧。

似乎O(N)做不到。
和KMP有点关系，但似乎很难借鉴KMP的做法。
完整的说一下你的思路？:

[Justin L]

一共也就是26个字母，一个萝卜一个坑对号入座罢。

On 5月28日, 下午4时11分, windstorm <likunarmstr...@gmail.com> wrote:
> 哦，这个意思阿
>
> 第一题，我的想法是用hash做，表中顺着下来第一个只出现一次的就是题目所要求的，貌似这样不算复杂吧。
>
> 2008/5/27 pongba <pon...@gmail.com>:
>
>
>
>
>

> > 2008/5/27 windstorm <likunarmstr...@gmail.com>:

[windstorm]

......看错题了。如果元素位置不定，貌似不能直接用kmp.......

我想了一下，能不能这样，首先计算B中元素的和，假设是sumB，然后找a中和它元素和相等的，同样长度的序列（这个顺序浏览一次就可以了），中途只要找到，就匹配两者。

关于这个匹配A[flag+1，count]和B[1..m]，我想的是把里面所有元素相乘，比较乘积，a1+a2+a3+...an =
a1xa2xa3x...an 的数很少，可以算特例单独排除

貌似这样算法是不是O(nm)?

2008/5/31 pongba <pon...@gmail.com>:

--

[pongba]

2008/5/31 windstorm <likunar...@gmail.com>:

......看错题了。如果元素位置不定，貌似不能直接用kmp.......

我想了一下，能不能这样，首先计算B中元素的和，假设是sumB，然后找a中和它元素和相等的，同样长度的序列（这个顺序浏览一次就可以了），中途只要找到，就匹配两者。

关于这个匹配A[flag+1，count]和B[1..m]，我想的是把里面所有元素相乘，比较乘积，a1+a2+a3+...an =
a1xa2xa3x...an 的数很少，可以算特例单独排除

貌似这样算法是不是O(nm)?

相加手法的本质是什么？

我也说说我自己的一个朴素解法，但优化起来似乎有点困难：

1. 首先是一个简单的观察：任何一个最小window，A[l,k]，其A[l] = B[1]，且A[k] = B[m]。于是，我们只需要考虑A[1..n]中所有等于B[1]的元素，因为最小window只能以它们开头。
2. 对于一个给定的A[r] = B[1]。从r开始往后寻找第一个匹配B[2]的元素，再接着寻找第一个能够匹配B[3]的元素.. 直到找到一个A[s] = B[m]。可以容易的证明A[r,s]是以r开头的window中最小的。
3. 对于所有使A[r] = B[1]的r，做第二步。

优化希望在于，第二步里面有些信息是可以留作后面用的。

[windstorm]

为什么A[l] = B[1]，且A[k] = B[m]？题目说的是

That is, find a pair <l,k> such that A[l..k] contains B[1..m] For
example, given A = 3,1,5,7,3,5,2 and B = 5,3

很明显这里A[l] = B[M]吧？如果你先找A[1..n]中所有等于B[1]的元素，那按原题的条件，就解不出 B = 5,3 的序列了。

我的理解是在A中找一个序列，序列中的元素和B中元素完全一样，但是顺序不一定一样

话说要是顺序一样，那不就是KMP？

2008/5/31 pongba <pon...@gmail.com>:

--

[pongba]

2008/5/31 windstorm <likunar...@gmail.com>:

为什么A[l] = B[1]，且A[k] = B[m]？题目说的是

That is, find a pair <l,k> such that A[l..k] contains B[1..m] For
example, given A = 3,1,5,7,3,5,2 and B = 5,3

很明显这里A[l] = B[M]吧？如果你先找A[1..n]中所有等于B[1]的元素，那按原题的条件，就解不出 B = 5,3 的序列了。

l = 3
k = 5

A[l] = A[3] = 5
A[k] = A[5] = 3

B[1] = 5
B[M] = 3

你好像把l当成A[l]了.
<l, k>是下标.

[windstorm]

Oh, sorry, 我理解成在A中找一个序列，序列中的元素和B中元素完全一样，但是顺序不一定一样了，粗心了-_-!!

2008/6/1 pongba <pon...@gmail.com>:

--

[silwile]

提醒一下，第7题是个很不错的题目。

2008/5/27 pongba <pon...@gmail.com>:

That is, find a pair <l,k> such that A[l..k] contains B[1..m] For example, given A = 3,1,5,7,3,5,2 and B = 5,3

then the smallest window is [3,5].
Amazon面试题

17. 一个n*n的矩阵数列，若此序列每一列都是增序的，求这n^2个数的中位数。

18. 给一个数组，将它们分为两部分，平均值相等。