[今天我们思考17]两道google面试题

[pongba]

有点火星，但肯定有人没做过的:-) ... 比如我...

1. 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。

2. 给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*…*A[n]/A[i]。你不能使用除法运算。

在matrix67的blog上看到的，上面还有很多题目。

当时两个题目都没有想出来，主要是没有思路。想来是知识性的储备不够，比如第一道题目，完全联想不起任何有关的知识和题目。而题目的简洁也导致了辅助探索手法完全没用。有时，知识的有无的确是决定作用的。

第二个题目很有意思，当时没有想到。但后来在《编程之美》上看到收录了，不过改成这样一个问法：

2'. 给定一个数组A[1..n]，求出任意n-1个数的乘积中最大的一个。（不允许使用除法）

这下想出来了。比较了一下为什么原来那个想不出来，现在这个想出来了，得到了一些很有意义的启发。

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

[pongba]

添加一道微软的:-)

3. 给出两个单链表，判断它们是否从某个节点开始就合二为一了。

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

[NjuBee]

matrix67的blog 所有帖子我都看完了的说

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

[sanachilleus]

第三题最直接的想法是找到两个链表的结尾，比较是否相等。这样的复杂度是O(M+N)，M和N分别是两个链表的长度。
我觉得很难找到小于O(M+N)的算法，因为链表有可能在最后一位才合二为一。

On 5月8日, 下午8时32分, NjuBee <eag0...@gmail.com> wrote:
> matrix67的blog 所有帖子我都看完了的说
>
> 2008/5/8 pongba <pon...@gmail.com>:
>
>
>
> > 添加一道微软的:-)
>
> > 3. 给出两个单链表，判断它们是否从某个节点开始就合二为一了。
>
> > 2008/5/8 pongba <pon...@gmail.com>:
>
> >> 有点火星，但肯定有人没做过的:-) ... 比如我...
>
> >> 1.

> >> 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有-k个，且它们是完全随机的（出现概率均等）。
>
> >> 2.
> >> 给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用-除法运算。
>
> >> 在matrix67的blog上看到的，上面还有很多题目。
>
> >> 当时两个题目都没有想出来，主要是没有思路。想来是知识性的储备不够，比如第一道题目，完全联想不起任何有关的知识和题目。而题目的简洁也导致了辅助探索手法完-全没用。有时，知识的有无的确是决定作用的。

>
> >> 第二个题目很有意思，当时没有想到。但后来在《编程之美》上看到收录了，不过改成这样一个问法：
>
> >> 2'. 给定一个数组A[1..n]，求出任意n-1个数的乘积中最大的一个。（不允许使用除法）
>
> >> 这下想出来了。比较了一下为什么原来那个想不出来，现在这个想出来了，得到了一些很有意义的启发。
>
> > --
> > 刘未鹏(pongba)|C++的罗浮宫
> >http://blog.csdn.net/pongba
> > TopLanguage

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

[silwile]

喜欢第1题。可以先做k=1的时候。再做k可能会简单一些。

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

[windstorm]

第二题应该是

Bi = （A1 × A2 ×......× Ai-1 ） × （ Ai+1 ×......×AN）

分成两部分

前面这个好算，扫一遍数组就能算出来，构建一个乘积数组。

后面这个同理，只不过倒序扫一遍数组A，构建另外一个乘积数组。这个数组的第0项是An×.....×A2×A1， 第一项是An×......A2，以此类推。

扫两边数组A即能得出答案。

[hayate]

cool!
我居然想到对数上面去了

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

[windstorm]

第一题没明白，出现概率均等怎么理解？

[hayate]

均等是指n个元素取k个的组合数为概率空间，每种组合出现的几率一样

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

[pongba]

2008/5/8 sanachilleus <sanach...@gmail.com>:

第三题最直接的想法是找到两个链表的结尾，比较是否相等。这样的复杂度是O(M+N)，M和N分别是两个链表的长度。
我觉得很难找到小于O(M+N)的算法，因为链表有可能在最后一位才合二为一。

思路？难道是"直接"就想到比较最后一个了？

我思路是这样：

1. 抽象：相当于两个数组，判断是否从某个元素开始后面就都一样了。（实际上，这个抽象减少了条件）
2. 从前往后的话不知道从哪个地方开始对齐，但可以从后往前，总是对齐的。
3. 既然要从后往前挨个考察，那就需要把链表逆一下。
4. 发现，只要逆一下之后，就会导致从第一个链表头能够走到第二个链表头。

然后过了一会儿，发现，最后两步不是必须的，只要直接比较最后一个节点就够了。。。

这个思路基本没有什么价值。

[hayate]

汗 也意识到了... 如果只是要问是否的话

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

[NjuBee]

链表1前进到1步
2 2
1 4
2 8
....................

步数 M+N or min(M+N, 4 * max(Mx, Nx)) if 合并在Mx,Nx

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

[lbaby]

1，我想出了一个办法：
从头遍历，然后计数，对 n 属于 1-N ，取 random/n % k 存入 结果中

On May 8, 7:06 pm, pongba <pon...@gmail.com> wrote:
> 有点火星，但肯定有人没做过的:-) ... 比如我...
>
> 1.
> 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
>
> 2.
> 给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*…*A[n]/A[i]。你不能使用除法运算。
>
> 在matrix67的blog上

> <http://www.matrix67.com/blog>看到的，上面还有很多题目<http://www.matrix67.com/blog/archives/category/program-impossible>
> 。

[Googol Lee]

但取出来的一定是k个么？

2008/5/9 lbaby <lba...@yahoo.com.cn>:

--
新的理论从少数人的主张到一统天下，并不是因为这个理论说服了别人抛弃旧观点，而是因为一代人的逝去。

My blog: http://googollee.blog.163.com

[hayate]

这个我知道了答案之后，才发现对概率论还是不熟啊。

我发现各大公司都喜欢考概率 特别是古典概率 想来是因为概率本身不直观 难以验证 而且常常违反直觉 所以可以考察思维严密性以及抽象性

2008/5/9 Googol Lee <goog...@gmail.com>:

[windstorm]

答案是什么？我还是没想出来。那个blog帖子太多，懒的翻了。

[Marshall]

第一题其实是编程珠玑习题12.10的推广，原题既是k=1的情况，关键就是想到可以替换以前已经选择的元素。
按照这个思路：
1. 对于前k个，全部选择，即选择集S里为前k个元素
2. 第k+i(i>0)个时，令r1=rand(1,k+i)，如果r1>k，则保持现有的选择集合S不变
3. 如果r1<=k, 令r2=rand(1,k)，并让第k+i元素（即当前元素）替换集合S里第r2个元素

归纳：
1. 如果N=k, 前k个全部选择，被选择概率p=1
2. 如果N=k+1, 第k+1个被选择的概率为p=k/(k+1)，前k个被选择的概率为
p=1*(1/(k+1)+(k/(k+1))*((k-1)/k)) = k/(k+1)
3. 如果N=k+i，第k+i个被选择的概率为p=k/(k+i)=k/N，前k+i-1(N-1)个被选择的概率为
p=k/(k+i-1) * (i/(k+i) + (k/(k+i) * (k-1)/k) = k/(k+i-1) * (i/(k+i) + (k-1)/(k+i)) =
k/(k+i-1) * (k+i-1)/(k+i) = k/(k+i) = k/N

2008/5/9 Googol Lee <goog...@gmail.com>:

--
Marshall Wu,
Software Institute, Nanjing University

[hayate]

呵呵

我想起了一个和抽签有关概率问题

4个人抽签 按顺序来一个个来 第一个以1/4的概率选一个签 第二人以1/3的概率选剩下来的，依次下去...

那么，为什么不管抽的顺序，每个人都会以相等的概率抽中签呢。原来是如此基本的概率知识啊，XD

2008/5/9 Marshall <liujinm...@gmail.com>:

[Googol Lee]

恩……确实忽略了"可以替换"

2008/5/9 Marshall <liujinm...@gmail.com>:

[windstorm]

原来是这样想的

压根没有思路......囧

[怀宇范]

赞过。。。这题昨天翻编程珠玑的时候看过得解。。。但我有一些其他的想法不知对否。。。

1. 遍历1次，用数组保存下所有链表的脚标，然后random。题目说是遍历一次，小专个空子不知对否？
2. 还是沿用空间换时间的思路，遍历一次得到一个从C[i]=A[1]*...*A[i-1]，再反向遍历一次得到D[i]=A[i+1]*...*A[N]，so B[i]=C[i]*D[i]。。。另防止越界对边界做1的处理。。。
3. 看过就不说了。。。

2008/5/9 Marshall <liujinm...@gmail.com>:

--
bool ContactMe(person you)
{
if(you.GoTo("14#344, Tsinghua") && you.Find("Fan Huaiyu"))return true;
if(you.MailTo(" dugu...@gmail.com ") || you.MailTo(" fan...@mails.tsinghua.edu.cn "))return true;
if(you.PhoneTo("13488810330") || you.PhoneTo("01062778689"))return true;
if(you.QQTo("120628812") || you.MSNTo("dugu...@hotmail.com"))return true;
if(you.NetTo(" www.cnblogs.com/duguguiyu "))return true;
return false;
}

[Eric]

第一道题 TAOCP 第二卷开头就讲了。 而且讲的是更强的在外存上操作的情形。 我觉得思路不难想， 就是假设某个N终止了，这时候要等概率。 然
后新来一个，又要等概率，必定是要以 1/N+1 概率替换掉原来的。 验证一下的确正确。

On May 9, 12:22 am, "怀宇范" <dugugu...@gmail.com> wrote:
> 赞过。。。这题昨天翻编程珠玑的时候看过得解。。。但我有一些其他的想法不知对否。。。
>
> 1. 遍历1次，用数组保存下所有链表的脚标，然后random。题目说是遍历一次，小专个空子不知对否？
> 2.
> 还是沿用空间换时间的思路，遍历一次得到一个从C[i]=A[1]*...*A[i-1]，再反向遍历一次得到D[i]=A[i+1]*...*A[N]，so
> B[i]=C[i]*D[i]。。。另防止越界对边界做1的处理。。。
> 3. 看过就不说了。。。
>

> 2008/5/9 Marshall <liujinmarsh...@gmail.com>:

>
>
>
> > 第一题其实是编程珠玑习题12.10的推广，原题既是k=1的情况，关键就是想到可以替换以前已经选择的元素。
> > 按照这个思路：
> > 1. 对于前k个，全部选择，即选择集S里为前k个元素
> > 2. 第k+i(i>0)个时，令r1=rand(1,k+i)，如果r1>k，则保持现有的选择集合S不变
> > 3. 如果r1<=k, 令r2=rand(1,k)，并让第k+i元素（即当前元素）替换集合S里第r2个元素
>
> > 归纳：
> > 1. 如果N=k, 前k个全部选择，被选择概率p=1
> > 2. 如果N=k+1, 第k+1个被选择的概率为p=k/(k+1)，前k个被选择的概率为
> > p=1*(1/(k+1)+(k/(k+1))*((k-1)/k)) = k/(k+1)
> > 3. 如果N=k+i，第k+i个被选择的概率为p=k/(k+i)=k/N，前k+i-1(N-1)个被选择的概率为
> > p=k/(k+i-1) * (i/(k+i) + (k/(k+i) * (k-1)/k) = k/(k+i-1) * (i/(k+i) +
> > (k-1)/(k+i)) =
> > k/(k+i-1) * (k+i-1)/(k+i) = k/(k+i) = k/N
>

> > 2008/5/9 Googol Lee <googol...@gmail.com>:

>
> >> 但取出来的一定是k个么？
>
> >> 2008/5/9 lbaby <lba...@yahoo.com.cn>:
> >> > 1，我想出了一个办法：
> >> > 从头遍历，然后计数，对 n 属于 1-N ，取 random/n % k 存入 结果中
>
> >> > On May 8, 7:06 pm, pongba <pon...@gmail.com> wrote:
> >> >> 有点火星，但肯定有人没做过的:-) ... 比如我...
>
> >> >> 1.
>
> >> 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
>
> >> >> 2.
>

> >> 给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用除法运算。

>
> >> >> 在matrix67的blog上
> >> >> <http://www.matrix67.com/blog>看到的，上面还有很多题目<
> >>http://www.matrix67.com/blog/archives/category/program-impossible>
> >> >> 。
>
> >> 当时两个题目都没有想出来，主要是没有思路。想来是知识性的储备不够，比如第一道题目，完全联想不起任何有关的知识和题目。而题目的简洁也导致了辅助探索手法完全没用。有时，知识的有无的确是决定作用的。
>
> >> >> 第二个题目很有意思，当时没有想到。但后来在《编程之美》上看到收录了，不过改成这样一个问法：
>
> >> >> 2'. 给定一个数组A[1..n]，求出任意n-1个数的乘积中最大的一个。（不允许使用除法）
>
> >> >> 这下想出来了。比较了一下为什么原来那个想不出来，现在这个想出来了，得到了一些很有意义的启发。
>
> >> >> --
> >> >> 刘未鹏(pongba)|C++的罗浮宫http://blog.csdn.net/pongba
> >> >> TopLanguagehttp://groups.google.com/group/pongba
>
> >> --
> >> 新的理论从少数人的主张到一统天下，并不是因为这个理论说服了别人抛弃旧观点，而是因为一代人的逝去。
>
> >> My blog:http://googollee.blog.163.com
>
> > --
> > Marshall Wu,
> > Software Institute, Nanjing University
>
> --
> bool ContactMe(person you)
> {
> if(you.GoTo("14#344, Tsinghua") && you.Find("Fan Huaiyu"))return true;

> if(you.MailTo(" dugugu...@gmail.com ") || you.MailTo("
> fanh...@mails.tsinghua.edu.cn "))return true;

> if(you.PhoneTo("13488810330") || you.PhoneTo("01062778689"))return true;

> if(you.QQTo("120628812") || you.MSNTo("dugugu...@hotmail.com"))return true;

[空气]

第三题应该还要求出第一个开始合二为一的结点


我面试微软的时候遇到过一个类似的题目：
有一种特殊的二叉树：它的每个结点都只有指向其父节点的指针。现有某棵这种树的两个结点，求他们最近的公共父节点。

TIP:和他们的深度有关

On 5月8日, 下午8时03分, pongba <pon...@gmail.com> wrote:
> 添加一道微软的:-)
>
> 3. 给出两个单链表，判断它们是否从某个节点开始就合二为一了。
>
> 2008/5/8 pongba <pon...@gmail.com>:
>
>
>
>
>
> > 有点火星，但肯定有人没做过的:-) ... 比如我...
>
> > 1.

> > 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有-k个，且它们是完全随机的（出现概率均等）。
>
> > 2.

> > 给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用-除法运算。
>

> > 在matrix67的blog上 <http://www.matrix67.com/blog>看到的，上面还有很多题目<http://www.matrix67.com/blog/archives/category/program-impossible>
> > 。
>

> > 当时两个题目都没有想出来，主要是没有思路。想来是知识性的储备不够，比如第一道题目，完全联想不起任何有关的知识和题目。而题目的简洁也导致了辅助探索手法完-全没用。有时，知识的有无的确是决定作用的。

>
> > 第二个题目很有意思，当时没有想到。但后来在《编程之美》上看到收录了，不过改成这样一个问法：
>
> > 2'. 给定一个数组A[1..n]，求出任意n-1个数的乘积中最大的一个。（不允许使用除法）
>
> > 这下想出来了。比较了一下为什么原来那个想不出来，现在这个想出来了，得到了一些很有意义的启发。
>
> --
> 刘未鹏(pongba)|C++的罗浮宫http://blog.csdn.net/pongba

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

[pongba]

2008/5/12 空气 <lct...@gmail.com>:

第三题应该还要求出第一个开始合二为一的结点


我面试微软的时候遇到过一个类似的题目：
有一种特殊的二叉树：它的每个结点都只有指向其父节点的指针。现有某棵这种树的两个结点，求他们最近的公共父节点。

TIP:和他们的深度有关

逆着一对一对比，直到分道扬镳的那个节点。

[空气]

没有从父到子的连接。如果要自己存这个连接的话就浪费空间了

[pongba]

2008/5/12 空气 <lct...@gmail.com>:

没有从父到子的连接。如果要自己存这个连接的话就浪费空间了

根据提示想出来的:-(
先算出两条路径深度。求得差值delta。将长的那条剪掉开头delta个节点。然后等位节点一个个比，直到比到一个相等的。

[空气]

嗯嗯～就是这样
面试的时候我也没想到这个方法
也是面试官提示了深度才想到的



On 5月12日, 下午9时58分, pongba <pon...@gmail.com> wrote:
> 2008/5/12 空气 <lct8...@gmail.com>:

[eric Chen]

我觉得和KMP匹配很像,应该可以那样解,对吧

On 5月8日, 下午8时03分, pongba <pon...@gmail.com> wrote:
> 添加一道微软的:-)
>
> 3. 给出两个单链表，判断它们是否从某个节点开始就合二为一了。
>
> 2008/5/8 pongba <pon...@gmail.com>:
>
>
>
> > 有点火星，但肯定有人没做过的:-) ... 比如我...
>
> > 1.

> > 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
>
> > 2.

> > 给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*…*A[n]/A[i]。你不能使用除法运算。
>

> > 在matrix67的blog上 <http://www.matrix67.com/blog>看到的，上面还有很多题目<http://www.matrix67.com/blog/archives/category/program-impossible>
> > 。
>

> > 当时两个题目都没有想出来，主要是没有思路。想来是知识性的储备不够，比如第一道题目，完全联想不起任何有关的知识和题目。而题目的简洁也导致了辅助探索手法完全没用。有时，知识的有无的确是决定作用的。

>
> > 第二个题目很有意思，当时没有想到。但后来在《编程之美》上看到收录了，不过改成这样一个问法：
>
> > 2'. 给定一个数组A[1..n]，求出任意n-1个数的乘积中最大的一个。（不允许使用除法）
>
> > 这下想出来了。比较了一下为什么原来那个想不出来，现在这个想出来了，得到了一些很有意义的启发。
>

[eric Chen]

第二个题目:要除的不乘就行了,通过下标来决断是否需要乘

[eric Chen]

第一个题目:是不是可以先生成一个k(0<k<N)的随机数组,将他们排序,然后一次遍历就可以取出这k个数据.

[Justin L]

这个题我联想到一个实际问题就是淘金，例如要在n吨沙里淘出k克金。我们可能要淘多次，先淘掉一部分，然后再剩下的那部分中继续淘。

实际上不是简单的替换，实际上是分开两步。
1）选择的第一个部分（类似于海选）：遍历，以等概率确定当前的元素是否被选择。（上面有讲到古典概率学的方法）
2）选择的第二个部分（类似于海选选上了之后，进行一个复试，复试肯定不是直接替，而是一个迭代的选择过程，类似第一步）：确认如何替代原来的K个中的
数据。肯定不是随机的从k个中选一个替代。而是有个计数，代表当前选择第一次的时候，有多少（x个）选中了，然后是等概率的从x个中选取。随着第一个部
分的选择量的增加，x的值也会增加，没准进行了两次选择，从x中选出来的x2个字，x2也大于k，于是就要进行第三次选择了。（长期循环下去）也可以在
第三次选择（中国有句话叫是不过三，大概也是说：三次之后，误差已经达到了平时生活中的要求了）的后，进行随机替代法，而不需要进行第四次选择了。

罗嗦了半天，也没说太清楚。总之意思就是不能直接在已经选出来的k个中随便挑一个出来替换掉。而是要计数，然后从这个计数队列中进行随机挑选。