百度技术专员面试经历

面试： 1.判断一个链表是否存在回路? 给指针加一个标志域，如访问过则置1.当遍历到标志为1的项说明有了回路。 定义2个指针，一快(fast)一慢(slow)，即：从头向后遍历过程中，每循环一次，快指针一次向后移动2个元素，慢指针移动一个元素，每次判断( fast==slow || slow==fast->nest ),如果成立，说明慢指针赶上了快指针，则为循环链表，否则，如果有一个指针到达NULL，则为单链表。 重新做一个链表，用于存放所有原链表中的节点，插入节点时按按地址顺序插入， 如果出现相同的地址就说明是死链，结束查询.... 2.两个单向链表，有可能交叉，请设计算法判断是否交叉，如果交叉，返回交叉点！算法复杂度o(n) 两个链表最后是合并成一个 而不是交叉 所以： （1）先找到p1，p2的最后一个节点，同时记录节点数量a，b； （2）判断最后一个节点是否相同， 如果不相同则没相交。 如果相同 则从第一个节点和|a-b| 1个节点开始比较 看是否相等 不相等都寻找下一个节点 直到找到交叉点 3.硬盘文件系统设计，及磁盘整理算法 4.Hash表 5.php MySQL 6.问参加过ACM/数学建模没有 7.多边形标记问题： 判断点是否在多边形内的问题？ 我知道有两种方法： 1。累计角度法 过此点连接多边形的每一顶点，各相邻边角度之和为360度，则此点在多边形内。 否则为0度，在多边形外部。 2。射线法 过此点向任意角度发一条射线，若与多边形的各条边交点个数之和为偶数，则此点在 多边形之外，否则在多边形之内。 若有交点为多边形顶点则要另选一条射线重算。 请问哪种方法好一点（时间复杂度）？ 方法一对凹多边形可能会出现问题吧。 8.多线程 同步互斥的概念 同步：只有a做完才能做b。 互斥：a和b只是在一个时间做一个。 可用p,v操作来实现。 相交进程之间的关系主要有两种，同步与互斥。所谓互斥，是指散步在不同进程之间的若干程序片断，当某个进程运行其中一个程序片段时，其它进程就不能运行它们之中的任一程序片段，只能等到该进程运行完这个程序片段后才可以运行。所谓同步，是指散步在不同进程之间的若干程序片断，它们的运行必须严格按照规定的某种先后次序来运行，这种先后次序依赖于要完成的特定的任务。 显然，同步是一种更为复杂的互斥，而互斥是一种特殊的同步。 例: ... s=1; i=0; cobegin p1(); p2(); endbegin p1(){ while(未完成){ p(s); i ; printf("%d",i)； v(s); } } p2(){ while(未完成){ p(s); i--; printf("%d",i)； v(s); } } p1(),p2()是两个进程。i 和i--分别是两个程序片断。在没有执行完p1（）是不允许执行p2()的。这里的p1()和p2()并不是指一个完整的进程，只是两进程的公共资源（临界资源）. 当程序1调用程序2时，程序1就停下不动，直到程序2完成回到程序1来，程序1才继续下去，这就是所谓的“synchronous”,即同步。如果程序1调用程序2后，径自继续自己的下一个动作，那么两者之间就是所谓“asynchronous”，即异步。Win32 API中的SendMessage()就是同步行为，而PostMessage()就是异步行为。 同步机制有critical sections(关键区域、临界区域），mutex(互斥器），semaphore(信号量），event(事件）。 在同步机制中，critical sections是指一小块“用来处理一份被共享之资源”的程序代码，这里所指的资源，并不是指来自.RES(资源文件）的Windows资源，而是广义的指一块内存，一个数据结构，一个文件，或任何其他具有“使用之排他性”的东西。也就是说，资源每一次（同一时间）只能被一个线程处理。 mutex的用途和critical sections非常类似，但是它牺牲速度已增加弹性。 其它两个我就不再说了，这些在《Win32多线程程序设计》中第四章同步机制中有详细的讨论和例子。 “临界” 该段代码属于原子操作 “同步” 一般是双方协调，如一方等待 “互斥” 不能一起执行 “临界状态” 处于临界状态的代码段一个时间段只允许一个进程访问 “同步” 多个进程之间协调对某些临界资源的访问顺序 “互斥” 当某个线程访问某个临界资源的时候，不允许别的线程同时访问此资源 怎样才能实现线程的同步与互斥？ EnterCriticalSection LeaveCriticalSection CreateSemaphore ReleaseSemaphore WaitForSingleObject SetEvent WaitForSingleObject Mutex... CSyncObject是MFC中解决互斥同步问题的基础类 常用4种 关键代码段——单进程内 互斥量——互斥 信号灯——充许设定一个以上共享资源 事件内核对象——灵活