以下是小编为大家整理的百度算法面试题（共含8篇），欢迎阅读与收藏。同时，但愿您也能像本文投稿人“Deporc”一样，积极向本站投稿分享好文章。
算法1: 1.在字典中查找单词 字典采用27叉树组织,每个节点对应一个字母,查找就是一个字母 一个字母匹配.算法时间就是单词的长度k. 2.纠错算法 情况:当输入的最后一个字母不能匹配时就提示出错,简化出错处理，动态提示可能 处理方法: (a)当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议; (b)当前字母拼写错误：当前字母的键盘相邻作为提示;(只是简单的描述，可 以有更多的)根据分析字典特征和用户单词已输入部分选择(a),(b)处理复杂性分析：影响算法的效率主要是字典的实现与纠错处理 (a)字典的实现已有成熟的算法，改进不大，也不会成为瓶颈; (b)纠错策略要简单有效 ,如前述情况，是线性复杂度; (3)改进策略选择最是重要，可以采用统计学习的方法改进。 问题4 寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。(1)请描述你解决这个问题的思路;(2)请给出主要的处理流程，算法，以及算法的复杂度。 答案： (1)思路：用哈希做 (2)首先逐次读入查询串，算哈希值，保存在内存数组中，同时统计频度(注意值与日志项对应关系)选出前十的频度，取出对应的日志串，简单不过了。哈希的设计是关键。 问题5 集合合并：给定一个字符串的集合，格式如：{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}(1)请描述你解决这个问题的思路;(2)请给出主要的处理流程，算法，以及算法的复杂度(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。 答案： (1)思路：先将集合按照大小排列后,优先考虑小的集合是否与大的集合有交集。有就合并，如果小集合与所有其他集合都没有交集则独立。独立的集合在下一轮的比较中不用考虑。这样就可以尽量减少字符串的比较次数。当所有集合都独立的时候，就终止。 (2)处理流程：1.将集合按照大小排序，组成集合合并待处理列表2.选择最小的集合，找出与之有交集的集合，如果有，合并之;如果无，则与其它集合是独立集合，从待处理列表 中删除。3.重复直到待处理列表为空 算法2： 1、将集合按照大小从小到大排序,组成待处理的集合列表。 2、取出待处理集合列表中最小的集合，对于集合的每个元素，依次在其他集合中搜索是否有此元素存在： 1>若存在，则将此小集合与大集合合并，并根据大小插入对应的位置 。转3。 2>若不存在，则在该集合中取下一个元素。如果无下一个元素，即所有元素都不存在于其他集合。则表明此集合独立，从待处理集合列表中删除。并加入结果集合列表。转3。 3、如果待处理集合列表不为空，转2。如果待处理集合列表为空，成功退出，则结果集合列表就是最终的输出。算法复杂度分析：假设集合的个数为n，最大的集合元素为m排序的时间复杂度可以达到n*log(n)然后对于元素在其他集合中查找，最坏情况下为(n-1)*m查找一个集合是否与其他集合有交集的最坏情况是m*m*(n-1)合并的时间复杂度不会超过查找集合有交集的最坏情况。所以最终最坏时间复杂度为O(m*m*n*n)需要说明的是：此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先与最大的集合进行比较，这些都最大的回避了最坏情况。3)可能的改进：首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及合并的效率增高。另外，可能采取恰当的数据结构也可以将查找以及合并等操作的效率得到提高。
更多互联网相关面试题分享：1、腾讯超难面试试题 2、百度Web开发工程师笔试题
3、腾讯公司程序员面试题及答案详解 4、腾讯往届面试试题【汇总】 5、百度技术研发类笔试题 6、阿里前端大神寒冬谈谈面试与面试题 7、百度android开发类面试题目 8、最新阿里面试题汇总 9、百度校园招聘数据挖掘工程师面试题集锦
1、反转一个链表。循环算法。
1 List reverse(List l) {
2 if(!l) return l;
3 list cur = l.next;
4 list pre = l;
5 list tmp;
6 pre.next = null;
7 while ( cur ) {
8 tmp = cur;
9 cur = cur.next;
10 tmp.next = pre
11 pre = tmp;
12 }
13 return tmp;
14 }
2、反转一个链表。递归算法。
1 List resverse(list l) {
2 if(!l || !l.next) return l;
3
4 List n = reverse(l.next);
5 l.next.next = l;
6 l.next=null;
7 }
8 return n;
9 }
3、广度优先遍历二叉树。
1 void BST(Tree t) {
2 Queue q = new Queue;
3 q.enque(t);
4 Tree t = q.deque();
5 while(t) {
6 System.out.println(t.value);
7 q.enque(t.left);
8 q.enque(t.right);
9 t = q.deque();
10 }
11 }
----------------------
1class Node {
2 Tree t;
3 Node next;
4 }
5class Queue {
6 Node head;
7 Node tail;
8 public void enque(Tree t){
9 Node n = new Node();
10 n.t = t;
11 if(!tail){
12 tail = head = n;
13 } else {
14 tail.next = n;
15 tail = n;
16 }
17 }
18 public Tree deque() {
19 if (!head) {
20 return null;
21 } else {
22 Node n = head;
23 head = head.next;
24 return n.t;
25 }
26}
4、输出一个字符串所有排列。注意有重复字符。
1char[] p;
2void perm(char s[], int i, int n){
3 int j;
4 char temp;
5 for(j=0;j
6 if(j!=0 && s[j]==s[j-1]);
7 elseif(s[j]!='@'){
8 p[i]=s[j];
9 s[j]='@';
10 if(i==n-1){
11 p[n]='';
12 printf(“%s”, p);
13 }else{
14 perm(s,i+1,n);
15 }
16 s[j]=p[i];
17 }
18 }
19}
--------------------------
1void main() {
2 char s[N];
3 sort(s);
4 perm(s,0,strlen(s));
5}
5、输入一个字符串，输出长型整数。
1 long atol(char *str){
2 char *p = str;
3 long l=1;m=0;
4 if (*p=='-') {
5 l=-1;
6 ++p;
7 }
8 while(isDigit(*p)){
9 m = m*10 + p;
10 ++p;
11 }
12 if(!p) return m*l;
13 else return error;
14}
6、判断一个链表是否有循环。
1 int isLoop(List l) {
2 if ( ! l) return - 1 ;
3 List s = l.next;
4 while (s && s != l) {
5 s = s.next;
6 }
7 if ( ! s) return - 1 ;
8 else reutrn 1 ;
9 }
-----------
1int isLoop(List l){
2 if(!l) return 0;
3 p=l.next;
4 wihle(p!=l&&p!=null) {
5 l.next=l;
6 l=p;p=p.next;
7 }
8 if(p=l) return 1;
9 return 0;
10}
实际上，在我的面试过程中，还问到了不破坏结构的其他算法。
我的答案是从链表头开始遍历，如果节点next指针指向自身，则循环存在;否则将next指针指向自身，遍历下一个节点。直至next指针为空，此时链表无循环。
7、反转一个字符串。
1 void reverse( char * str) {
2 char tmp;
3 int len;
4 len = strlen(str);
5 for ( int i = 0 ;i < len / 2 ; ++ i) {
6 tmp = char [i];
7 str[i] = str[len - i - 1 ];
8 str[len - i - 1 ] = tmp;
9 }
10 }
8、实现strstr函数。
1int strstr(char[] str, char[] par){
2 int i=0;
3 int j=0;
4 while(str[i] && str[j]){
5 if(str[i]==par[j]){
6 ++i;
7 ++j;
8 }else{
9 i=i-j+1;
10 j=0;
11 }
12 }
13 if(!str[j]) return i-strlen(par);
14 else return -1;
15}
9、实现strcmp函数。
1int strcmp(char* str1, char* str2){
2 while(*str1 && *str2 && *str1==*str2){
3 ++str1;
4 ++str2;
5 }
6 return *str1-*str2;
7}
10、求一个整形中1的位数。
1 int f( int x) {
2 int n = 0 ;
3 while (x) {
4 ++ n;
5 x &= x - 1 ;
6 }
7 return n;
8 }
11、汉诺塔问题。
1void tower(n,x,y,z){
2 if(n==1) move(x,z);
3 else {
4 tower(n-1, x,z,y);
5 move(x,z);
6 tower(n-1, y,x,z);
7 }
8}
12、三柱汉诺塔最小步数。
1 int f3(n) {
2 if (f3[n]) return f3[n];
3 else {
4 if (n == 1 ) {
5 f3[n] = 1 ;
6 return 1 ;
7 }
8 f3[n] = 2 * f3(n - 1 ) + 1 ;
9 return f3[n];
10 }
11 }
四柱汉诺塔最小步数。
1int f4(n){
2 if(f4[n]==0){
3 if(n==1) {
4 f4[1]==1;
5 return 1;
6 }
7 min=2*f4(1)+f3(n-1);
8 for(int i=2;i
9 u=2*f4(i)+f3(n-i);
10 if(u
11 }
12 f4[n]=min;
13 return min;
14 } else return f4[n];
15}
13、在一个链表中删除另一个链表中的元素。
1void (List m, List n) {
2 if(!m || !n) return;
3 List pre = new List();
4 pre.next=m;
5 List a=m, b=n,head=pre;
6 while(a && b){
7 if(a.value < b.value) {
8 a=a.next;
9 pre=pre.next;
10 }else if(a.value >b.value){
11 b=b.next;
12 }else{
13 a=a.next;
14 pre.next=a;
15 }
16 }
17 m=head.next;
18}
14、一个数组，下标从0到n，元素为从0到n的整数。判断其中是否有重复元素。
1int hasDuplicate(int[] a, int n){
2 for(int i=0;i
3 while(a[i]!=i && a[i]!=-1){
4 if(a[a[i]]==-1) return 1;
5 a[i]=a[a[i]];
6 a[a[i]]=-1;
7 }
8 if(a[i]==i) {a[i]=-1;}
9 }
10 return 0;
11}
15、判断一颗二叉树是否平衡。
1int isB(Tree t){
2 if(!t) return 0;
3 int left=isB(t.left);
4 int right=isB(t.right);
5 if( left >=0 && right >=0 && left - right <= 1 || left -right >=-1)
6 return (left
7 else return -1;
8}
9
16、返回一颗二叉树的深度。
1int depth(Tree t){
2 if(!t) return 0;
3 else {
4 int a=depth(t.right);
5 int b=depth(t.left);
6 return (a>b)?(a+1):(b+1);
7 }
8}
17、两个链表，一升一降。合并为一个升序链表。
1 List merge(List a, List d) {
2 List a1 = reverse(d);
3 List p = q = new List();
4 while ( a && a1 ) {
5 if (a.value < a1.value) {
6 p.next = a;
7 a = a.next;
8 } else {
9 p.next = a1;
10 a1 = a1.next;
11 }
12 p = p.next;
13 }
14 if (a) p.next = a;
15 elseif(a1) p.next = a1;
16 return q.next;
17 }
18、将长型转换为字符串。
1char* ltoa(long l){
2 char[N] str;
3 int i=1,n=1;
4 while(!(l/i<10)){i*=10;++n}
5 char* str=(char*)malloc(n*sizeof(char));
6 int j=0;
7 while(l){
8 str[j++]=l/i;
9 l=l%i;
10 i/=10;
11 }
12 return str;
13}
19、用一个数据结构实现
1 if (x == 0) y = a;
2 else y = b;
1 j[] = {a,b};
2 y=j[x];
20、在双向链表中删除指定元素。
1void del(List head, List node){
2 List pre=new List();
3 pre.next = head;
4 List cur = head;
5 while(cur && cur!=node){
6 cur=cur.next;
7 pre=pre.next;
8 }
9 if(!cur) return;
10 List post = cur.next;
11 pre.next=cur.next;
12 post.last=cur.last;
13 return;
14}
21、不重复地输出升序数组中的元素。
1 void outputUnique( char [] str, int n) {
2 if (n <= 0 ) return ;
3 elseif(n == 1 ) putstr[ 0 ]);
4 else {
5 int i = 0 ,j = 1 ;
6 putstr[ 0 ]);
7 while (j < n) {
8 if (str[j] !== str[i]) {
9 putstr[j]);
10 i = j;
11 }
12 ++ j;
13 }
14 }
15 }
22、面试过程中我还遇到了下面几题：
1、如何删除链表的倒数第m的元素?我的方法是先用pre指针从链表头开始步进m，新建pst节点next指针指向头节点，cur指针指向头节点，然后pre，cur，post三个指针一起步进，当pre指向链表结尾的时候cur指向倒数第m个元素，最后利用pst指针删除cur指向元素。
2、如何判断一个字符串是对称的?如a，aa，aba。设置头尾指针同时向中间比较靠齐直至相遇。
3、如何利用2函数找出一个字符串中的所有对称子串?以子串头指针和尾指针为循环变量设置两个嵌套的循环以找出所有子串，对每个子串应用2函数。
[微软算法面试题]
1. 使用PHP描述冒泡排序和快速排序算法，对象可以是一个数组
2. 使用PHP描述顺序查找和二分查找(也叫做折半查找)算法，顺序查找必须考虑效率，对象可以是一个有序数组
3. 写一个二维数组排序算法函数，能够具有通用性，可以调用php内置函数
【附答案】(以下答案不一定是最好的，只是一个简单的参考)
一、基础题
1. 相等 相等 不相等
2. true true true true true false true false
3. aaaaaa
4. 5 0 1
5. 5 2
6. 1 2
7. 使用五种以上方式获取一个文件的扩展名
function get_ext1($file_name){
return strrchr($file_name, ‘.’);
}
function get_ext2($file_name){
return substr($file_name, strrpos($file_name, ‘.’));
}
function get_ext3($file_name){
return array_pop(explode(‘.’, $file_name));
}
function get_ext4($file_name){
$p = pathinfo($file_name);
return $p['extension'];
}
function get_ext5($file_name){
return strrev(substr(strrev($file_name), 0, strpos(strrev($file_name), ‘.’)));
}
二、算法题
1. 使用PHP描述冒泡排序和快速排序算法，对象可以是一个数组
//冒泡排序(数组排序)
function bubble_sort($array)
{
$count = count($array);
if ($count <= 0) return false;
for($i=0; $i<$count; $i++){
for($j=$count-1; $j>$i; $jC){
if ($array[$j] < $array[$j-1]){
$tmp = $array[$j];
$array[$j] = $array[$j-1];
$array[$j-1] = $tmp;
}
}
}
return $array;
}
//快速排序(数组排序)
function quick_sort($array) {
if (count($array) <= 1) return $array;
$key = $array[0];
$left_arr = array();
$right_arr = array();
for ($i=1; $i
if ($array[$i] <= $key)
$left_arr[] = $array[$i];
else
$right_arr[] = $array[$i];
}
$left_arr = quick_sort($left_arr);
$right_arr = quick_sort($right_arr);
return array_merge($left_arr, array($key), $right_arr);
}
2. 使用PHP描述顺序查找和二分查找(也叫做折半查找)算法，顺序查找必须考虑效率，对象可以是一个有序数组
//二分查找(数组里查找某个元素)
function bin_sch($array, $low, $high, $k){
if ($low <= $high){
$mid = intval(($low+$high)/2);
if ($array[$mid] == $k){
return $mid;
}elseif ($k < $array[$mid]){
return bin_sch($array, $low, $mid-1, $k);
}else{
return bin_sch($array, $mid+1, $high, $k);
}
}
return -1;
}
//顺序查找(数组里查找某个元素)
function seq_sch($array, $n, $k){
$array[$n] = $k;
for($i=0; $i<$n; $i++){
if($array[$i]==$k){
break;
}
}
if ($i<$n){
return $i;
}else{
return -1;
}
}
3. 写一个二维数组排序算法函数，能够具有通用性，可以调用php内置函数
//二维数组排序， $arr是数据，$keys是排序的健值，$order是排序规则，1是升序，0是降序
function array_sort($arr, $keys, $order=0) {
if (!is_array($arr)) {
return false;
}
$keysvalue = array();
foreach($arr as $key =>$val) {
$keysvalue[$key] = $val[$keys];
}
if($order == 0){
asort($keysvalue);
}else {
arsort($keysvalue);
}
reset($keysvalue);
foreach($keysvalue as $key =>$vals) {
$keysort[$key] = $key;
}
$new_array = array();
foreach($keysort as $key =>$val) {
$new_array[$key] = $arr[$val];
}
return $new_array;
}
[php算法面试题]
* 有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
* 木杆很细，不能同时通过一只蚂蚁。开始 时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，
* 但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。
* 编写程序，求所有蚂蚁都离开木杆 的最小时间和最大时间。
*
*
* 分析:题目中的蚂蚁只可能相遇在整数点,不可以相遇在其它点,比如3.5cm处之类的,也就是可以让每只蚂蚁走 1秒,然后
* 查看是否有相遇的即可.
*
* 这样我的程序实现思路就是,初始化5只蚂蚁,让每只蚂蚁走1秒,然后看是否有相遇的,如果有则做相应处理.当每只蚂蚁都
* 走出木杆时,我就记录当前时间.这样就可以得到当前状态情况下,需要多久可以走出木杆,然后遍历所有状态则可以得到所胡
* 可能.
*/
package baidu;
public class Ant {
/*
* step 表示蚂蚁每一个单位时间所走的长度
*/
private final static int step = 1;
/*
* position表示蚂蚁所处的初始位置
*/
private int position;
/*
* direction表示蚂蚁的前进方向，如果为1表示向27厘米的方向走， 如果为-1，则表示往0的方向走。
*/
private int direction = 1;
/*
* 此函数运行一次，表示蚂蚁前进一个单位时间，如果已经走下木杆则会抛出异常
*/
public void walk {
if (isOut()) {
throw new RuntimeException(“the ant is out”);
}
position = position + this.direction * step;
};
/**
* 检查蚂蚁是否已经走出木杆，如果走出返回true
*
*/
public boolean isOut() {
return position <= 0 || position >= 27;
}
/**
* 检查此蚂蚁是否已经遇到另外一只蚂蚁
* @param ant
* @return 如果遇到返回true
*/
public boolean isEncounter(Ant ant) {
return ant.position == this.position;
}
/**
* 改变蚂蚁的前进方向
*/
public void changeDistation() {
direction = -1 * direction;
}
/**
* 构造函数,设置蚂蚁的初始前进方向,和初始位置
* @param position
* @param direction
*/
public Ant(int position, int direction) {
this.position = position;
if (direction != 1) {
this.direction = -1;//方向设置初始位置,比如为0时,也将其设置为1.这样可以方便后面的处理
} else {
this.direction = 1;
}
}
}
/////////////////////////////////////////////////////////
package baidu;
public class Controller {
public static void main(String[] args) {
int time = 0;
for (int i = 0; i < 32; i++) {
Ant[] antArray = getAntList(getPoistions(), getDirections(i));
while (!isAllOut(antArray)) {
for (Ant ant : antArray) {
if (!ant.isOut()) {
ant.walk();
}
}
time++;
// 查看是否有已经相遇的Ant,如果有则更改其前进方向
dealEncounter(antArray);
}
System.out.println(time);
// 将时间归0,这样可以重新设置条件,再次得到全部走完所需要的时间.
time = 0;
}
}
/**
* 这个函数的算法很乱，但暂时能解决问题
*
* @param list
*/
public static void dealEncounter(Ant[] antArray) {
int num_ant = antArray.length;
for (int j = 0; j < num_ant; j++) {
for (int k = j + 1; k < num_ant; k++) {
if (antArray[j].isEncounter(antArray[k])) {
antArray[j].changeDistation();
antArray[k].changeDistation();
}
}
}
}
/**
* 因为有5只Ant，所以组合之后有32种组合.刚好用5位二进制来表示,如果为0则表示Ant往0的方向走 如果为1,则表示往27的方向走
*
* 注:在通过Ant的构造函数设置初始值时,通过过滤把0修改成了-1.
*/
public static int[] getDirections(int seed) {
int result[] = new int[5];
result[0] = seed % 2;
result[1] = seed / 2 % 2;
result[2] = seed / 4 % 2;
result[3] = seed / 8 % 2;
result[4] = seed / 16 % 2;
System.out.println(“directions is ” + result[0] + “|” + result[1] + “|”
+ result[2] + “|” + result[3] + “|” + result[4]);
return result;
}
/**
* 批量设置Ant的初始位置,这样设置不是十分必要,可以直接在代码中设置
*
* @return
*/
public static int[] getPoistions() {
return new int[] { 3, 7, 11, 17, 23 };
}
/**
* 取得设置好初始值的5只Ant
*
* @param positions
* @param directions
* @return
*/
public static Ant[] getAntList(int[] positions, int[] directions) {
Ant ant3 = new Ant(positions[0], directions[0]);
Ant ant7 = new Ant(positions[1], directions[1]);
Ant ant11 = new Ant(positions[2], directions[2]);
Ant ant17 = new Ant(positions[3], directions[3]);
Ant ant23 = new Ant(positions[4], directions[4]);
return new Ant[] { ant3, ant7, ant11, ant17, ant23 };
}
/**
* 判断是否所有的Ant都已经走出了木杆,也就是设置退出条件
*
* @param antArray
* @return
*/
public static boolean isAllOut(Ant[] antArray) {
for (Ant ant : antArray) {
if (ant.isOut() == false) {
return false;
}
}
return true;
}
}
编程：
用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。
2 编程：
用C语言实现函数void * memmove(void *dest,const void *src,size_t n)。memmove
函数的功能是拷贝src所指的内存内容前n个字节
到dest所指的地址上。
3 英文拼写纠错：
在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包
含了正确英文单词的词典，请你设计一个拼写纠错
的程序。
(1)请描述你解决这个问题的思路;
(2)请给出主要的处理流程，算法，以及算法的复杂度;
(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。
4 寻找热门查询：
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串
的长度为1-255字节。假设目前有一千万个记录，
这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个
。一个查询串的重复度越高，说明查询它的用户越多，
也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
(1)请描述你解决这个问题的思路;
(2)请给出主要的处理流程，算法，以及算法的复杂度。
5 集合合并：
给定一个字符串的集合，格式如：
{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}
要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应
输出
{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}
(1)请描述你解决这个问题的思路;
(2)请给出主要的处理流程，算法，以及算法的复杂度
(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。
////////////////////////////////1
1 题
char *revert(char * str)
{
int n=strlen(str);
int i=0;
char c;
for(i=0;i
{
c=str;
str=str[n-i];
str[n-i]=c;
}
return str;
}
///////////////////////////////////
2 题
void * memmove(void *dest,const void *src,size_t n)
{
assert((dest!=0)&&(src!=0));
char * temp=(char * )dest;
char * ss=(char * )src;
int i=0;
for(;i< p=“”>
{
*temp++=*ss++;
}
return temp;
}
/////////////////////////////////////////////////
3 题
(1)思路 :
字典以字母键树组织，在用户输入同时匹配
(2)
流程:
每输入一个字母：
沿字典树向下一层，
a)若可以顺利下行，则继续至结束，给出结果;
b)若该处不能匹配，纠错处理，给出拼写建议,继续至a);
算法:
1.在字典中查找单词
字典采用27叉树组织,每个节点对应一个字母,查找就是一个字母
一个字母匹配.算法时间就是单词的长度k.
2.纠错算法
情况:当输入的最后一个字母不能匹配时就提示出错,简化出错处理，动态提示
可能 处理方法:
(a)当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议;
(b)当前字母拼写错误：当前字母的键盘相邻作为提示;(只是简单的
算法面试题中经常出现的一种题目就是查找或者是排序. 个人感觉有80%的题目都和查找排序有关，大部分常用的排序算法时间复杂度都是O(nLogn)。这个只能说是通用解,一般解，对于算法面试题中往往要求很低的时间复杂度。
例如下面这个题目
已知一个数组长为m 中间存放的都是整数 其值范围为1-m ,中间的元素有可能重复 也有可能不重复
如何在O(M)的情况下查到 (1-m)的数中 哪些数重复了,哪些数没有出现
counting sort 的本质是 新建一个长度为M的数组An 每一个数组下标代表一个数 ,数组中的值代表这个元素出现的次数 (初始值都为0)
那么, 遍历一次m 遇到一个数 就在对应的下标上加1
那么最终可以得到一个An 其中包含了所有元素的出现个数
将其展开 就可以获得排序完的数组
这是一种特殊的算法,只能解决特殊的问题 但是他的时间复杂度是O(n)
如果在你遇到排序 或者查找之类的算法题的时候,不如上去先试试counting sort
相关文章分享：
四大非常规性面试问题 五大最棘手的面试问题 九种最难缠的面试题
1.java 基础题,输入结果是什么?
public static void main(String[] args) {
String str = new String(“abc”);
char[] ch = {‘a’,'b’,'c’};
change(str,ch);
System.out.print(str+” “);
System.out.print(ch);
}
public static void change(String str,char[] ch){
str = “gbc”;
ch[0] = ‘g’;
}
2.HashMap,Hashset,ArrayList以及LinkedList集合的区别,以及各自的用法
3.Activity的启动模式有哪几种
4.介绍Handler机制
5.线程考核,解析sleep,wait,join,yield方法,以及notify 和notifyAll是如何控制线程同步的
6.android 存储方式以及各至用法
7.ListView 中BaseAdapter的使用和优化;在ListView中的item放置一个按钮,如何使用按钮对不能的item响应不同的事件
8.编程题:
题意:生成一个1-100的随机数组,但数组中的数字不能重复,即位置是随机的,但数组元素不能重复
笔试题目就只能记住这么多了.
由于笔试时间是在晚上,麦洛答好题目才交卷,时间大概用一个半小时(感觉其他人答得非常快,有的没有半个小时就交卷了).
总体上,麦洛感觉笔试题目还是比较简单的,只要平时稍微注意学习,这些题目都不是很难.
百度评卷的效率也是很高的,麦洛刚从茂业大厦(百度深圳研发中心)出来不多久,就电话通知进入面试了.第二天面试时,被麦洛瞄到了答卷的分数,93分!
面试的第一轮是第二天9:00开始,在酒店里.因为深圳这边的研发中心刚刚建立起来,面试官都是从北京飞过来的.第一轮面试的面试官,应该也是 Android工程师,这一轮问的题目基本都还行.就是其中一个题目是说,监听数据库变化的一个接口,这个接口麦洛用的比较少,所以没有答上来,就是 ContentObserver这个接口.
这一轮的题目:
1.以前做过项目的,画个简单的架构图,介绍之前的项目;
2.项目中遇到的问题,以及怎么解决的.麦洛就举了之前写的上拉下拉这个控件的例子
3.Android Activity生命周期
4.Adapter中View重用的问题
就回忆起这么多了
第一轮讨论的话题是项目比较多,都是介绍项目经验之类的.
这一关讨论了一个多小时,顺利通过.
第二轮还是面试,是另外一个工程师来面试,就是面试官交换面试.
这一轮难度其实也不是特别大,但是因为问到几个麦洛没有做过的东西,被卡住了一下.
能回忆起的题目有:
1.介绍Http协议
2.Http协议实现多线程下载并支持断点续传,以及服务端是怎么支持的?
3.面向对象的理解,面向对象的原则C开发封闭原则的理解
4.android wap与net的两种连接方式
5.项目中的一些问题
这一轮主要是一些java基础知识,以及项目中的一些问题
两轮下来一个上午就过去了.麦洛也感觉精疲力尽了.然后就是吃午饭,等待第三轮面试了.
第三轮是比较轻松了.这一轮的面试应该是部门老大级别的了.随便聊聊,说说为何离职,以及有什么问题需要问的,大概半个小时就搞定了.
然后就回去等通知,要1周到两周时间.OMG!麦洛可不想等那么久啊
从笔试到面试总体感觉其实不是特别的难,只要做好准备平时注意积累,很多问题都是很好回答的.
第一题
简评
百度的主要业务是搜索，搜索的基本原理如下
1.编写爬虫程序到互联网上抓取网页海量的网页。
2.将抓取来的网页通过抽取，以一定的格式保存在能快速检索的文件系统中。
3.把用户输入的字符串进行拆分成关键字去文件系统中查询并返回结果。
由以上3点可见，字符串的分析，抽取在搜索引擎中的地位是何等重要。
因此，百度的笔试面试题中，出现这样的题就变得理所当然了。
以下是该题的java实现，代码如下：
程序代码 程序代码
import java.net.*;
import java.io.*;
import java.util.*;
/** * @author tzy * 在j2sdk1.4.2下测试通过 */
public class FileNameStat{
private String srcPath;//要统计的文件路径
private Map statMap;//用于统计的map
public FileNameStat(String srcPath)
{
this.srcPath=srcPath; 软件开发网 www.mscto.com
statMap=new TreeMap;
}
/*获得要统计的URL的文件名*/
public String getFileName(String urlString)
{
URL url=null;
String filePath=null;
String fileName=null;
try
{
url=new URL(urlString);
filePath=url.getPath();
int index=0;
if ((index=filePath.lastIndexOf(“/”))!=-1)
{
fileName=filePath.substring(index+1);
}
else
{
fileName=”";
}
}
catch(MalformedURLException e)
{
}
return fileName;
}
/*统计指定文件名的个数*/
public void stat(String filename)
{
Integer count=null;
if(statMap.get(filename)!=null)
{
count=(Integer)statMap.get(filename);
count=new Integer(count.intValue()+1);
}
else
{
count=new Integer(1);
}
statMap.put(filename,count);
}
/*统计的主方法*/
public void start() throws FileNotFoundException,IOException
{
BufferedReader bfin=new BufferedReader(new FileReader(this.srcPath));
String temp=null;
while((temp=bfin.readLine())!=null)
{
stat(getFileName(temp));
}
}
/*输出统计结果*/
public void result()
{
Iterator it=statMap.entrySet().iterator();
while(it.hasNext())
{
Map.Entry entry=(Map.Entry)(it.next());
System.out.println((entry.getKey().equals(“”)?”空文件名”:entry.getKey()) + “的个数是” + entry.getValue());
}
}
public static void main(String[] args) throws Exception
{
FileNameStat fns=new FileNameStat(“src.txt”);//指定成待统计文件
fns.start();
fns.result();
}
}
第二题
简评：
这道题也与百度的业务有关，百度现在除了搜索外，还有贴吧，知道，博客等重要产品。 同时也在积极的探索社区化，包括前不久宣布进军电子商务领域，搜索之外的这些产品，其主要功能的实现主要是对数据库的操作。 因此，想进入百度，也需要对数据库有一定的认识。 实现思路及数据库设计： 1，该论坛主要有两个实体对象，用户和帖子;对于帖子对象，有一个问题：回复的帖子是否应该跟主题帖子存放在同一个表里?
考虑到每天更新10万帖子，说明帖子数比较多，为了方便主题的呈现，我一般都把主题贴和回帖分别放在不同的表中，把主题贴和回帖分开可以提高查询效率(300万的访问量每天)。
2，按照1中的思路，该论坛由两个对象(用户和帖子)变成三个实体对象，分别是用户，主题帖子，回复帖子;
3，上述三个对象存在三个关系，分别是：
用户C主题帖，一个用户可以发0个或多个帖子，一个帖子对应一个用户(一对多关系)，
主题帖C回复帖：一个主题有0个或多个回复帖子，一个回复帖子对应一个主题(一对多关系);
用户C回复贴：一个用户可以回0个或多个帖，一个帖子对应一个用户(一对多关系)。
还存在对回复贴的回复，这个考虑用fatherId来表示。
4，由于三个关系 “用户C主题帖，主题帖C回复帖，用户C回复贴” 都是一对多关系，根据表设计一般原则，可以将这两个关系独立建立表，也可以不另外建表而将一对多的关系体现在实体表中;然而，表间的连接查询是非常耗资源的，所以应尽量减少表间连接，那么对三个关系不应该分别建表，而是把用户的id作为主题表和回帖表的外键，把主题贴id作为回帖表的外键。
5，鉴于以上考虑，该论坛的三个表如下所示
表名：t_user_info (用户信息表)
字段名 类型 缺省值 中文含义 约束 备注
id Int 用户编号 PRI Auto_increment
Name Varchar(30) 用户名
Email Varchar(50)
Phone Varchar(30)
Addr Varchar(200)
其他字段略，根据需要添加 表名：main_content_info (主题帖信息表)
字段名 类型 缺省值 中文含义 约束 备注
id Int 贴编号 PRI Auto_increment
Title Varchar(200) 发帖标题
Content Text 发帖内容
UserID Int 用户编号 外键
其他字段略，根据需要添加
表名：sub_content_info (回复贴信息表)
字段名 类型 缺省值 中文含义 约束 备注
id Int 贴编号 PRI Auto_increment
Title Varchar(200) 发帖标题
Content Text 发帖内容
UserID Int 用户编号 外键
FatherID Int 父编号
MainID Int 主题帖编号 外键
其他字段略，根据需要添加
6，符合范式分析：
上述表中每个字段不可再分，首先满足1NF;
然后数据库表中的每个实例或行都是可以被惟一地区分(id)，不存在部分依赖，因此满足2NF;
t_user_info (用户信息表)和main_content_info (主题帖信息表)不存在任何传递依赖，至少属于BCNF;
但是sub_content_info (回复贴信息表)不满足3NF,因为存在如下传递依赖：idC>FatherID,FatherIDC>MainID。
范式并不是越高越好，sub_content_info表只满足2NF却更有效率，也是当今论坛较主流的设计。
第三题
简评：
如何对海量数据进行快速检索，这是搜索引擎的必需考虑的问题。这又涉及到数据结构和算法。 因此，要想进入百度，就必须熟悉一些基本的算法和数据结构。 思路及解决方案如下：
1: 设计用TRIE树实现关键词到其对应id的快速词典查找
TRIE树的每一个节点为一个包含256个元素的数组，同时指针指向其下一级节点
节点定义如下：
struct trienode
{
int id;
struct trienode *child[256];
}TRIENODE;
如果TRIE树的某个节点的指针为NULL，说明从跟节点到当前节点的路径构成文件B中的一个关键词，
在其节点的id保存该关键词的id;如果指针不为NULL，则id对应为0或者一个无穷大的整数，标志从根节点
到当前节点的路径不是一个完整的关键词。
将关键词转化为二进制无符号char型数组，即对于汉字等双字节字符视为两个无符号char型整数，
每个元素的取值范围在0到255之间。
2：生成文件b的TRIE树
步骤1：依次读取文件b的每一行，对每一行执行步骤2到步骤5
步骤2：读取关键词id和关键词，令为key
步骤3：依次读取key的每一个字符，对每一个字符，执行步骤4;
步骤4：如果该字符对应的指针为NULL，则创建其儿子节点;
步骤5：为当前节点的对应字符id置为关键词id
3：根据A文件生成C文件
步骤1：依次读取文件A的每一行，对每一行执行步骤2到步骤5
步骤2：分别获取当前行关键词、ip地址和时间
步骤3：令关键词key=c1c2…cm，对c1到cm每个字符，执行步骤4
步骤4：获取根节点的第c1个元素指针，转移到节点node1，
根据node1的第c2个元素指针，转移到node2…
根据nodem的第cm个元素，获取关键词的id
步骤5：往文件c中写入一行数据，格式为关键词的id、ip地址和时间
4：复杂度分析
生成文件B的TRIE树过程时间复杂度为O(n*m)，其中n为文件b行数，m为文件b关键词的最大长度。TRIE的空间复杂度为O(n*m)，n和m含义同上，但由于实际应用中关键词之间可能会有很多前缀相同现象，所以实际耗费空间并不会很高。
生成C文件的时间复杂度同样为O(n*m)，n为文件a行数，m为文件a关键词的最大长度，因为有了TRIE树之后，给定一个关键词获得其id的时间复杂度为关键词长度。生成C文件的过程除了TRIE树空间外基本不需要太多额外的空间，空间复杂度为O(1)，由于系统有1G的可用内存，TRIE占用的空间在几十兆到200M之间(与关键词集合有关)，因此本方法完全可行。
一面(1 hour)：
1. 面试官从简历里抽了一个较感兴趣的项目，让把项目简单介绍了下，针对项目问了几个技术问题
2. 介绍Java中垃圾回收机制，程序员平时需要关注这个吗?为什么?请举例说明。
3. 数据库隔离级别介绍、举例说明。
4. override和overload的区别。
5. 求二叉树的最大距离(即相距最远的两个叶子节点)，写代码。
6. 两个栈实现一个队列，写代码。
7. 你觉得你的优势是什么?有什么技术薄弱点吗?
8. 目前手上有offer吗?
二面(40 minutes)：
1. 详细介绍研究生期间的小论文项目。
2. 求二叉树的宽度，先简介思路再写代码。
3. Hashmap、Hashtable和cocurrentHashMap的区别，要讲出它们各自的实现原理才行，比如Hashmap的扩容机制、cocurrentHashMap的桶分割原理、多线程安全性。
4. 进程调度算法，有哪些算法比较难实现?
5. linux下如何修改进程优先级?(nice命令的使用)。
6. linux下性能监控命令uptime介绍，平均负载的具体含义是什么?建议看server load概念。
7. linux下如何调试程序?说到gdb，具体如何调试?如何查看core文件中的堆栈信息等(bt指令)。
三面(1 hour and twenty minutes)：
1. 介绍我研究生期间的论文，讲的很详细，每个点具体采用的技术、实现方法等，花了较长时间。
2. 打印二叉树两个叶子节点间的路径，写代码(汗，百度这么喜欢问二叉树)。
3. 字符串中第一个只出现一次的字符，如何优化算法使得遍历次数更少?
4. socket编程相关，如果服务器这边调用write写了100个字节的数据，客户端想要获得这个数据，是直接用read系统调用，参数也是100吗?
5. 百度新闻缓存预算问题：一般为了追求时间性能，都需要缓存一些新闻数据，你怎么计算所需预算?然后申请需要的主机……
6. 多线程的适用场景是什么?为啥要用多线程?
7. 问是否会go语言，……
8. 为啥对技术感兴趣，一些相关问题讨论。
9. 聊北京、谈offer。
最后面试官说像计算机体系结构、操作系统这样的书一定要看国外的，国内的有时候会误导人。
总结
三面都是技术面，总体下来没有特别难的题目，从我的面试情况来看，百度这次非常看重面试者对二叉树的掌握情况，还有所做的项目详细介绍。后面我会继续分享自己在面试过程中的一些个人经验和技巧。
★ 百度求职信
★ 数据库面试题
★ 学生会面试题
★ php 面试题
★ 医师面试题
★ 谷歌面试题
