笔试题

20170913腾讯

1 输入4个数a,b,A,B，按一次左按钮可以使a,b同时*2，按一次右按钮可以使a,b同时+1，求最少的按按钮次数使得a,b变成A,B。如果不存在变换方法则返回-1。

2 有一堆钱1 1 2 2 4 4 ... 2^k 2^k ,也就是2的各次幂的钱都有两个。现在买一样价值为n的物品，求有多少种钱的组合方式。

3 输入n*n的二维表，表示每个结点到其他各结点的时间，无向连通图，结点0到结点1的时间==结点1到结点0的时间。一魔法师从结点0前往节点1，他可以使用k次魔法，每次魔法可以使两个节点间的时间缩短一半，求魔法师从0到1的最短时间。

20170913招银信用卡中心

1 输入两个数和k，求这两个数的不大于k的公倍数的个数。

2 输入一个数组（身高），AB两个人从左边开始取数，每次可以取1个数或2个数，直到取完所有数，AB两个人各自取的数之和大者获胜。令A先取，如果A获胜输出true，如果A失败输出false。

20170911百度

1营地摊位，求最小连通图

2给两个圆的坐标和半径，求重合面积

3拔植物问题，每天拔掉比左侧植物高的那些植物，求第几天就不用拔了

20170826阿里

1 给定一个字符串S和有效单词的字典D，请确定可以插入到S中的最小空格数，使得最终的字符串完全由D中的有效单词组成，并输出解。
如果没有解则应该输出n/a
例如

输入
S = "ilikealibaba"
D = ["i", "like", "ali", "liba", "baba", "alibaba"]
Example Output:
输出
"i like alibaba"

解释：
字符串S可能被字典D这样拆分

"i like ali baba"
"i like alibaba"

很显然，第二个查分结果是空格数最少的解。

中国历史上曾出现过多次诸侯割据的时期，诸侯之间通过各种方式派出间谍来刺探军情，留下了许多惊心动魄的谍战故事，其中有一个是这样的：A国在B国安插了多名间谍，有一次这些间谍刺探到B国将在T时间攻打A国，如果A国不做防备则A国必败；如果A国能提前埋伏则A国必胜，所以A国的间谍需要在T之前将情报安全的送回A国。为了避免情报被B国截获而取消攻打计划：A国的间谍采用了一种特殊的编码算法，会将情报编码在m份数据中，只有同时拿到至少任意的n份数才能解码出情报；这m份数据会由m个间谍分别送出，避免同时被B国捕获。由于输送情报的过程中要躲避B国的随机检查，输送情报的时间是不固定的，A国间谍已经将之前情报的输送时间都记录下来。A国间谍需要估算出A国拿到完整情报时间的期望值。
注：为了简单起见，m个间谍都会成功的把各自的情报送回A国；所耗费的时间是独立的。
概念抽象：A国间谍记录的情报输送时间的情况：会记录每个时间总共出现的次数，以Point结构表示：

struct Point
{
 int value; // 情报输送时间
 int num; // value出现过的次数。
 double ratio; // value在所有情报输送占的概率。
};

20170824亚马逊

1 图有N个节点，其中K个节点有苹果，多条边，约束为每条边只能经过一次，可从任意点出发，求最多可以得到多少个苹果。

2 输入一个01串，可以将其中的k个0变为1，求有多少种方法可以得到最长的连续1串。

3 在一个有N个节点的图上，已知部分节点之间的边和距离，其中节点表示城市，边表示城市间有道路相连并有相应的距离。一魔法师可以施放K次魔法，每次魔法可以瞬间从一城市到达相连的另一城市，求魔法师从给定出发点到达给定终点所需要走过的最短距离。

20170822今日头条

1 输入多个点坐标，定义最大值为某点坐标均大于其余点横纵坐标，找出所有最大值的点并输出。

2 输入数组，定义区间值 = 区间内数字和 * 区间内最小数字，求该数组的最大区间值。

3 产品经理有若干idea，每个idea有4个属性：产品经理id、提出时间、优先级、完成所需时间。输入为产品经理人数、程序员人数、idea数、多个idea。程序员在空闲时，需要从多个idea中挑出优先级高的、完成所需时间少的、提出时间早的idea。输出每个idea的完成时间。