资源描述：
《c 面试笔试必备题目》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1.在linkedlist中找倒数第N个结点2.倒转linkedlist3.二叉树的结点有指向parent的指针，求最近公共祖先4.给一个数组,如何打印该数组成员构成集合的全部子集合.5.有两个字符串，一个是text,一个是command,Command有四种： ‘+’:在text中前进一位 ‘-’:在text中后退一位 ‘a’:在当前位置插入一个字符，字符由command中的后一位决定‘d’:删除当前字符 实现函数Process(string&text,string&command,strin
2、g&result);Coding题，大致要点:1.扫描一遍command,看看有多少加字符的command,再建一个满足大小要求的临时数组，copytext2.在临时数组上进行操作，注意插入和删除的复杂度都是O(N)6.实现一个LRU的cache 数据结构： 插入新cache的算法:1.如果找到了，用splice函数将刚刚被访问的CacheEntry移到队首。关于多线程，一般来说reader/writerlock不适用，因为reader也会更改LRUcache.一种解决的办法是让每个线程拥有自
3、己的cache.7.两个排序的数组，求它们的交集8.在二叉树中添加额外的两个指针（树可能非满），遍历整棵树并将同一层的结点用这两个额外指针连接起来9.用一个给定的值partition一个数组，注意这个值不一定在数组中出现10.用数组实现一个queue,考虑以下一些内容：a) 实现固定sizeb) 实现可变size 每次size不够用时，建一个更大的array并复制原有数据c) 与linkedlist的实现相比，有什么好处和坏处？保证了操作恒定为O(1),但是内存有浪费，且不连续d) 如何处理thread
4、safe1.在queue被更改的情况下，使用locker2.Lock-freecode,11.洗牌算法 Fori=0ton-1,生成一个i到n-1之间的随机数j，将v[i]与v[j]交换 12.[Microsoft]对stack上的元素排序，可以使用的方法有pop(),top(),push(),isEmpty(),isFull().13.[Microsoft]有一个M*N行的矩阵，如果第(i,j)个元素是0，则把i行和j列都设为零，注意尽量少使用额外空间分成如下几步:1.扫描第M行和第N列，看(M,
5、N)是否需要设为零2.扫描每行和每列，在第M行和第N列记录对应的列和行的结果3.扫描第M行和第N列，将其所对应的列和行记为零4.处理(M,N) 14.[Microsoft]一个二维空间第一象限有很多点，怎么找出最外围的那些点？Graham扫描算法：1.选出y最小的起始点p02.将其它所有点按相对于p0的极角排序，记为p1,p2,…pN-13.将p0,p1,p2push到栈4.对余下的所有点：a) Px为栈顶的下一个点，Py为栈顶，当前点为Pib) 如果Py->Pi,相对于Px->Py向右i.
6、 Pop栈ii. PushPi到栈算法复杂为O(NlogN)(第二步的排序) 15.[Google]返回一组字符串的最长公共前缀，如“abc”,“abcdef”,“abcd”,则返回”abc”16.[Microsft]给出平面上第一象限内landscape的轮廓，也就是一些列的(x,y)坐标,x=0,1,…,N，以及Y轴上光源坐标(0,H)。问这N+1个点钟那些被照亮那些是阴影。(叉乘)一一计算光源到(x,y)的角度，再与左边的角度对比即可知是否被遮挡，复杂度O(N)17.[Microsoft]
7、一个linkedlist，每个节点除了正常next指针外，还有一个extra指针，这个指针可以指向链表中的任一节点，不同的extra指针可以指向同一个节点，extra指针也可能形成loop。问怎么复制这个结构。18.[Microsoft]怎么组织字典，使得在解crosspuzzle时可以很快得到满足条件的所有单词(比如所有第二个字母是o，第5个是H的单词）。不过这题算brainstorm，不用写code. 按单词的长度不同，构造多个container对某一组长度相同的单词，构造多个index,从(2
8、,o),(5,H)映射到单词（id）,每一个collection保持有序，可以加快merge的速度 19.[Google]如何设计binarytree和hashtable的iteratorBinaryTreeIterator:假设是中序遍历的话，在iterator中保存一个遍历的状态(parentnodestack).HashTableIterator:取决于hashtable的数据结构，一般直接按array或者bucket顺序遍历就可以了
