【2018年必威体育精装版整理】C面试笔试必备题目.docx

1. 在linked list中找倒数第N个结点2. 倒转linked list3. 二叉树的结点有指向parent的指针，求最近公共祖先4. 给一个数组,如何打印该数组成员构成集合的全部子集合.5. 有两个字符串，一个是text,一个是command, Command有四种：?? ‘+’: 在text中前进一位?? ‘-’: 在text中后退一位?? ‘a’: 在当前位置插入一个字符，字符由command中的后一位决定‘d’: 删除当前字符?? 实现函数Process(string text, string command, string result);Coding题，大致要点:扫描一遍command,看看有多少加字符的command,再建一个满足大小要求的临时数组，copy text 在临时数组上进行操作，注意插入和删除的复杂度都是O(N) 6. 实现一个LRU的cache??? 数据结构：??? ? 插入新cache的算法:如果找到了，用splice函数将刚刚被访问的CacheEntry移到队首。 关于多线程，一般来说reader/writer lock不适用，因为reader也会更改LRU cache. 一种解决的办法是让每个线程拥有自己的cache.7. 两个排序的数组，求它们的交集8. 在二叉树中添加额外的两个指针（树可能非满），遍历整棵树并将同一层的结点用这两个额外指针连接起来9. 用一个给定的值partition一个数组，注意这个值不一定在数组中出现10. 用数组实现一个queue, 考虑以下一些内容：a)? 实现固定sizeb)? 实现可变size? 每次size不够用时，建一个更大的array并复制原有数据c)? 与linked list的实现相比，有什么好处和坏处？保证了操作恒定为O(1),但是内存有浪费，且不连续d)? 如何处理thread safe在queue被更改的情况下，使用locker Lock-free code, 11. 洗牌算法??? For i = 0 to n-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列都设为零，注意尽量少使用额外空间分成如下几步:扫描第M行和第N列，看(M,N)是否需要设为零 扫描每行和每列，在第M行和第N列记录对应的列和行的结果 扫描第M行和第N列，将其所对应的列和行记为零 处理(M,N) ?14. [Microsoft] 一个二维空间第一象限有很多点，怎么找出最外围的那些点？Graham扫描算法：选出y最小的起始点p0 将其它所有点按相对于p0的极角排序，记为p1,p2,…pN-1 将p0, p1, p2 push到栈 对余下的所有点： a)?? Px为栈顶的下一个点，Py为栈顶，当前点为Pib)?? 如果Py-Pi, 相对于Px-Py向右i.????? Pop栈ii.????? Push Pi到栈算法复杂为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] 一个linked list，每个节点除了正常next指针外，还有一个extra指针，这个指针可以指向链表中的任一节点，不同的extra指针可以指向同一个节点，extra指针也可能形成loop。问怎么复制这个结构。18. [Microsoft] 怎么组织字典，使得在解cross puzzle时可以很快得到满足条件的所有单词(比如所有第二个字母是o，第5个是H的单词）。不过这题算brain storm，不用写code.??? 按单词的长度不同，构造多个container对某一组长度相同的单词，构造多个index, 从(2,o), (5, H) 映射到单词（id）, 每一个collection保持有序，可以加快merge的速度?19. [Google] 如何设计binary tree和hash table的iteratorBinary Tree Iterator:假设是中序遍历的话，在iterator中保存一个遍历的状态