1、实现一个函数，对一个正整数n，算得到1需要的最少操作次数。操作规则为：如果n为偶数，将其除以2；如果n为奇数，可以加1或减1；一直处理下去。
例子：
func(7) = 4，可以证明最少需要4次运算
n = 7
n-1 6
n/2 3
n-1 2
n/2 1
要求：实现函数(实现尽可能高效) int func(unsign int n)；n为输入，返回最小的运算次数。给出思路(文字描述)，完成代码，并分析你算法的时间复杂度。
答：
[cpp]
view plain
copy
1.
int
func(unsigned
int
n)
2.
{
3.
if
(n == 1)
4.
return
0;
5.
if
(n % 2 == 0)
6.
return
1 + func(n/2);
7.
int
x = func(n + 1);
8.
int
y = func(n – 1);
9.
if
(x > y)
10.
return
y+1;
11.
else
12.
return
x+1;
13.
}
假设n表示成二进制有x bit，可以看出计算复杂度为O(2^x)，也就是O(n)。
将n转换到二进制空间来看（比如7为111，6为110）：
– 如果最后一位是0，则对应于偶数，直接进行除2操作。
– 如果最后一位是1，情况则有些复杂。
**如果最后几位是???01，则有可能为???001，???1111101。在第一种情况下，显然应该-1；在第二种情况下-1和+1最终需要的步数相同。所以在???01的情况下，应该选择-1操作。
**如果最后几位是???
011
，则有可能为???
0011
，???1111
1011
。在第一种情况下，+1和-1最终需要的步数相同；在第二种情况下+1步数更少些。所以在???
011
的情况下，应该选择+1操作。
**如果
最后有更多的连续
1，也应该
选择
+1操作。
如果
最后剩下的各位都是
1，则
有
11时应该选择-1；111时+1和-1相同；1111时应选择+1；大于四个1时也应该选择+1；
[cpp]
view plain
copy
1.
int
func(unsigned
int
n)
2.
{
3.
if
(n == 1)
4.
return
0;
5.
if
(n % 2 == 0)
6.
return
1 + func(n/2);
7.
if
(n == 3)
8.
return
2;
9.
if
(n&2)
10.
return
1 + func(n+1);
11.
else
12.
return
1 + func(n-1);
13.
}
由以上的分析可知，奇数的时候加
1
或减
1
，完全取决于二进制的后两位，如果后两位是
10
、
00
那么肯定是偶数，选择除以
2
，如果后两位是
01
、
11
，那么选择结果会不一样的，如果是
*****01
，那么选择减
1
，如果是
*****11
，那么选择加
1
，特殊情况是就是
n
是
3
的时候，选择减
1
操作。
非递归代码如下：
[cpp]
view plain
copy
1.
//
非递归写法
2.
int
func(
int
n)
3.
{
4.
int
count = 0;
5.
while
(n > 1)
6.
{
7.
if
(n % 2 == 0)
8.
n >>= 1;
9.
else
if
(n == 3)
10.
n–;
11.
else
12.
{
13.
if
(n&2)
//
二进制是
******11
时
14.
n++;
15.
else
//
二进制是
******01
时
16.
n–;
17.
}
18.
count++;
19.
}
20.
return
count;
21.
}
另外一种写法如下：
[cpp]
view plain
copy
1.
//
非递归写法
2.
int
func(
int
n)
3.
{
4.
int
count = 0;
5.
while
(n > 1)
6.
{
7.
if
(n % 2 == 0)
// n % 4
等于
0
或
2
8.
n >>= 1;
9.
else
if
(n == 3)
10.
n–;
11.
else
12.
n += (n % 4 – 2);
// n % 4
等于
1
或
3
13.
count++;
14.
}
15.
return
count;
16.
}
2
、找到满足条件的数组
给定函数d(n)=n+n的各位之和，n为正整数，如d(78)=78+7+8=93。这样这个函数可以看成一个生成器，如93可以看成由78生成。
定义数A：数A找不到一个数B可以由d(B)=A，即A不能由其他数生成。现在要写程序，找出1至10000里的所有符合数A定义的数。
回答：
申请一个长度为10000的bool数组，每个元素代表对应的值是否可以有其它数生成。开始时将数组中的值都初始化为false。
由于大于10000的数的生成数必定大于10000，所以我们只需遍历1到10000中的数，计算生成数，并将bool数组中对应的值设置为true，表示这个数可以有其它数生成。
最后bool数组中值为false的位置对应的整数就是不能由其它数生成的。
3
、一个大的含有
50M
个
URL
的记录，一个小的含有
500
个
URL
的记录，找出两个记录里相同的
URL
。
回答：
首先使用包含
500
个
url
的文件
创建一个
hash_set
。
然后
遍历
50M
的
url
记录
，如果
url
在
hash_set
中
，则
输出此
url
并
从
hash_set
中删除这个
url
。
所有输出的
url
就是两个记录里
相同的
url
。
4
、海量日志数据，提取出某日访问百度次数最多的那个
IP
。
回答：
如果日志文件足够的大，大到
不能完全加载到内存
中的话。
那么可以考虑分而治之的策略，按照
IP
地址的
hash(IP)%1024
值，将海量日志存储到
1024
个小文件
中。每个小文件最多包含
4M
个
IP
地址
。
对于每个
小文件
，可以构建
一个
IP
作为
key
，出现次数作为
value
的
hash_map
，并记录当前
出现次数最多的
1
个
IP
地址
。
有了
1024
个小文件中的出现次数最多的
IP
，我们就可以轻松得到总体上出现次数最多的
IP
。
5
、有
10
个文件，每个文件
1G
，每个文件的每一行都存放的是用户的
query
，每个文件的
query
都可能重复。如何按照
query
的频度排序？
回答：
1
）读取
10
个文件，按照
hash(query)%10
的结果将
query
写到对应的文件中。这样我们就有了
10
个大小约为
1G
的文件。任意一个
query
只会出现在某个文件中。
2
）对于
1
）中获得的
10
个文件，分别进行如下操作
–
利用
hash_map
（
query
，
query_count
）来统计每个
query
出现的次数。
–
利用堆排序算法对
query
按照出现次数进行排序。
–
将排序好的
query
输出的文件中。
这样我们就获得了
10
个文件，每个文件中都是按频率排序好的
query
。
3
）对
2
）中获得的
10
个文件进行归并排序，并将最终结果输出到文件中。
6
、蚂蚁爬杆问题
有一根
27
厘米长的细木杆，在第
3
厘米，
7
厘米，
11
厘米，
17
厘米，
23
厘米这五个位置上各有一只蚂蚁，木杆很细，不能同时通过两只蚂蚁，开始时，蚂蚁的头朝向左还是右是任意的，他们只会朝前走或掉头，但不会后退，当两只蚂蚁相遇后，蚂蚁会同时掉头朝反方向走，假设蚂蚁们每秒钟可以走
1
厘米的距离。求所有蚂蚁都离开木杆的最小时间和最大时间。
答案：
两只蚂蚁相遇后，各自掉头朝相反方向走。如果我们不考虑每个蚂蚁的具体身份，这和两只蚂蚁相遇后，打个招呼继续向前走没有什么区别。
所有蚂蚁都离开木杆的最小时间为
max(min(3,27-3),min(7,27-7),min(11,27-11), min(17,27-17),min(23,27-23))=11
所有蚂蚁都离开木杆的最大时间为
max(max(3,27-3),max(7,27-7),max(11,27-11), max(17,27-17),max(23,27-23))=24
7
、当在浏览器中输入一个
url
后回车，后台发生了什么？比如输入
url
后，你看到了百度的首页，那么这一切是如何发生的呢？
回答：
简单来说有以下步骤：
1
、查找
域名
对应的
IP
地址
。这一步会依次查找
浏览器缓存
，
系统缓存
，
路由器缓存
，
ISPDNS
缓存，根域名服务器
。
2
、向
IP
对应的
服务器发送请求
。
3
、
服务器响应请求
，发回
网页内容
。
4
、浏览器
解析网页内容
。
当然，由于网页可能有重定向，或者嵌入了图片，
AJAX
，其它子网页等等，这
4
个步骤可能反复进行多次才能将最终页面展示给用户。
8
、判断两棵树是否相等，请实现两棵树是否相等的比较，相等返回
1
，否则返回其他值，并说明算法复杂度。
数据结构为：
[cpp]
view plain
copy
1.
typedef
struct
TreeNode
2.
{
3.
char
c;
4.
TreeNode *leftchild;
5.
TreeNode *rightchild;
6.
}TreeNode;
函数接口为：
int CompTree(TreeNode* tree1,TreeNode*tree2);
注：
A
、
B
两棵树相等当且仅当
RootA->c==RootB–>c,
而且
A
和
B
的左右子树相等或者左右互换相等。
递归方法：
[cpp]
view plain
copy
1.
bool
CompTree(TreeNode *tree1, TreeNode *tree2)
2.
{
3.
if
(tree1 == NULL && tree2 == NULL)
4.
return
true
;
5.
if
(tree1 == NULL || tree2 == NULL)
6.
return
false
;
7.
if
(tree1->c != tree2->c)
8.
return
false
;
9.
if
( (CompTree(tree1->leftchild, tree2->leftchild) && CompTree(tree1->rightchild, tree2->rightchild)) || CompTree(tree1->leftchild, tree2->rightchild) && CompTree(tree1->rightchild, tree2->leftchild))
10.
return
true
;
11.
}
时间复杂度：
在树的第
0
层，有
1
个节点，我们会进行
1
次函数调用；
在树的第
1
层，有
2
个节点，我们可能会进行
4
次函数调用；
在树的第
2
层，有
4
个节点，我们可能会进行
16
次函数调用；
….
在树的第
x
层，有
2^x
个节点，我们可能会进行
(2^x)^2
次函数调用；
所以假设总节点数为
n
，则算法的复杂度为
O(n^2)
。
腾讯面试题：求一个论坛的在线人数，假设有一个论坛，其注册
ID
有两亿个，每个
ID
从登陆到退出会向一个
日志文件
中记下
登陆时间和退出时间
，要求写一个算法统计一天中论坛的
用户在线分布
，取样粒度为
秒
。
回答：
一天总共有
3600*24=
86400
秒
。
定义一个长度为
86400
的
整数数组
intdelta[86400]
，每个整数对应
这一秒的人数变化值
，可能为
正
也可能为
负
。开始时
将数组元素都初始化为
0
。
然后依次读入每个用户的
登录时间和退出时间
，将
与登录时间对应的整数值加
1
，将
与退出时间对应的整数值减
1
。
这样处理一遍后数组中存储了每秒中的
人数变化情况
。
定义另外一个长度为
86400
的整数数组
intonline_num[86400]
，每个整数对应
这一秒的论坛在线人数
。
假设
一天开始时
论坛
在线人数为
0
，则
第
1
秒的人数
online_num[0]=delta[0]
。第
n+1
秒
的人数
online_num[n]=
online_num[n-1]
+
delta[n]
。
这样我们就获得了一天中
任意时间的在线人数
。
9
、三个警察和三个囚徒的过河问题
三个警察和三个囚徒共同旅行。一条河挡住了去路，河边有一条船，但是每次只能载
2
人。存在如下的危险：无论在河的哪边，当囚徒人数多于警察的人数时，将有警察被囚徒杀死。问题：请问如何确定渡河方案，才能保证
6
人安全无损的过河。
答案：第一次：两囚徒同过，回一囚徒
第二次：两囚徒同过，回一囚徒
第三次：两警察同过，回一囚徒一警察（此时对岸还剩下一囚徒一警察，是安全状态）
第四次：两警察同过，回一囚徒（此时对岸有
3
个警察，是安全状态）
第五次：两囚徒同过，回一囚徒
第六次：两囚徒同过；
over
10
、从
300
万字符串中找到最热门的
10
条
搜索的输入信息是一个字符串，统计
300
万输入信息
中的
最热门的前
10
条
，我们
每次输入的一个字符串为不超过
255byte
，
内存使用只有
1G
。请描述思想，写出算法（
c
语言），空间和时间复杂度。
答案：
300
万个字符串最多（假设没有重复，都是最大长度）占用内存
3M*1K/4=0.75G
。所以可以将所有字符串都存放在内存中进行处理。
可以使用
key
为字符串
（事实上是字符串的
hash
值），
值为字符串出现次数的
hash
来
统计每个字符串出现的次数
。并用一个
长度为
10
的数组
/
链表来存储目前出现次数最多的
10
个字符串。
这样空间和时间的复杂度都是
O(n)
。
11
、如何找出字典中的兄弟单词。给定一个单词
a
，如果通过交换单词中字母的顺序可以得到另外的单词
b
，那么定义
b
是
a
的兄弟单词。现在给定一个字典，用户输入一个单词，如何根据字典找出这个单词有多少个兄弟单词？
答案：
使用
hash_map
和链表。
首先定义一个
key
，使得兄弟单词有相同的
key
，不是兄弟的单词有不同的
key
。例如，将单词按字母从小到大重新排序后作为其
key
，比如
bad
的
key
为
abd
，
good
的
key
为
dgoo
。
使用链表将所有兄弟单词串在一起，
hash_map
的
key
为单词的
key
，
value
为链表的起始地址。
开始时，先遍历字典，将每个单词都按照
key
加入到对应的链表当中。当需要找兄弟单词时，只需求取这个单词的
key
，然后到
hash_map
中找到对应的链表即可。
这样创建
hash_map
时时间复杂度为
O(n)
，查找兄弟单词时时间复杂度是
O(1)
。
12
、找出数组中出现次数超过一半的数，现在有一个数组，已知一个数出现的次数超过了一半，请用
O(n)
的复杂度的算法找出这个数。
答案
1
：
创建一个
hash_map
，
key
为数组中的数，
value
为此数出现的次数。遍历一遍数组，用
hash_map
统计每个数出现的次数，并用两个值存储目前出现次数最多的数和对应出现的次数。
这样可以做到
O(n)
的时间复杂度和
O(n)
的空间复杂度，满足题目的要求。
但是没有利用
“
一个数出现的次数超过了一半
”
这个特点。也许算法还有提高的空间。
答案
2
：
使用两个变量
A
和
B
，其中
A
存储某个数组中的数，
B
用来计数。开始时将
B
初始化为
0
。
遍历数组，如果
B=0
，则令
A
等于当前数，令
B
等于
1
；如果当前数与
A
相同，则
B=B+1
；如果当前数与
A
不同，则令
B=B-1
。遍历结束时，
A
中的数就是要找的数。
这个
intfindMore(int a[],int n)
{
int A=a[0],B=0;
for(int i=0;i<n;i++)
{
if(A==a[i])
B++;
else
B–;
if(B==0)
{
A=a[i];
B=1;
}
}
return A;
}
算法的时间复杂度是
O(n)
，空间复杂度为
O(1)
。
13
、找出被修改过的数字
n
个空间（其中
n<1M
），存放
a
到
a+n-1
的数，位置随机且数字不重复，
a
为正且未知。现在第一个空间的数被误设置为
-1
。已经知道被修改的数不是最小的。请找出被修改的数字是多少。
例如：
n=6
，
a=2
，原始的串为
5,3,7,6,2,4
。现在被别人修改为
-1,3,7,6,2,4
。现在希望找到
5
。
回答：
由于修改的数不是最小的，所以遍历第二个空间到最后一个空间可以得到
a
的值。
a
到
a+n-1
这
n
个数的和是
total=na+(n-1)n/2
。
将第二个至最后一个空间的数累加获得
sub_total
。
那么被修改的数就是
total-sub_total
。
14
、设计
DNS
服务器中
cache
的数据结构。
要求设计一个
DNS
的
Cache
结构，要求能够满足每秒
5000
以上的查询，满足
IP
数据的快速插入，查询的速度要快。（题目还给出了一系列的数据，比如：站点数总共为
5000
万，
IP
地址有
1000
万，等等）
回答：
DNS
服务器实现域名到
IP
地址的转换。
每个域名的平均长度为
25
个字节（估计值），每个
IP
为
4
个字节，所以
Cache
的每个条目需要大概
30
个字节。
总共
50M
个条目，所以需要
1.5G
个字节的空间。可以放置在内存中。（考虑到每秒
5000
次操作的限制，也只能放在内存中。）
可以考虑的数据结构包括
hash_map
，字典树，红黑树等等。
15
、找出给定字符串对应的序号。
序列
Seq=[a,b,…z,aa,ab…az,ba,bb,…bz,…,za,zb,…zz,aaa,…]
类似与
excel
的排列，任意给出一个字符串
s=[a-z]+(
由
a-z
字符组成的任意长度字符串），请问
s
是序列
Seq
的第几个。
回答：
注意到每满
26
个就会向前进一位，类似一个
26
进制的问题。
比如
ab
，则位置为
26*1+2
；
比如
za
，则位置为
26*26+1
；
比如
abc
，则位置为
26*26*1+26*2+3
；
16
、找出第
k
大的数字所在的位置。
写一段程序，找出数组中第
k
大小的数，输出数所在的位置。例如
{2
，
4
，
3
，
4
，
7}
中，第一大的数是
7
，位置在
4
。第二大、第三大的数都是
4
，位置在
1
、
3
随便输出哪一个均可。
答案：
先找到第
k
大的数字，然后再遍历一遍数组找到它的位置。所以题目的难点在于如何最高效的找到第
k
大的数。
我们可以通过快速排序，堆排序等高效的排序算法对数组进行排序，然后找到第
k
大的数字。这样总体复杂度为
O(NlogN)
。
我们还可以通过二分的思想，找到第
k
大的数字，而不必对整个数组排序。从数组中随机选一个数
t
，通过让这个数和其它数比较，我们可以将整个数组分成了两部分并且满足，
{x,xx,…,t}<{y,yy,…}
。
在将数组分成两个数组的过程中，我们还可以记录每个子数组的大小。这样我们就可以确定第
k
大的数字在哪个子数组中。
然后我们继续对包含第
k
大数字的子数组进行同样的划分，直到找到第
k
大的数字为止。
平均来说，由于每次划分都会使子数组缩小到原来
1/2
，所以整个过程的复杂度为
O(N)
。
17
、给
40
亿个不重复的
unsigned int
的整数，没排过序的，然后再给几个数，如何快速判断这几个数是否在那
40
亿个数当中
?
答案：
unsignedint
的取值范围是
0
到
2^32-1
。我们可以申请连续的
2^32/8=512M
的内存，用每一个
bit
对应一个
unsigned int
数字。首先将
512M
内存都初始化为
0
，然后每处理一个数字就将其对应的
bit
设置为
1
。当需要查询时，直接找到对应
bit
，看其值是
0
还是
1
即可。
18
、在一个文件中有
10G
个整数，乱序排列，要求找出中位数。内存限制为
2G
。
回答：
不妨假设
10G
个整数是
64bit
的。
2G
内存可以存放
256M
个
64bit
整数。
我们可以将
64bit
的整数空间平均分成
256M
个取值范围，用
2G
的内存对每个取值范围内出现整数个数进行统计。这样遍历一边
10G
整数后，我们便知道中数在那个范围内出现，以及这个范围内总共出现了多少个整数。
如果中数所在范围出现的整数比较少，我们就可以对这个范围内的整数进行排序，找到中数。如果这个范围内出现的整数比较多，我们还可以采用同样的方法将此范围再次分成多个更小的范围（
256M=2^28
，所以最多需要
3
次就可以将此范围缩小到
1
，也就找到了中数）。
19
、时分秒针在一天之类重合多少次？（
24
小时）
2
次
而时针和分针重合了
22
次。
20
、将多个集合合并成没有交集的集合。
给定一个字符串的集合，格式如：
{aaabbbccc}
，
{bbbddd}
，
{eeefff}
，
{ggg}
，
{dddhhh}
要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出
{aaabbbcccdddhhh}
，
{eeefff}
，
{ggg}
。
（
1
）请描述你解决这个问题的思路；
（
2
）请给出主要的处理流程，算法，以及算法的复杂度
（
3
）请描述可能的改进。
回答：
集合使用
hash_set
来表示，这样合并时间复杂度比较低。
1
、给每个集合编号为
0
，
1
，
2
，
3…
2
、创建一个
hash_map
，
key
为字符串，
value
为一个链表，链表节点为字符串所在集合的编号。遍历所有的集合，将字符串和对应的集合编号插入到
hash_map
中去。
3
、创建一个长度等于集合个数的
int
数组，表示集合间的合并关系。例如，下标为
5
的元素值为
3
，表示将下标为
5
的集合合并到下标为
3
的集合中去。开始时将所有值都初始化为
-1
，表示集合间没有互相合并。在集合合并的过程中，我们将所有的字符串都合并到编号较小的集合中去。
遍历第二步中生成的
hash_map
，对于每个
value
中的链表，首先找到最小的集合编号（有些集合已经被合并过，需要顺着合并关系数组找到合并后的集合编号），然后将链表中所有编号的集合都合并到编号最小的集合中（通过更改合并关系数组）。
4
、现在合并关系数组中值为
-1
的集合即为最终的集合，它的元素来源于所有直接或间接指向它的集合。
算法的复杂度为
O(n)
，其中
n
为所有集合中的元素个数。
题目中的例子：
0:{aaabbbccc}
1:{bbbddd}
2:{eeefff}
3:{ggg}
4:{dddhhh}
生成的
hash_map
，和处理完每个值后的合并关系数组分别为
aaa:0
。
[-1,-1,-1,-1,-1]
bbb:0,1
。
[-1,0,-1,-1,-1]
ccc:0
。
[-1,0,-1,-1,-1]
ddd:1,4
。
[-1,0,-1,-1,0]
eee:2
。
[-1,0,-1,-1,0]
fff:2
。
[-1,0,-1,-1,0]
ggg:3
。
[-1,0,-1,-1,0]
hhh:4
。
[-1,0,-1,-1,0]
所以合并完后有三个集合，第
0
，
1
，
4
个集合合并到了一起，
21
、平面内有
11
个点，由它们连成
48
条不同的直，由这些点可连成多少个三角形？
解析：
首先你要分析，平面中有
11
个点，如果这些点中任意三点都没有共线的，那么一共应该有
C(11
，
2)=55
，
可是，题目中说可以连接成
48
条直线，那么这
11
个点中必定有多点共线的情况。
55-48=7
，从
7
来分析：
假设有一组三个点共线，那么可以组成的直线在
55
的基础上应该减去
C(3
，
2)-1=2 2*3=6≠7
，因此，可以断定不仅有三点共线的，也可能有四个点共线的可能。
假设有一组四个点共线，那么可以组成的直线在
55
的基础上应该减去
C(4
，
2)-1=5
（备注，五个点共线的可能不存在，因为，
C(5
，
2)-1=9>7
，故不可能有五条直线共线。）
因此，三点共线少
2
条，
4
点共线少
5
条，只有一个
4
点共线，一个
3
点共线才能满足条件，其余情况不能满足少了
7
条直线。
那么，这
11
个点能组成的三角形的个数为，
C(11
，
3)-C(3
，
3)-C(4
，
3)=165-1-4=160
（备注，三个点共线不能组成三角形）