Author Archives: yo2superhaiou

1.从海量数据中找出最大的500个数，在协作平台直接写出代码。这道题的解法我就不赘述了，好说不好写，折腾了半个小时才写好； 2.二分查找，查出最接近某个数的index最大的那个数，这个题相对比较简单； 3.在二叉树中找出离两个结点最近的公共父结点，我Coding的思路是：用两个栈，先深度优先找到两个结点，栈保存路径，然后弹出较大的栈中多出的结点，然后两个栈再同步弹栈比较，相同即return。 4.在一个M*N的格式里，在某些位置有礼物，一只鸟从第一个格子出发，每次只能往右或往下飞一格，求出该鸟取得最多礼物的路径。 这是一道典型的动态规划题，我的思路是先找出递归式，由于时间关系，我用递归写了一个程序，就没改成动态规划了，然后说了一下动态规划的思路，也算OK。 5.关于字符串的全排列，这个很经典，前段时间才写过，所以几分钟就写出来了，这些经典题大家还是准备一下好。主要思路就是先拿一个字符和另一个字符swap，然后递归全排列，处理完后swap回来，继续循环处理； 6. 一堆数，如{1, 2, 3, 4, 5, 6}，一共N个，在中间加M个加号，使得和最大。这也是个DP的问题。这是二面时的第三道题，前两道题写了程序，这道就讲了思路：先找递归式，就是把所有 数分成两部分（有多个位置，用一个循环），两部分分别用i个加号和M-i个加号，然后再比较出一个最大的和。 7.一个数组，去掉最小的数使得该数 组先递增再递减，这个题的思路就是使用最大递增子序列的做法，先求最长递增子序列，然后再把余下的数reverse再求最长递增子序列；再把这个过程放到 一个循环里比较就可以求出最佳答案。这个时间复杂度比较高，大家可以给出更优的方案，洗耳恭听。 8.C/C++/Java中的 serialize 和deserialize，这是Foreigner面试给我出的第一个题。关于序列化和反序列化我只在Java开发过程中用过，首先写了一个 serialize的类，然后写了WriteObject和ReadObject的方法，然后再调用这两个方法。不过他说不能用文件，就重新让我写了一个 字符串通过序列化在网络上编码解码的程序，这个还好，在Java里主要调用了new String[byte[], encode]和String.getBytes(encode)两个方法。 9.也是Foreigner出的题，如何比较两棵二叉树所有结点的结构和值都一样(同构)，这个题相对比较简单，用C++写好程序后，他不是太满意，提了一些问题我没听懂，就over了。 10. 一个开放性试题：一个QQ程序在手机上跑，从登录到使用，如何设计后台服务器保证整个流程的安全性。这个题我答得不好，最后他还问我数字签名、各种加密算法等，没答好。我说不是学信安的，面试官就说“你不是过了系统分析师和信息系统项目管理师么？”，因为这点还问了我关于UML建模的东西，如聚合和组合的 区别等，最后还问了“一致性哈希”。 11.一个逻辑题：8*8的方格，去掉左上角和右下角的两个方格，问能否用2*1的方格覆盖？解决方案：对方格涂色，黑的和白的相邻，最后总会有两个黑的或白的相邻。 12. 一个文件有100万条数据，每一行包含姓名、年龄两部分，如何按年龄对所有的数据排序？这个题就非常简单了，按年龄1-100分为100个桶，然后把相应 年龄的数据放到相应的桶，然后再对这些桶内的数据按姓名进行排序即可。假设采用Unicode对内容（可能包含中文）进行编码，整个过程需要的内存空间也 在数十兆的范围内。