2018秋招freewheeljava笔试题,祝大家春招好运
历经两个多月,辗转波折,终于结束春招,拿到了自己满意的offer,先分享一份自己去年做的freewheel的java笔试题,面经稍后补上
问答题
方向选择:请选出以下你所中意的方向并做出排序( )
A. 分布式高性能视频广告投放引擎(C++/Go)
B. 大数据基础架构及数据产品(Go,Hadoop,AWS)
C. 广告投放和流量预测及策略优化(C++/Go)
D. 机器学习,算法(只考虑机器学习算法的同学请标明)
E. 核心业务系统开发(基于Web前端的全栈开发,Ruby,Go,Javascript)
F. 产品运维/运维开发
不定项选择题
1、对某二叉树进行先序遍历的结果为ABDEFC,中序遍历的结果为DBEFAC,则后序遍历的结果是( )
A. BDEFAC
B. DFEBCA
C. BDFECA
D. DBFEAC
2、在关系型数据库中,只有满足联接条件的记录才包含在查询结果中,这种联接为( )
A. 右联接
B. 完全联接
C. 内部联接
D. 左联接
3、在关系型数据库中,适合建立索引的字段有( )
A. 主键字段
B. 在WHERE句中的字段
C. 外键字段
D. 在SELECT句中的字段
4、TCP拥塞控制算法中,发送方在检测网络拥塞情况时,对发送速率的控制方式是( )
A. 乘性增,乘性减
B. 乘性增,加性减
C. 加性增,加性减
D. 加性增,乘性减
5、下列哪个IP不是用于内部网络的?( )
A. 10.0.0.1
B. 192.168.3.55
C. 205.0.35.26
D. 172.18.0.1
填空题
1、设哈夫曼树***有99个结点,则该树中有( )个叶子结点;若采用二叉链表作为存储结构,则该树中有( )个空指针域。
2、初始序列为1 8 6 2 5 4 7 3一组数采用堆排序,当建堆(小根堆)完毕时,堆所对应的二叉树中序遍历序列为( )
问答题
1、有一关键字序列(265,301,751,129,937,863,742,694,076,438),写出希尔排序的第二趟排序结果。(取增量为5,3,1)。
答:
初始状态:265 301 751 129 937 863 742 694 076 438
第一趟:265 301 694 076 438 863 742 751 129 937
第二趟:076 301 129 265 438 694 742 751 863 937
2、由用户态切换到内核态,是否切换了进程?为什么?
答:没有切换进程。
因为操作系统的很多操作会消耗系统的物理资源,例如创建一个新进程时,要做很多底层的细致工作,如分配物理内存,从父进程拷贝相关信息,拷贝设置页目录、页表等,这些操作显然不能随便让任何程序都可以做,于是就产生了特权级别的概念,与系统相关的一些特别关键性的操作必须由高级别的程序来完成,这样可以做到集中管理,减少有限资源的访问和使用冲突。Intel的X86架构的CPU提供了0到3四个特权级,而在我们Linux操作系统中则主要采用了0和3两个特权级,也就是我们通常所说的内核态和用户态。
运行于用户态的进程可以执行的操作和访问的资源都受到极大的限制,而运行于内核态的进程则可以执行任何操作并且在资源的使用上也没有限制。很多程序开始时运行于用户态,但在执行的过程中,一些操作需要在内核权限下才能执行,这就涉及到一个从用户态切换到内核态的过程。本文主要要介绍的就是这个过程。
这里再明确一个概念,每个进程都有一个4G大小的虚拟地址空间,在这个4G大小的虚拟地址空间中,前0~3G为用户空间,每个进程的用户空间之间是相互独立的,互不相干。而3G~4G为内核空间,因为每个进程都可以从用户态切换到内核态,因此,内核空间对于所有进程来说,可以说是共享的,不过这么说有些不太严谨,应该说内核空间中大部分区域对于所有的进程来说都是共享的,这不共享的小部分区域是存储所有进程内核栈的区域,为什么这么说,因为每个进程都存在一个内核栈,而各个进程的内核栈之间一定是不共享的。
答:当两个进程共享内存时,各自进程中虚拟内存页面是内存中一块专门的用于共享的内存区域(实际物理页面)的映射,也就是说操作各自进程的虚拟内存相当于直接操作所映射的物理内存页。
def bubble_sort(array) cur_len = array.length-1 while cur_len>0 idx = 0 while idx<cur_len if array[idx]>array[idx+1] array.swap!(idx,idx+1) end idx +=1 end end end
cur_len -=1
def bubble_sort(array) cur_len = array.length-1 flag=1 while cur_len>0 and flag==1 idx = 0 flag=0 while idx<cur_len flag=1 if array[idx]>array[idx+1] array.swap!(idx,idx+1) end idx +=1 end cur_len -=1 end end
def min_depth_recursive(root) if root = =nil return 0 end min_depth = -1 left_child_min = min_depth_recursive(root.left) right_child_min = min_depth_recursive(root.right) end
return min_depth
def min_depth_recursive(root) if root = =nil return 0 end min_depth = -1 left_child_min = min_depth_recursive(root.left) right_child_min = min_depth_recursive(root.right) min_depth= left_child_min< right_child_min? left_child_min+1: right_child_min+1 return min_depth end
Day 1:Pill #5
Day 2:Pill #8
Day 3:Pill #5
……
Day 200:Pill #40
附加问题:
哪一天最有可能第一次碰到半片的药?
(编程题)略
int max_sum(int ** matrix, int m, int n)
题目:求一个MN的矩阵的最大子矩阵和。
比如在如下这个矩阵中:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
拥有最大和的子矩阵为:
9 2
-4 1
-1 8
其和为15。 /
include <cstdlib> include <iostream> int maxSubArray(int * array, int len){ if(array == NULL || len < 1) return -1; int max = -10000; int b = 0; for(int i = 0; i < len; ++i){ if(b > 0){ b += array[i]; } else{ b = array[i]; } if(b > max) max = b; } return max; } int maxSubMatrix(int matrix[][4], int rowlen, int collen){ if(matrix == NULL || rowlen < 1 || collen < 1) return -1; int max = -10000; int array[collen]; for(int i = 0; i < rowlen; ++i){ for(int j = 0; j < collen; ++j){//init array to 0 array[j] = 0; } for(int j = i; j < rowlen; ++j){//from row i to row j for(int k = 0; k < collen; ++k){ array[k] += matrix[j][k]; } int maxarray = maxSubArray(array, collen); if(maxarray > max) max = maxarray; } } return max; } int main(int argc, char * argv){ int matrix[][4] = {{0,-2,-7,0},{9,2,-6,2},{-4,1,-4,1},{-1,8,0,-2 }}; int collen = sizeof(matrix)/sizeof(matrix[0]); int rowlen = sizeof(matrix)/(sizeof(collen) int matrix[][4] = {{0,-2,-7,0},{9,2,-6,2},{-4,1,-4,1},{-1,8,0,-2 }}; int collen = sizeof(matrix)/sizeof(matrix[0]); int rowlen = sizeof(matrix)/(sizeof(collen)sizeof(int)); //std::cout<<"rowlen : "<<rowlen<<"collen : "<<collen<<std::endl; int max = maxSubMatrix(matrix, rowlen, collen); std::cout<<"max : "<<max<<std::endl; system("pause"); return 0; }
- 共有N类目标人群Un,0≤n<N
- 给定M支广告Am,0≤m<M
- 对应广告的单次投放成本Pm,0≤m<M
*已知广告Ai,单次投放能够到达的目标人群Ui的人数为Ri,j
请描述并实现算法,满足(或证明无法满足): - 1.每类目标人群Uj被覆盖的人数大于等于阈值Sj
- 2.最小化总体广告投放预算
- 3.如果有解,输出每支广告的投放次数和总体投放预算;如果无解,输出“无解”
请按照如下顺序作答:
1.写出最小成本的公式
2.对约束条件建模
3.试计算下列用例
a.广告主希望用2支广告:
i. 广告1(单价13元)
ii. 广告2(单价23元)
覆盖3类目标人群:
i. “青年观众”490人
ii. “中年观众”1220
iii. “老年观众”160人
b.单次广告投放能够覆盖的人群数量如下: -
青年 中年 老年 广告1 5人 35人 4人 广告2 15人 20人 4人
- 4.用你熟悉的语言或伪代码描述算法
编程题(略)