九月十月百度，迅雷，华为，阿里巴巴笔试面试六十题(第411~470题)（2）

问题导读
1、你如何理解面向对象是一种思想？
2、如何判定二叉树是否是有序二叉树？
3、怎样对一个数组中找出第二大的数？





本文接上一篇：九月十月百度，迅雷，华为，阿里巴巴笔试面试六十题(第411~470题)（1）

三.系统设计题
面向对象是一种思想，使用C语言来实现下列问题。
  1.如何定义一个类？
  2.如何创建以及销毁对象？
  3.如何实现类的继承？
题目来源：http://blog.csdn.net/cocoarannie/article/details/12691025。

10月14日，欢聚时代YY-2014校招软件研发笔试题



点评：类似上面第1题跟海量数据相关的笔试面试题，看这一篇文章即够：http://blog.csdn.net/v_july_v/article/details/7382693。更多题目请参见：http://blog.csdn.net/Arcsinsin/article/details/12714027。

输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

点评：求子数组的最大和这个问题，在本博客内的编程艺术系列第7章：http://blog.csdn.net/v_JULY_v/article/details/6444021 已有详细阐述，但那毕竟只是针对一维数组，如果数组是二维的呢？
                               
          
如果 “子数组” 并不只是一个二维数组或矩形，而是联通的元素(上下或左右相邻即视为联通)呢?
                               
          
再言之，如果是个轮胎呢？嘻



上述这些问题来源于邹欣老师的博客：http://www.cnblogs.com/xinz/p/3318230.html。而且事实上，去年本博客内也同样整理过这几个问题，如此文第
22题：http://blog.csdn.net/v_july_v/article/details/6855788。
给平面上的2n个点，怎么找一个圆包含其中的n个点？

10月17日，微策略2014校招笔试
1. coding判定二叉树是否是有序二叉树
2. 一个有序数组A（buffer足够大），和一个有序数组B，设计算法，merge两个数组后有序，不使用任何额外的内存空间。
3. 100个点灯问题，初始状态都是OFF，进行1000次试验，第x次，按动一下能被x整除，计算最终的状态是ON的点灯编号。Coding实现，设计两种方案，并分析时间、空间复杂度
4. Web, css3中 visibility="hide"(页面保留空间) 与 display="none"（页面不保留空间）有何区别?一般元素选择器有哪些？
   Padding, margin, height, width在图形中指什么？
一个干净的、轻量级的标签以及 结构与表现更好的分离，高级选择器是非常有用的。
Class选择器
Id选择器
属性选择器 [arr = xx] [att *= xx] [att ^=xx] [att $= xx]
伪选择器 first after before
5. Web性能改进方面的10个提议：涉及图片、js、css、client, server
6. 数字游戏：桌子上有数值为Number的数字，2个玩家，每个玩家可以选择减去有 Number中连续1,2，，，，位构成的数值，桌子上换成差值，循环下去。提出算法：第一个玩家应该怎么减去桌子上的数值，如果第一个玩家输，返回-1
7. 交换单链表中两个指针（提示不能直接交互单链表中值）
读者@fhljys留言提供：百度一面试题
磁盘里有100T的数据，每一个数据项有一个Key，数据项按key的升序排列，但是key不连续。每个数据项的大小不一样，但是都不超过1M，每一个数据项以特定的标识符结束。现在内存大小为256M，如何找到指定Key的数据项。
点评：具体思路就是二分查找，更多讨论请见：http://weibo.com/1580904460/AeVSDCdac?mod=weibotime。

10月17日，新浪2014校招应用开发笔试题




10月17日，360校招测试开发一面
1、写一个单例模式
2、怎么样对一个hashmap里的<key，value>根据key进行排序？
3、给出一个路径“D/test/test.txt”，其中记录了一个搜索结果“百度，关键词，结果1-10,360，关键词，结果1-10”，用程序实现把这两个搜索结果中出现相同关键词的搜索结果存入另一个文件中。
4、对一个数组中找出第二大的数
5、TCP的三次握手是怎样的过程，如果是两次握手会怎么样，四次握手呢？

美团2014校招二面
假设已有10w个敏感词，现给你50个单词，查询这50个单词中是否有敏感词。
点评：换句话说，题目要你判断这50个单词是否存在那10w个敏感词库里，明显是字符串匹配，由于是判断多个单词不是一个，故是多模式字符串匹配问题，既是多模式字符串匹配问题，那么便有一类称之为多模式字符串匹配算法，而这类算法无非是kmp、hash、trie、AC自动机、wm等等：http://stblog.baidu-tech.com/?p=418。
那到底用哪种算法呢？这得根据题目的应用场景而定。10w + 50，如果允许误差的话，你可能会考虑用布尔过滤器；否则，只查一次的话，可能hash最快，但hash消耗空间大，故若考虑tire的话，可以针对这10w个敏感词建立trie树，然后对那50个单词搜索这颗10w敏感词构建的tire树，但用tire树同样耗费空间，有什么更好的办法呢？Double Array Trie么？请读者继续思考。
谷歌面试题：输入是两个整数数组，他们任意两个数的和又可以组成一个数组，求这个和中前k个数怎么做？
点评：引用朋友Ben博客http://blog.csdn.net/tnndye/article/details/12857577 内的分析，“假设两个整数数组为A和B，各有N个元素，任意两个数的和组成的数组C有N^2个元素。
       那么可以把这些和看成N个有序数列：

              A[1]+B[1] <= A[1]+B[2] <= A[1]+B[3] <=…
              A[2]+B[1] <= A[2]+B[2] <= A[2]+B[3] <=…
              …
             A[N]+B[1] <= A[N]+B[2] <= A[N]+B[3] <=…
复制代码

        问题转变成，在这N个有序数列里，找到前k小的元素”：http://blog.csdn.net/v_JULY_v/article/details/6370650。

阿里巴巴二面：
两个字符串A、B。从A中剔除存在于B中的字符。比如A=“hello world”,B="er"，那么剔除之后A变为"hllowold"。空间复杂度要求是O(1)，时间复杂度越优越好。
点评：微博上一朋友@kanrence留言到：把B对应的字符在asc码表上置1，然后扫描A，表上置1的就A上删掉。或者如@齐士博Go所说asc的bitvector, O(m+n); 先把B映射到vecotr，再遍历A。这两种方法因为都是常数空间127，所以可以认为是空间复杂度O(1)，此外，还有别的什么方法么？位运算？更多讨论请见这：http://weibo.com/1580904460/AeNifo3tI?mod=weibotime。

创新工场面试
1、有一个int型数组，每两个相邻的数之间的差值不是1就是-1.现在给定一个数，要求查找这个数在数组中的位置。
2、一个字符数组，里面的字符可能是a-z、A-Z、0-9.现在要求对数组进行排序，要求所有小写字符放在最前面，所有大写字符放在中间，所有数字放在最后，而且各部分内部分别有序。
点评：面试中纸上coding能力尤为重要，且答题之前一定要跟面试官交流以彻底弄清楚题意，题目来源：http://blog.csdn.net/xiajun07061225/article/details/8882981。

10月17日，网易2014校招雷火游戏一面
1、i）

Class A{  
...  
};  
A *pa = new A();  
A *pas = new A[NUM]();
复制代码

1.delete []pas;                //详细流程  
2.delete []pa;                //会发生什么  
3.delete pas;                //哪些指针会变成野指针  
ii）、为什么不建议经常手动new和delete而以内存池取代
iii）、malloc函数本身涉及的几种系统调用
iv）、内存分配算法伙伴算法
整理自：http://www.itmian4.com/forum.php?mod=viewthread&tid=3753。

10月21日，唯品会2014校招南京站-数据挖掘与分析岗位笔试题目






来源：http://www.itmian4.com/forum.php?mod=viewthread&tid=3770。

2013巨人网络笔试题
1、双向链表
用C++实现一个双向链表（元素类型为int）,需支持
  a、两个链表之间的深拷贝
  b、两个链表的拼接
  c、从链表头插入/删除元素
  d、查找链表中的某个元素
  e、返回链表中指定下标的元素
2、图像旋转90度；上下行互换
其余题目参见：http://www.itmian4.com/forum.php?mod=viewthread&tid=3777。


10月21日，微策略MicroStrategy2014校招聘面试题
1、判断一个字符串是否回文
2、如何快速找出一个有序数组中a=i的那个元素
3、p是素数，p>=3,证明p(p^2-1)能被24整除
来源：http://www.itmian4.com/forum.php?mod=viewthread&tid=3780。


腾讯2014校招笔试题-广州站
简单题
1 请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在队列中所处的位置和变化，队伍可能随时有人加入和退出；当有人退出影响到用户的位置排名时需要及时反馈到用户。
2 A，B两个整数集合，设计一个算法求他们的交集，尽可能的高效。
其余题目参见：http://www.itmian4.com/forum.php?mod=viewthread&tid=3788。

网易2014校园招聘杭州
Java笔试题http://blog.csdn.net/hxz_qlh/article/details/13168267；
2014小米研发笔试(南京站)http://blog.csdn.net/thyftguhfyguj/article/details/13161339；
10月26日，2014年腾讯校园招聘技术类笔试题(杭州站) http://www.itmian4.com/forum.php ... &extra=page%3D1。

10月19日，合合信息科技-校园招聘笔试题


点评：上述第3题即为编程艺术第二章，见http://blog.csdn.net/v_JULY_v/article/details/6347454。
10月29日，奇虎360校招面试，一堆的基础题，详见：http://blog.csdn.net/wangyf101/article/details/14048333。

10月30日， UC2014校园招聘技术类笔试题


有无OJ的ID，或github的账号，或技术博客地址？
点评：快排实现见此文http://blog.csdn.net/v_JULY_v/article/details/6262915。更多题目见：http://blog.csdn.net/lujingbiao/article/details/13510299。

10月31日，58同城2014校园招聘笔试题


点评：着实没想到，58同城于2013年10月31日在纽约上市了，恭喜！毕竟他们的老总姚金波也是我湖南人。记得之前去这家公司面试过，面试官很好，即便一时半会答不上来，他也会耐心引导你一起思考，可惜的是最后跟人事谈待遇的时候，不给一点余地，所以，直接拒掉了，如果现在再面一次，人事还是那般，依然会再拒一次:-)。但，尽管如此，58还是值得朋友们选择。OK，更多题目见：http://blog.csdn.net/Hedy20120808/article/details/13766781。
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order。一句话，即为螺旋矩阵问题。
举个例子，给定如下的一个矩阵:

        [
                 [ 1, 2, 3 ],
                 [ 4, 5, 6 ],
                 [ 7, 8, 9 ]
        ]
复制代码

你应该返回：[1,2,3,6,9,8,7,4,5]。如下图所示，遍历顺序为螺旋状：


以下是一份参考代码：

class Solution {    
public:    
    vector<int> spiralOrder(vector<vector<int> >& matrix) {    
        vector<int> result;    
        if (matrix.empty()) return result;    
        ssize_t beginX = 0, endX = matrix[0].size() - 1;    
        ssize_t beginY = 0, endY = matrix.size() - 1;    
  
        while (true) {    
            // From left to right    
            for (ssize_t i = beginX; i <= endX; ++i)    
                result.push_back(matrix[beginY][i]);    
            if (++beginY > endY) break;    
  
            // From top down    
            for (ssize_t i = beginY; i <= endY; ++i)    
                result.push_back(matrix[i][endX]);    
            if (beginX > --endX) break;    
  
            // From right to left    
            for (ssize_t i = endX; i >= beginX; --i)    
                result.push_back(matrix[endY][i]);    
            if (beginY > --endY) break;    
  
            // From bottom up    
            for (ssize_t i = endY; i >= beginY; --i)    
                result.push_back(matrix[i][beginX]);    
            if (++beginX > endX) break;    
        }    
        return result;    
    }    
};  
复制代码

代码来源leetcode：http://discuss.leetcode.com/questions/29/spiral-matrix。
待续，11月5日中午..


后记
    有一点想不遗余力的特别强调：如果你是找软件开发相关的职位，那么基础第一，其次便是coding能力是否过硬，此决定你有多少资本/薪水/是在国内还是国外，最后才是算法，希望勿本末倒置。不少人总是有意无意忽视coding，以为虽coding能力一般，但算法好，抱有此种侥幸心理的最后都会发现得不偿失。不具备基本编程能力的人，永远无法真正迈进软件开发领域。

    再者，算上今年，本博客已经连续整理了4个年头的笔试面试题，从这些笔试面试题中，细心的朋友自会发现，每一年校招的很多编程题屡屡都是编程艺术系列上的原题，故我希望大家掌握的是一类题目的方法，而不是纠结于某一道题的标准答案。

    正因为方法比答案重要，所以编程艺术系列从最容易想到的思路开始讲起，一步步优化，而不是其它题解那样一上来就给你所谓的标准速成答案，面试亦如此。

    最后，除了程序员编程艺术系列外，再推荐一些资料、书籍和讲座给大家，供大家参考：

程序员编程艺术http://blog.csdn.net/column/details/taopp.html；
秒杀99%的海量数据处理面试题http://blog.csdn.net/v_july_v/article/details/7382693；
微软面试100题系列http://blog.csdn.net/column/details/ms100.html；
《编程之美》；
《剑指offer》；
《Cracking the Coding Interview: 150 Programming Questions and Solutions》，顺便贴个此本书的题解：http://hawstein.com/posts/ctci-solutions-contents.html，且其中文版《程序员面试金典》即将由图灵教育出版社出版；
我个人举办的专为帮助大家找工作的面试&算法讲座：http://blog.csdn.net/v_july_v/article/details/7237351#t26；
一个刷面试题的leetcode：http://leetcode.com/，顺便附带一个leetcode的题解供参考：https://github.com/soulmachine/leetcode；
程序员面试网站careercup：http://www.careercup.com/；
一个IT面试论坛：http://www.itmian4.com/。







作者：结构之法 算法之道
本文转载自：http://blog.csdn.net/v_july_v/article/details/11921021