美团2015校园招聘研发笔试题.pdfVIP

NOWCODER.COM 牛客网-中国最大IT笔试/面试题库 美美团团2015校校园园招招聘聘研研发发笔笔试试题题 一. 单项选择题 1. 美团有个传统，就是公司各部门每月都 组织员工进行一次团建互动(team building ，简称TB) ，每个员工 都可以带家属参加。活动内容出了吃喝玩之外，还 做一些互动的游戏，需 从员工中随机选出几名组成一 队来完成游戏。一次TB活动，一共有20个人(含员工和家属)参加。已知如果随机选取3位员工以及该3位员工 的家属，一共有220组合。问如果每次随机选取4个员工及该4位员工的家属，会有多少组合? A 405 B 455 C 495 D 505 二. 问答题 2. 一组随机排列的字母数组。请编写一个时间复杂度为O(n)的算法，使得这些字母按照字母从小到大顺序排 好。 说明：字母区分大小写，相同的字母，排序后小写排在大写前。 例如：R，B，B，b ，W ，W ，B，R，B， 排序为：b ，B，B，B，B，R，R， ，W ，W 1)描述思路(2分) 2)请用你熟悉的编程语言编码实现(8分) 2 3 n 3. 给定整数x ，定义函数A(n)=1+x+x +x +…+x (n为整数且n=0).已知乘运算的时间远大于加运算，输入 x ，n;如何尽可能快的求出A(n)? 求： 1)描述思路(2分) 2)评估你的算法需 进行多少次乘法?(3分) 3)请用你熟悉的编程语言编码实现(5分) 4. 实现方法：print_ rotate_ matrix(int[] matrix, int n), 将一个n×n二维数组逆时针旋转45度后打印，例如，下图 显示一个3×3的二维数组及其旋转后屏幕输出的效果。 描述思路(2分) 请用你熟悉的语言编码显示(8分) 牛客出品-http:// .no NOWCODER.COM 牛客网-中国最大IT笔试/面试题库 5. 已知队列(Queue)支持先进先出的操作add/remove ，而栈(Stack)则支持先进后出的操作push/pop ，请用两个 队列实现栈先进后出的操作，希望该栈的push/pop时间复杂度尽量小。 1) 简述思路(3分) 2) 已知这两个队列的容量为M,该栈的容量是多少(1分) 3) 假设队列的每次Add/ Remove操作时间复杂度O(1) ，N代表存储在栈里的元素个数，请评估该栈的push/pop 操作时间复杂度(1分) 4) 写出push/pop的代码，需 考虑栈溢出(stackoverflo )的情况(3分) 6. 任务务调度在分布式调度系统中是一个很复杂很有挑战的问题。这里我们考虑一个简化的场景：假设一个 中央调度机，有n个相同的任务需 调度到m台服务器上去执行。由于每台服务器的配置不一样，因此服务器 执行一个任务所花费的时间也不同。现在假设第i个服务器执行一个任务需 的时间为t[i]。 例如：有2个执行机a, b. 执行一个任务分别需 7min ，10min ，有6个任务待调度。如果平分这6个任务，即 a ，b各分三个任务，则最短需 30min执行完所有。如果a分这4个任务，b分2个，则最短28min执行完。 请设计调度算法，使得所有任务完成所需的时间最短 1) 简述思路 2) 请用你熟悉的编程语言编码实现以下方法，输入为m台服务器，每台机器处理一个任务的时间为t[i] ，完成n个任务，输出n个任务在m 台服务器的分布： int estimate_process_time(int[] t, int m, int n); 7. n个元素{1，2 ，……，n}有n!个不同的排列。将这n!个排列按字典序列排列。并编号为0 ，1，……，n!-1。 每个排列的编号为其字典序的值。例如，当n=3是，其字典排序为：123 ，132 ，213 ，131，312 ，321，这6 个数的字典序值分别为0,1