这样的面试题，你会吗？（有奖）

无风之谷

获奖名单已公布，详情请看：http://bbs.chinaunix.net/thread-3630628-1-1.html

程序员求职找工作，谁也逃不掉做编程面试题，这样的面试题，你做过吗？
1，二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。



2，青蛙跳台阶问题
（1）一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
（2）一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？

活动流程：
1.请将你的答案跟帖回答
2我们邀请了何海涛老师对参与者的回复进行评选，将根据提交的思路及答案评选出5个获奖者。
3.获奖者均可获得图书《剑指Offer：名企面试官精讲典型编程题》1本。

活动时间：2011-11-30——2011-12-14

活动要求：
参赛者以跟帖的方式提交代码，相似代码以最先提交为准。
注：严禁抄袭，一经发现，取消评选资格；

zhedahht

sinoman 发表于 2011-12-22 16:42
第二问的结果和很多网友分析的一样，是2^(n-1)次方。没有得出这个结果的网友，可以用数学归纳法证明f(n)=f( ...

谢谢您的提醒。您说得对。之前的回复已做修改。

sinoman

第二问的结果和很多网友分析的一样，是2^(n-1)次方。没有得出这个结果的网友，可以用数学归纳法证明f(n)=f(n-1)+f(n-2)+...+f(2)+f(1)=2^(n-1)。

这里有错误吧，应该是 f(n)=f(n-1)+f(n-2)+...+f(2)+f(1) + 1=2^(n-1)

edshea

回复 131# zhedahht
第一题的函数的确设计得不好，用一维数组存更方便一些，传二维数组进去还是得提供第二维的长度。
第二题的第二问是可以不用辅助栈，但第一问还是有必要的：如果有多次查询，之前计算的结果可以复用，否则每次计算f(n)都得从f(1)和f(2)开始迭代。

午夜凋零

回复 118# zhedahht


谢谢老师的指点~
做题时没考虑效率，做完后看别的朋友的答案，才知道差距了，失败。。。

eliteforce

青蛙的题是斐波那契数列，很简单的

绝_影

学习

陈斌群

{:3_202:}

zhedahht

程序员求职找工作，谁也逃不掉做编程面试题，这样的面试题，你做过吗？
1，二维数组中的查找
在一个二维 ...
无风之谷 发表于 2011-11-30 11:52

    非常感谢大家关注、参与本次活动。刚才逐一拜读了大家的回复，很有收获，我看到了很多有意思的思路与讨论，学到了不少新方法。谢谢各位。

    接下来我会根据大家的思路的可行性、代码的完整性、时间效率以及答题的先后打分。最终的获奖结果随后由主办方公布。

    参考答案：

    第一题：本题是《剑指Offer——名企面试官精讲典型编程题》的第三个例题。书中的解题思路碰巧和这里22楼crazyhadoop的思路一致。暂时没有买书的朋友，可以到china-pub网上的免费试读样章（http://images.china-pub.com/ebook195001-200000/198770/ch02.pdf）的第38-42页中看到详细的分析以及代码。

    这一题很多网友都试图用二分法查找来解决。试图用二分法在对角线上做文章的朋友，可以参考一篇博客（http://blog.csdn.net/expp/article/details/7008972）。这是一个网友参加同一活动时（在新浪微博上举行）的解答。博客中有插图，分析很形象。

    第二题：第一问很多网友都分析出来了，它的规律是fibonacci数列。fibonacci数列不同的实现方式的时间效率大不一样。通常我们认为递归不是一个很好的办法。感兴趣的网友可以试着用递归的方法去就fibonacci的43项，看看需要很长时间才能算出结果。我在一篇博客（http://zhedahht.blog.163.com/blog/static/25411174200722991933440/）讨论了不同实现方式的效率。通常在面试的时候，面试官会期待基于循环的解法。基于矩阵乘法的O(lgN)的解法由于代码量很大，面试时一般不会作要求。

    第二问的结果和很多网友分析的一样，是2^(n-1)次方。没有得出这个结果的网友，可以用数学归纳法证明f(n)=f(n-1)+f(n-2)+...+f(2)+f(1)+1=2^(n-1)。由于是求2的乘方，写代码时可以通过移位运算符实现。这样效率比在一个循环里做乘法要快一些。

    这个题目也收录到了《剑指Offer——名企面试官精讲典型编程题》中了，是书中的第9个例题，在书中73-77页。

zhedahht

回复  zhedahht 22L的。代码很重要么
hbmhalley 发表于 2011-12-14 11:20

    谢谢你写出22L思路对应的代码。

    我的想法是，评判的时候我会根据思路、代码、以及先后时间，打个分数。您认为这样合理吗？