一次面试经历

今天去面试。

在青旅睡了一晚上,第二天早上起来已经是十一点钟。在路上买了一组(四个)生煎包,在地铁站吃掉之后,就上了二号线。十二点半到了公司的楼下。在楼下坐了坐等到十二点五十分,就上去面试了。

一开始是 HR 面试。她问了我延毕的事情,我也就实话实说。然后接下来是讲了一下公司的业务和规模,还讲了一下薪资,但是我也不知道这边一般拿多少,就随便说了说,也没个定数。


然后是第一个面试官。他打电话给我面试过一次,当时问的问题我答得不是很好。他给我的感觉就是一个挺严肃的人,搞得我也挺紧张的。

一上来就是一个数据结构问题,不过挺简单的。

给出一个 M 行 N 列的矩阵,由 1 和 0 组成,每一行的 1 都出现在 0 前面,例如:

$$ \begin {bmatrix} 1 1 1 1 0 0 \\ 1 1 0 0 0 0 \\ 1 1 1 1 1 0 \\ 0 0 0 0 0 0 \\ 1 1 0 0 0 0 \\ …… \\ \end {bmatrix} $$

这样一个矩阵,求出它含有最多 1 的一行,和那一行 1 的个数。要求时间复杂度为 $O(M+N)$ 。

一般数据量小就直接暴力搜索咯,直接统计每一行的行数然后找到最大的就可以了。不过那就变成 $O(M*N)$ 了。现在我们要 $O(M+N)$ ,那就要按照折线搜索。就是保存每一行找到的最后一个 1 的列数 n ,然后进入下一行的时候不从头开始搜索,而是从刚刚保存的那个 n 列开始搜索。

我一开始直接找到最多的那一行就输出结果了,但是面试官问我如果有多行有一样个数的 1 该怎么办,我就加了后面那个循环。不过他又问我能不能在一个循环里面搞定。刚刚又写了一下,还热乎着,放上来:

如果用 a[i][j-1] == 0 来判断是否有更多的 1 ,那么在第一行的时候应该会 out of range ,所以改成了 j+1


然后怎么说呢,这个面试官一直翻看手里的文件,也不提问题,我就很尴尬,但是我也不知道该说什么。不过还是问了几个东西。

当时我是用 C++ 写的,然后我跟他提到在一次循环里做完的方法就是每次发现更多 1 的行的时候就 clear ,他就问我 C++ 里的 vector::clear() 函数会不会调用析构函数。这个我就没答上来,但是我知道 clear 的时候 vectorcapacity 是不会减小的,只有 size() 会减小。回来搜索之后知道了 vector::clear() 是会调用析构函数的。写一个程序看看:

会看到第一次 push_back 的时候没有输出。第二次有输出一个 Test des 。第三次输出了两个 Test des。而在最后 clear 的时候输出了三个 Test des。前面的输出是因为 vector 在发现空间不够了的时候,就会重新分配空间,把原有的删除,分配方式是原来的空间乘以二。


接下来提到上次电话面试的时候说到的如何发现系统中的反弹 shell 。可惜我上次电话面试完之后查问题把这个忘了,于是还是没有答出来,很是尴尬。接下来会写一个文章专门总结这个东西。

后来扯到 Linux 里的 fd 的问题,他问我 fd 是一个 int ,那是不是从 0 开始的。我当时紧张得忘了,其实 0 就是 stdin , 1 是 stdout ,2 是 stderr


接下来是另一个面试官。跟我聊了我做的项目和实习的经历。聊到实习的时候做的东西的时候,我说到大端小端的问题,面试官让我现场写一个程序判断当前的系统是大端还是小端,我开始还觉得是要 printf ,但是后来我缓过神来意识到应该是强制类型转换:


接下来是另外一个题:

给出一个二叉树,对每一个节点增加一个兄弟指针,让它链接到同一层的右边的节点。如果它是这一层的最后一个节点,那就链接到下一层的第一个节点。

其实就是一个广度优先搜索,为了响应女王殿下的号召,多花十几分钟写出来放在这里:


其实这个面试很多东西都是随便提的。他们并没有一个确定的题库,他们会在面试的过程中根据你的经历随时抛出问题。但是算法题应该是准备好的,虽然都不难。我还以为现在的公司都会考红黑树,还好没有考红黑树……

不过还是感觉凉了。其实明天那个公司我也不想去了,但是既然有面试机会,那就去面试一下吧。年后再去深圳找找其他的工作。我最开始来这里是为了去另一个公司,但是他们没要我,我感觉再来这里意义不大。因为我其实不是很喜欢这个地方,虽然它发达,现代化,但是我在这里感觉并不好。

CC BY-NC-SA 4.0 一次面试经历 by James & Alice is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

一次面试经历》上有3条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据