这样的面试题，你会吗？

1、有300层高楼与2个玻璃杯，玻璃杯从x层掉落摔到地面刚好摔碎(x层以下是摔不碎的)，请问至少需要多少次摔杯子试验就一定能够找到x层是第几层？

2、5000个数中找出3个数，使它们和的绝对值最小，求算法与时间复杂度。

3、在2×n的一个长方形方格中(高：2,宽：n),用一个1× 2的骨牌铺满方格(高：1,宽：2 / 高：2,宽：1),输入n ,输出铺放方案的总数.
例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：

|----|----|----|
|    |    |    |
|  1 |  3 |  5 |
|----|----|----|
|    |    |    |
|  2 |  4 |  6 |
|----|----|----|

A方格:高：1,宽：2
B方格:高：2,宽：1
方案1：(1,2)放入B、 (3,4)放入B、 (5,6)放入B
方案2: (1,2)放入B、 (3,5)放入A、 (4,6)放入A
方案3：(1,3)放入A、 (2,4)放入A、 (5,6)放入B

4、从1-N这N个数中任意取3个数使这三个数之和为Sum，其中N<Sum<3N，求共有多少种组合方式，请给出算法与时间复杂度。（注：1+2=3与2+1=3只能算一种组合方式）

5、一个字符串，长度为200，字符串的每个位置上只能出现A T G C四个字符中的一个，每个位置上的四种字符出现的概率不同，要求计算出生成概率最大的前50个字符串，请给出算法与时间复杂度。
例如长度为6的相关概率数据：
位置 1 2 3 4 5 6
A 0.2 0.3 0.1 0.55 0.25 0.3
T 0.3 0.5 0.6 0.25 0.25 0.1
G 0.1 0.05 0.2 0.2 0.25 0.4
C 0.4 0.15 0.1 0 0.25 0.2

1、有编号为1-N的N个房间，从左到右，每个房间分别有一台机器(重量各不相等)，现在要求把这些机器按照重量重新分配房间，重量从左到右依次递增。移动机器只能做交换操作，但交换机器要花费一定的费用，费用的大小就是交换机器重量的和。问怎样移动机器才能使排序的费用最小。

 

2 假定有这样一个游戏，规则定义如下:
游戏的基本元素是25个字母。游戏开始，玩家会获得一定目的字母，可能有重复的字母。比如两个A,一个B。
玩家把这些字母排成一行，两个字母相邻会有一定分值，本次游戏的得分为所有相邻字母的分值的和。
比如假定a-a 100 a-b 101。一次游戏的字母为两个A,一个B,则排成a-b-a得到最大的分数为202。
给定了字母之间的分值计算游戏能取得的最大分值，一次输入的字母数量不超过20。

3 有一副特别扑克牌,有26*3张,每张扑克牌的点数为A-Z，扑克牌没有花色,相同点数的有3张。随机从扑克牌里抽30张出来，去掉里面的成对的点数相同的牌(比如抽6张牌得到A,A,A,B,B,C成对去掉点数相的牌后得到A,C)，最后剩下5张牌的概率为多少?最后剩下6张牌的概率为多少?

4、定义一种数列，它的定义如下
s(x) = 0 (x<0)
s(x) = 1 (0<=x<1)
s(x) = s(x-1) + s(x-3.14) (x>=1)

现在需要计算出s(x) (x为浮点数)

1)、求s(x) MOD 1000000007的值，x < 1000
2)、求s(x) MOD 107的值，x < 2^31
3)、求s(x) MOD 1000000007的值，x < 2^31
请分别给出以上几问的算法与时间复杂度

5、5个不同的自然数N1 N2 N3 N4 N5，其中N1 < N2 < N3 < N4 < N5，并且满足 N1^2 + N2^2 + N3^2 + N4^2 + N5^2 = N1 * N2 * N3 * N4 * N5

1）、求符合条件的1组N1,N2,N3,N4,N5
2）、求符合条件的100组N1,N2,N3,N4,N5
3）、求N5 < 100000的解的数