20秋 后台开发 小红书 一二三四面

2020年9月20号

一面 下午2点

自我介绍

1.对一个长度为n的数组，给定k( 1≤k≤n)，求长度为k的连续子数组的平均值的最大值。如果k不确定，怎么做？

2.连续子数组的最大和

3.连续子数组的最大乘积

4.有1000个日志文件，每个日志文件中有很多按照时间顺序排列的记录，每条记录的格式为“时间 日志内容”。给定一个时间范围[t1, t2]，找出范围内所有的日志记录，并按照时间从小到大的顺序排列，如何实现？

二面 下午3点15

自我介绍，交流项目

1.给定两个用字符串表示的正整数，计算这两个数相减的结果，返回字符串表示的结果

2.Java的垃圾回收机制

3.走迷宫问题，如何求出所有可能路径？如何找出最短路径？

三面 下午4点30

自我介绍，交流项目

1.有一个矩阵，每个格子里有一定数量的金币，只能往右下走，求从左上角走到右下角能获得最多的金币数量。

2.给定一个正整数N，可以印刷任意面值的纸币无数张。给出一种方案，使得印出的纸币数量最少，且可以表示出1..N的所有整数（例如N=10，至少需要印面值为1、2、3、4的纸币各一张）

给了一个穷举的方法，最多可以印N张1块的纸币嘛，然后可以列出所有可能的方案再一一检验，时间复杂度大约是O(n!)    (*╹▽╹*)

面试官给了点提示，我想出了一个方案：最少需要印出⌊log₂N⌋ + 1 张，印刷方案是1、2、4、8... 2ᵏ 各印一张，这样就可以表示从1 - 2^(k+1)的所有数，最后再印一张面额为N - 2^(k+1)的纸币即可

如何证明这个是最优解？（真的想不出来...）

面试官说这个是他之前参加面试的时候被问到的题目，这道题还有后续的问题，如果现在已经有了一些面额的纸币若干张，最少需要补印多少张其他的纸币呢？

HR面 下午5点30

自我介绍

对前几轮面试的评价

如果大学可以重来，你打算怎么度过

介绍下之前的实习经历

从上一段实习中学到了什么

目前有哪些offer

HR表示过一段时间会发意向书