百度2013年校园招聘题

「爱情、让人受尽委屈。」 2022-05-24 23:06 236阅读 0赞

第一题，基础题：  
1. 数据库及线程产生死锁的原理和必要条件，如何避免死锁。  
2. 列举面向对象程序设计的三个要素和五项基本原则。

解答：

封装，继承，多态

面向对象的五大基本原则
    单一职责原则（SRP）
    开放封闭原则（OCP） 
    里氏替换原则（LSP） 
    依赖倒置原则（DIP） 
    接口隔离原则（ISP）单一职责原则（SRP）

3.Windows内存管理的方式有哪些？各自的优缺点。  
第二题，算法与程序设计：  
1.公司举行羽毛球比赛，采用淘汰赛，有1001个人参加，要决出“羽毛球最高选手”，应如何组织这次比赛？可以使用伪代码。

解答：

堆排序或者竞标赛排序。

2.有100盏灯泡，第一轮点亮所有电灯，第二轮每两盏灯熄灭一盏，即熄灭第2盏，第4盏，以此类推，第三轮改变编号为3的倍数的电灯，第3盏，第6盏，如果原来那盏灯是亮的，就熄灭它，如果原来是灭的，就点亮它，以此类推，直到第100轮。问第100结束后，还有多少盏灯泡是亮的？

解答：

完全平方数。

3.有20个有序数组，每个数组有500个uint变量，降序排序。要求从这10000个元素中选出最大的500个。

解答：

可能是多路归并排序思想，用到了堆，使用了优先队列数据结构

#include <iostream>
    #include <cstdlib>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    #define ROWS 20
    #define COLS 500
    
    int data[ROWS][COLS];
    
    void CreateData()
    {
        for(int i=0; i<ROWS; i++)
        {
            for(int j=0; j<COLS;j++)
            {
                data[i][j] = rand();                         //生成随机元素
            }
        }
        for( int i=0; i<ROWS; i++)
            sort(data[i],data[i]+COLS, greater<int>());     //对每一行降序排列
    }
    
    struct Node 
    {
        int *p;  //指向某个列，因为要放入优先队列中，所以要比较大小，就用结构体封装了下
        bool operator<(const struct Node &node) const
        {
            return *p < *node.p;
        }
    };
    
    void OutMinData( int k)
    {
        struct Node arr[ROWS];
        for(int i=0; i<ROWS;i++)
        {
            arr[i].p = data[i];                       //初始化指针指向各行的首位
        }
        priority_queue<Node > queue( arr, arr+ROWS );  //使用优先队列，默认是大堆
    
        for( int i=0; i<k&&i<COLS; i++)                //算法核心就是这个循环
        {
            Node temp = queue.top();                   //取出队列中最大的元素
            cout << *temp.p << " " <<endl;            
            queue.pop();                               //从队列里删除    
            temp.p++;                                  //对应行的指针后移
            queue.push( temp );                        //这里面有log（ROWS）次操作，所以算法的总复杂度为O（klog（20））
        }
        
    }
    
    int main()
    {
        CreateData();  //生成数据
        int k=500;
        OutMinData( k ); //输出k个元素，这里k不要大于列数COL，可以改进，去掉这个限制，不过会让程序不好懂，就没加
    }

4.  字符串左移， void \*pszStringRotate(char \*pszString, intnCharsRotate), 比如 ABCDEFG ，移 3 位变 DEFGABC ，要求空间复杂度 O （ 1 ），时间复杂度 O （ n ）

#include <iostream>
    using namespace std;
    
    void ReverseString( char* pBegin, char* pEnd ){
    
    	while( pBegin < pEnd ){
    		char ch = *pBegin;
    		*pBegin++ = *pEnd;
    		*pEnd-- = ch;
    	}
    }
    
    char *pszStringRotate(char *pszString, int nCharsRotate){
    	char * end = pszString;
    	while( *end++ );
    	end = end-2;
    	if( pszString + nCharsRotate -1 > end ) return NULL;
    	ReverseString( pszString, pszString+nCharsRotate-1);
    	ReverseString( pszString+nCharsRotate, end);
    	ReverseString( pszString, end);
    	return pszString;
    }
    
    int main(){
    	char str[] = "ABCDEFG";
    	char *s = pszStringRotate( str, 3 );
    	if( s )
    		cout << s <<endl;
    	return 0;
    }

第三题，系统设计题：  
手机数字键上有拼音字母，一个数字串对应着多个字母序列，如2--ABC，6--MNO，9--WXYZ，则926对应着WAN，YAN，是汉字“万”、“艳”的拼音等。要求设计一个系统，输入是联系人列表UserList<UserName, PhoneNo>，汉字字母映射Dict，数字串NumStr，输出满足下列条件的联系人列表ResultList<UserName, PhoneNo>：  
（1）输入一个数字串，输出与其部分连续匹配的所有手机号，如，输入926，输出13926118288  
（2）输入一个数字串，输出与其部分连续匹配的所有联系人姓名拼音，如输入926，输出“李万”，“李艳”等

解答：

1，字典树

2，哈希表

2.2的解答：

[http://gzcsl.blog.163.com/blog/static/4103020088244441761/][http_gzcsl.blog.163.com_blog_static_4103020088244441761]

这道题让人一看觉着非常有趣，但又让人感觉很复杂，其实这道题，只要弄清三点，问题就迎刃而解了。  
1．对于每盏灯，拉动的次数是奇数时，灯就是亮着的，拉动的次数是偶数时，灯就是关着的。  
2．每盏灯拉动的次数与它的编号所含约数的个数有关，它的编号有几个约数，这盏灯就被拉动几次。  
3．1——100这100个数中有哪几个数，约数的个数是奇数。我们知道一个数的约数都是成对出现的，只有完全平方数约数的个数才是奇数个。

所以这100盏灯中有10盏灯是亮着的。  
它们的编号分别是： 1、4、9、16、25、36、49、64、81、100。

[http_gzcsl.blog.163.com_blog_static_4103020088244441761]: http://gzcsl.blog.163.com/blog/static/4103020088244441761/