2013.5.24 某公司实习面试题

    昨天进行了实习生面试，长期的。本来报的图像识别，但是确实是不懂行，果然被调剂了。自动化测试组，不过做大数据分析和呈现，不是ML相关岗位，但应该有些问题是可以用ML来更好解决的，直觉这样认为。不说废话了，面试也是手写各种算法为主，应该是题库中的，准备的太少果然吃亏，当天出结果。给出记得的题目吧，还有解答。有的当时并没有答出最优解，下来好好想想还是值得的。

方便分开就都放到代码形式里面了。

 

1. 走台阶，一步只能走1或2个台阶，问n个台阶有多少种走法。
       当时我用二分的思路进行的，话说这条路走下来很复杂，虽然小数据是对的，但是数据一大就很复杂了。这个题是没答对的，不过下来想想从二分合并的思路深入想一下就可以发现这是动态规划问题，从1阶梯到n阶梯算一遍就ok了。   solve(n) = sovle(n-1) + sovle(n-2) n>2
       搜了下网上还有些其他解法，只看了两个，递归是肯定比动态规划差的，重复计算过多。另一个没仔细看。但目测是动态规划最优。

 

2. 输入一个String，和一个char，char表示键盘上的回退键，输入实际的输出。
其实就是获取键盘流后显示到显示屏上的问题。处理起来很简单，借用一个Stack，遇到此char pop一下，遇到的不是此char则push一个。Java的Stack也是Vector，所以输出也很容易，同时pop也不需要考虑栈空的情况。

 

3. 实现一个栈，获得最大值的时间复杂度是1
思路就是每次这个栈增加、删除一个元素都会改变最大值，另外根据只有pop、push操作，即只能操作栈顶节点考虑，实现另一个栈，记录每个栈顶元素对应的最大值。这里最大值记录编号int较省内存，如果存内容的话可能花费较大。

 

4. 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
关键是找对角线上的元素，找到最后一个小于x的，和第一个大于x的，把矩阵拆成四块，只保留左下和右上角部分，对这两部分继续操作，变成二分问题。

另外慢慢想想有个最好的解法，就是每个节点其实都有两个指示信息，但是需要选择往左-下，或者右-上的方向移动，对于任意一个位置，其左边小于它，下面大于它，相当于就有了一个决策方式。这样从右上角的元素开始，做此决策，比如找x，如果此元素大于x，则继续向下找；如果此元素小于x，则向左找，直到不能走了。这样就找到了，时间复杂度是O(n)