今日面试题:熟悉的陌生人

大家都知道facebook用户都是双向的好友,a是b的好友,那么b一定是a的好友,现在给定一个用户列表,其中有些用户是好友,有些不是,请判断,这些用户是否可以划分为两组,并且每组内的用户,互相都不是好友。如果能,请给出这个划分。

例子1:

用户:{1, 2, 3}

好友关系:1-2, 2-3

划分:{1,3} {2}

例子2:

用户{1,2,3,4}

好友关系:1-2, 2-3, 3-4,4-1

划分:{1, 3}{2, 4}

==================================

又见Google之星分析

原题

给定一批查询日志,数量为n。其中,有的查询出现了多于n/3次,请在线性时间内,找到所有满足条件的查询。

分析

如果初次遇到这个问题,我们会有什么样的思路呢?

  1. 采用hashmap进行计数,O(n)的空间,O(n)的时间
  2. 进行排序,O(nlogn)
  3. 快速选择算法,这个也可以做到O(n)的时间。

但是,如果面试官进一步限制了可以采用方法的范围:不允许使用上述方法,该如何处理呢?

我们在之前的面试题目中,遇到过类似的一个问题:那次的查询出现的次数是一半以上。大家还记得,我们的解法么?道理很简单,但解法是很巧妙的,当我们每次去掉两个不相同的查询,那最终剩下的查询,就是我们要找的查询——这个查询的出现次数,占了一半以上。

那如果是多于n/3次呢?更一般的情况下,如果是多于n/m次呢?道理完全一样的:我们每次去掉m个不同的查询,那最终剩下的查询,就是我们要找的备选的。道理很简单,可是要如何实现呢?之前的题目,是比较简单就能够实现每次去掉两个不同的查询的,更一般的情况下,如何每次去掉m个不同的元素呢?

下面我们会介绍一种实现方法,核心的原理就是:每次去掉m个不同的查询。第一个方法,是很有趣的一个方法,相信能够给大家以启发。

一种有趣的实现

有一个经典的游戏,叫做俄罗斯方块。想必很多同学都玩过的吧,俄罗斯方块,有不同颜色、不同形状的方块,从上往下落,如果砌满一行,这一行就会消失。一般列数都是固定的,在玩儿的过程中不会变化。这里要讲的一个实现,就是从俄罗斯方块这个游戏启发而来的。

我们申请一个大小为m的map,开始遍历查询日志,如果:

  1. 遇到一个不在map中的查询,则插入map中,并且将值设置为1(相当于新落下一个方块)
  2. 遇到一个在map中的查询,则将map中,该查询对应的值加1(相当于在已有的方块上又多加了一个)

当map中的查询个数等于m时,则对map中所有查询的值减一(相当于砌满了一层,就会消掉)。直到遍历完毕查询日志,map中还存在的查询,就是我们要找的查询的备选。我们看下面的具体的例子:

查询日志为:4 3 3 2 1 2 3 4 4 7 且m=5

上述方法的步骤如下:

当 4 3 3 落入到map中的时候,map的形状如下:

3 
4  3 

当 2 1 2 3 落入到map中的时候,map形状如下:

  3     
  3     2
4 3  1 2

当 4 4 落入到map中的时候,map的形状如下:

4  3     
4   3    2  
4 3   1  2  

当 7 落入到map中的时候,map形状如下:

4 3      
4 3   2  
4 3 1 2 7

此时,map的大小=5,可以消除一行了。

消除之后如下图:

4 3      
4 3   2  

此时剩下三个查询,但不都是满足条件的查询,需要逐个验证。O(n)即可。

分析上述方法的空间复杂度为O(m).当m=3时,就可以认为是常数空间。那么时间复杂度呢?切要看map是如何实现的,如果是基于树的,整个的时间复杂度O(nlogm),m=3时,可以认为是O(n)的。

【分析完毕】

本文来自微信:待字闺中,2013-07-18发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。