百度面试总结

http://blog.csdn.net/zhaojinjia/article/details/12649823

面试官当时只给了一个小时的时间,只写了一个链表反转的程序还问了其他一些,列举下来,希望网友看看下面,有新思路,请交流一下,谢谢。

1:实现带头结点的链表反转问题

     两种方法:递归和非递归实现

[cpp] view plaincopyprint?

  1. struct ListNode  
  2. {  
  3. int m_nKey;  
  4.     ListNode* m_pNext;  
  5. };  
  6. //非递归实现
  7. ListNode* ListReverse(ListNode* pHead)  
  8. {  
  9. if ( !pHead->m_pNext )  
  10. return pHead;       //如果链表只有头结点,直接返回头结点
  11.     ListNode *p1 = pHead->m_pNext;  
  12.     ListNode *p2 = p1->m_pNext;  
  13.     ListNode *p3;  
  14.     p1->m_pNext = NULL;      //这一步我面试时写程序落下了------注意一下
  15. while ( p2 )  
  16.     {  
  17.         p3 = p2->m_pNext;    //先保存p2的next指针,防止丢失
  18.         p2->m_pNext = p1;    //修改p2的next指针,改为指向p1
  19.         p1 = p2;            //p1向前移动
  20.         p2 = p3;            //p2向前移动
  21.     }  
  22.     pHead->m_pNext = p1;  
  23. return pHead;  
  24. }  
  25. //递归求链表反转,返回值当前链表的最后一个结点
  26. ListNode* RecursiveListReverse(ListNode* pNode, ListNode*& pHead)  
  27. {  
  28. if ( !pNode )   //当没有元素时处理
  29.     {  
  30. return pNode;  
  31.     }  
  32. if (!pNode->m_pNext) //当当前结点为最后一个结点时,找到头结点,固定不动
  33.     {  
  34.         pHead->m_pNext = NULL;  
  35.         pHead = pNode;  
  36. return pNode;  
  37.     }  
  38. else
  39.     {  
  40.         ListNode* temp = RecursiveListReverse(pNode->m_pNext, pHead);  
  41.         temp->m_pNext = pNode;  
  42.         temp = pNode;  
  43. return temp;  
  44.     }  
  45. }  
  46. void Traverse(ListNode* pHead)  
  47. {  
  48.     ListNode* pTemp = pHead->m_pNext;  
  49.     cout <<"output the list:   ";  
  50. if (!pTemp)  
  51.     {  
  52.         cout <<"空链表"<<endl;  
  53. return;  
  54.     }  
  55. while (pTemp)  
  56.     {  
  57.         cout << pTemp->m_nKey <<" ";  
  58.         pTemp = pTemp->m_pNext;  
  59.     }  
  60.     cout << endl;  
  61. }  
  62. //创建一个带头结点的链表
  63. ListNode* CreateList()  
  64. {  
  65.     cout<<"输入空格间隔,-1为结束表示 "<<endl;  
  66.     ListNode* pHead = new ListNode;     //建一个头结点
  67.     pHead->m_pNext = NULL;  
  68.     ListNode* p = pHead;  
  69. int data;  
  70. while ( cin>>data && data!=-1 )  
  71.     {  
  72.         ListNode* pNew = new ListNode;  
  73.         pNew->m_nKey = data;  
  74.         pNew->m_pNext = NULL;  
  75.         p->m_pNext = pNew;  
  76.         p = p->m_pNext;  
  77.     }  
  78. return pHead;  
  79. }  
  80. int _tmain(int argc, _TCHAR* argv[])  
  81. {  
  82.     ListNode* pHead = CreateList();     //建立
  83.     Traverse(pHead);                    //输出
  84.     pHead = ListReverse(pHead);         //链表反转
  85.     Traverse(pHead);                    //输出
  86.     RecursiveListReverse(pHead->m_pNext,pHead->m_pNext);  //递归链表反转
  87.     Traverse(pHead);  
  88. return 0;  
  89. }  

2:一个数组长度为N,且每个元素的范围是1到N+2,且不重复出现,那么1到N+2中肯定会有两个数字没有出现,要求用时间复杂度为O(n),空间复杂度为O(1)找出来。

     利用解方程思想:X+Y=一数,  X*Y=一数,可求出X和Y,但是当N较大时,这个方法不可取,求高效方法

3:虚拟内存(虚拟存储器)

     背景:常规存储器管理方式的特征:一次性和驻留性。

     虚拟内存提出原因:1:有些作业很大,无法一下全部装入内存;2:作业量很大,内存无法容纳所有这些作业,只能将少数作业装入内存,而将其他大量作业留在外存上。

虚拟内存是从逻辑上扩充内存容量解决问题的。

定义:具有请求调入功能和置换功能,能从逻辑上对内存容量进行扩充的一种存储系统。其逻辑容量由内存容量和外存容量之和所决定,其运行速度接近内存速度。

理论依据--->时间局部性:如果程序某条指令被指向,则不久以后该指令会再次执行;如果某数据被访问,则不久可能会被再次访问。原因:程序中存在大量循环操作空间局限性:一旦访问了某个存储单元,不久后,其附近的存储单元也将被访问,由于程序一般是顺序执行。     

     实现方法:有两种  分页请求系统   请求分段系统-------重点

     虚拟存储器的特征: 多次性、对换性、虚拟性

     页面置换算法:最佳置换算法、先进先出页面置换算法、LRU置换算法、clock置换算法、

4:存储器管理

存储层次至少应具有三级:CPU寄存器、主存(高速缓存,主存,磁盘缓存)、辅存。

用户源程序到内存中可执行程序分两步编译(将用户源代码编译成若干个目标模块),链接(将目标模块以及所需要的库函数链接,形成完整装入模块),装入(完整模块装入内存)

     程序装入方式:绝对装入、可重定位装入、动态运行时装入

     程序链接方式:静态链接、装入时动态链接、运行时动态链接

     连续分配方式:单一连续分配、固定分区分配、动态分区分配、动态重定位分区分配

内存管理方式:基本分页存储管理方式、基本分段存储管理方式、段页式存储管理方式

5:文件管理

6:OSI七层协议,网络层有哪些协议,TCP/Ip协议

7:已知有大量字符串,找出可以唯一标识每个字符串的前缀

例如:字符串为:abe、adef、aeg、ebg,那么它们的唯一标识前缀分别为:ab、ad、ae、e;

方法一:按照字符顺序排序,通过与其前后字符串比较计算其唯一标识前缀;

方法二:建立trie树

8:static virtual 类大小问题

[cpp] view plaincopyprint?

  1. class A  
  2. {  
  3. int a;  
  4. static int b;  
  5. virtual void f();  
  6. static void g();  
  7. void h();  
  8. };  

计算sizeof(A)=8

9:未排序的两个数组合并成一个数组。

求更高效方法

方法一:将两数排序,用二路归并进行处理

方法二:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏陈树义

(删)Java线程同步实现一:synchronzied和wait()/notify()

上面文章(2.Java多线程总结系列:Java的线程控制实现)讲到了如何对线程进行控制,其中有一个是线程同步问题。下面我们先来看一个例子: 1、一个典型的Jav...

32140
来自专栏Flutter入门

Weex是如何在Android客户端上跑起来的

Weex可以通过自己设计的DSL,书写.we文件或者.vue文件来开发界面,整个页面书写分成了3段,template、style、script,借鉴了成熟的MV...

63150
来自专栏菩提树下的杨过

用spring boot 2从零开始创建区块链

区块链这么火的技术,大java怎能落后,所以有了本文,主要代码参考自 Learn Blockchains by Building One , 中文翻译:用Pyt...

16420
来自专栏Netkiller

以太坊智能合约开发入门

中国广东省深圳市龙华新区民治街道溪山美地 518131 +86 13113668890 <netkiller@msn.com>

3.2K60
来自专栏向治洪

android 自定义Lint

概述 Android Lint是Google提供给Android开发者的静态代码检查工具。使用Lint对Android工程代码进行扫描和检查,可以发现代码潜在的...

313100
来自专栏aCloudDeveloper

LeetCode:146_LRU cache | LRU缓存设计 | Hard

题目:LRU cache Design and implement a data structure for Least Recently Used (LRU)...

25390
来自专栏刘望舒

LeakCanary看这一篇文章就够了

LeakCanary是Square公司基于MAT开源的一个内存泄漏检测工具,在发生内存泄漏的时候LeakCanary会自动显示泄漏信息。

3.7K50
来自专栏NetCore

Fluent NHibernate RC 1.0 --升级内容

Fluent NHiberante(FNT) RC 1.0 已经在上个星期发布了,其中很多东西被废弃,有些方法改进,还有一些命名更贴切,虽说不是很完美,但已经做...

21950
来自专栏数据结构与算法

P1576 最小花费

题目背景 题目描述 在n个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问...

36350
来自专栏大前端_Web

easyUI组件datagrid的二次封装

版权声明:本文为吴孔云博客原创文章,转载请注明出处并带上链接,谢谢。 https://blog.csdn.net/wkyseo/articl...

36630

扫码关注云+社区

领取腾讯云代金券