百度软件工程师面试题大全(2)

　　回答：

　　简单来说有以下步骤：

　　1、查找域名对应的IP地址。这一步会依次查找浏览器缓存，系统缓存，路由器缓存，ISPDNS缓存，根域名服务器。

　　2、向IP对应的服务器发送请求。

　　3、服务器响应请求，发回网页内容。

　　4、浏览器解析网页内容。

　　当然，由于网页可能有重定向，或者嵌入了图片，AJAX，其它子网页等等，这4个步骤可能反复进行多次才能将最终页面展示给用户。

　　8、判断两棵树是否相等，请实现两棵树是否相等的比较，相等返回1，否则返回其他值，并说明算法复杂度。

　　数据结构为：

　　[cpp] view plaincopytypedef struct TreeNode

　　{

　　char c;

　　TreeNode *leftchild;

　　TreeNode *rightchild;

　　}TreeNode;

　　函数接口为：int CompTree(TreeNode* tree1,TreeNode* tree2);

　　注：A、B两棵树相等当且仅当RootA->c==RootB-->c,而且A和B的左右子树相等或者左右互换相等。

　　递归方法：

　　[cpp] view plaincopybool CompTree(TreeNode *tree1, TreeNode *tree2)

　　{

　　if(tree1 == NULL && tree2 == NULL)

　　return true;

　　if(tree1 == NULL || tree2 == NULL)

　　return false;

　　if(tree1->c != tree2->c)

　　return false;

　　if( (CompTree(tree1->leftchild, tree2->leftchild) && CompTree(tree1->rightchild, tree2->rightchild)) || CompTree(tree1->leftchild, tree2->rightchild) && CompTree(tree1->rightchild, tree2->leftchild))

　　return true;

　　}

　　时间复杂度：

　　在树的第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人安全无损的过河。

　　回答：警察囚徒过去，警察回来

　　囚徒囚徒过去，囚徒回来

　　警察警察过去，警察囚徒回来

　　警察警察过去，囚徒回来

　　囚徒囚徒过去，囚徒回来

　　囚徒囚徒过去

　　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统计每个数出现的次数，并用两个值存储目前出现次数最多的数和对应出现的次数。

原文转自：http://www.ltesting.net