一次刺激的面试和笔试

继续总结经验教训

由招文桃在2019年9月21日发布

前言

那是经历的第一次面试,绿米联创 HR 面,2019 年 9 月 20 日下午 3 点,在华南理工大学(大学城校区)的图书馆底下的 O’Clock Coffee 咖啡厅。本来此前一天(2019 年 9 月 19 日)晚上 7 点参加了绿米联创的宣讲会,紧接着是 8 点多左右进行线下笔试,笔试时间为一个小时。题目难度中等,其中有“关灯开灯”问题(同 TCL 第 21 题),然后又有经典的输入网站按下回车键到浏览器显示网页经过了什么过程。还有一题是两个人轮流取硬币,最先取完的为胜…… 这类型题目,以前在看 BBC 一个关于算法的纪录片(Algorithms - The Secret Rules of Modern Living - BBC documentary)时候有看到,但是没有记住其中道理,因为到时已经有人翻译制作了中文字幕,所以我就没有翻译了,结果就是印象不够深刻。

那晚宣讲会加线下笔试,错过了腾讯的在线笔试,在一个没什么灯光的路边阶梯坐下,抱着笔记本,摄像头监考,光线不好,操作不了,而且后台综合的试题全部是编程题,在剩余的不到 20 分钟内根本就不可能完成,直接提交了空白卷,连自信心被打击的机会都没有了,题目印象也没有,因为根本看不见什么,早知道找个光线好的教室坐着什么的,但是第一次去到华工校园,不熟悉环境。

原本约的下午 3 点开始的面试,提前了十多分钟开始,持续了大概半小时。不过面试结束之后我赶紧拿出笔记本,坐到旁边的桌开始做网易的在线笔试题,这也是下午 3 点开始的。被面试占用了一些时间,后面就不够时间做在线笔试题了,最后十几分钟电池没电直接关机(因为调成高性能状态,且不设置电量少提示)。奇怪我也没有直接放弃,虽然知道最后也是么有办法做完和有机会通过笔试,但还是想办法继续完成考试。当时就走进咖啡厅里面询问是否有插座可以接电,还好有个位置可以充电接着完成考试。

下午 5 点结束了网易笔试,为了节省时间就没去食堂吃饭,在咖啡厅吃个三明治算了,因为接下来 7 点还有商汤科技的在线笔试。商汤的笔试就比较针对 Java 了,有选择题、填空题和简答题。这次也是使用牛客网的考试系统,但是监考过程比腾讯和网易的多了一个手机小程序监控的步骤,还要录屏的。商汤试题刚开始的选择题涉及比较多数据结构的内容,二叉树什么的,填空题有涉及看代码写输出结果的。最后简答题好像有 9 个题,比较多 x 与 y 的区别之类的问题,例如 session 与 cookie 的区别,ArrayListLinkedList 的区别,手写单例设计模式,常见的设计模式,Java 的原子类作用和原理, 还有关于 Java 虚拟机内存模型的, volatile 关键字的作用,后面的没时间,没有写完,中间网络出现点问题,中断一会。但也尽力做,开始有点感觉了,继续加油。

题目回顾

回顾一些错题,包括日常练习和在线笔试的。

日常练习

  • 一个以”.java”为后缀的源文件:

    只能有一个与文件名相同的 public 类,可以包含其他非 public 类(不考虑内部类)。

基础概念要清晰。

  • 关于 equals()hashcode() 的,对象属性之类的东西。

下面论述正确的是()?

A. 如果两个对象的 hashcode 相同,那么它们作为同一个 HashMap 的 key 时,必然返回同样的值

B. 如果 a, b 的 hashcode 相同,那么 a.equals(b) 必须返回 true

C. 对于一个类,其所有对象的 hashcode 必须不同

D. 如果 a.equals(b) 返回 true,那么 a,b 两个对象的 hashcode 必须相同

答案是 D 解释如下:

如果两个对象的 hashcode 相同,那么它们作为同一个 HashMap 的 key 时,必然返回同样的值。如果 a, b 的 hashcode 相同,那么 a.equals(b) 必须返回 true,对于一个类,其所有对象的 hashcode 必须不同,如果 a.equals(b) 返回 true,那么 a,b 两个对象的 hashcode 必须相同。

  • 关于计算机网络

如果在一个建立了 TCP 连接的 socket 上调用 recv 函数,返回值为 0,则表示()

A. 对端发送了一段长度为 0 的数据

B. 对端关闭了连接

C. 还没有收到对端数据

D. 连接发生错误

基础,对于 TCP 协议的认识,解阻塞与非阻塞 recv 返回值没有区分,都是

< 0 出错

= 0 连接关闭

< 0 接收到数据太小

  • 关于 JavaBean 的,还有一些 JSP,旧的技术还没有完全淘汰,有时候有必要了解一下。

笔试回顾

题目原表述和空间要求等已经记不清,凭回忆和草稿恢复题目如下:

输入 $T$ 组数,格式为第 1 行是组数 $T$ ,余下每行 1 个数 $x$ ,对每个 $x$ 求输出对应的 $n$ ,满足 $x \leq S(n)$ 的最小值。其中 $S(n)$ 表示 $n$ 的十进制各位之和, $1 \leq T \leq 10$, $1 \leq x \leq 10^5$。

示例输入

2

13

18

示例输出

49

99

Java实现
import java.util.Scanner;

public class Exam1 {

    public static void main(String[] args) {

        Scanner stdIn = new Scanner(System.in);
        int T; // 组数

        do {
            System.out.print("请输入数据组数T(1 <= T <= 10):");
            T = stdIn.nextInt();
        } while (T < 1 || T > 10);

        int[] x = new int[T]; // 输入的x

        for (int i = 0; i < T; i++) {
            do {
                System.out.printf("请输入第%2d 组的 x(1 <= x <= 100000):", (i + 1));
                x[i] = stdIn.nextInt();
            } while (x[i] < 1 || x[i] > 100000);
        }

        for (int number : x) {
            System.out.print((number % 9 == 0) ? "" : (number % 9));
            for (int i = 0; i < number / 9; i++) {
                System.out.print(9);
            }
            System.out.println();
        }
    }
}
思考过程

考试的时候初步想法,输入数据组数 $T$ ,接下来每组的数保存在长度为 $T$ 的整型数组里面。 这只是输入数据的保存,接着就是核心算法部分,思考这个算法要做什么,要寻找什么规律,最终达到题目要求。

我是这样想的,首先实现对于每个 $x$ 可以找到满足条件的 $n$ ,接着再考虑怎么知道这个 $n$ 是最小的,判断的依据是什么?功能实现完善了,再考虑优化时间复杂度或空间复杂度。

初步来看,随着 $x$ 增大,符合条件的 $n$ 将会是一个很大的数,位数肯定超过 Java 支持的数据类型上限,这就是要考虑到的问题。 但可以先从小数入手,先实现在 $x$ 较小的情况下可以运行的程序,接着优化,添加可以处理大数的操作,使得在题目要求的数值范围内可以有效运行。最后才是细化优化。

后来观察了一下这些数字,发现规律很明显,不用很复杂的算法就可以实现了。首先题目要求对于给定的 $x$ 要找到满足 $x \leq S(n)$ 的 $n$ 的最小值,所以最小就是 $x = S(n)$ 的情形。列出一些 $x$ 和 对应的 $n$ 如下:

1 … 8 9 10 11 12 … 28

1 … 8 9 19 29 39 … 1999

发现满足要求的都是最高位是 1~8 其余位数全部是 9 的数字(不然不可能最小)。所以问题就转化成求 $n$ 的最高位是什么,余下位数共有多少个 9 ,即最高位是 $n$ % 9, 余下有 $n$ / 9 个 9。 因为 $x = 10^5$ 的时候,满足条件的 $n$ 长度是 “最高位的 1 ” + “ 后面11111 个 9 ”, 长度达到 11112 位。 因此用打印字符串作为结果输出。时间复杂度$O(n)$。

总结

这题和轮流取硬币的那题都涉及到余数相关的性质,感觉有趣,平时解题思维锻炼得少,有时候会将简单问题复杂化,要多练习,希望有提高。

最后

今天应该报名 Oracle 的 Oracle Certified Java Programmer(1Z0 - 808), 然后预约 2019 年 10 月 25 日上午 9 点的考试。今天开始到 2019 年底,还有 100 天,开始百日刷题计划。