笔试

三道编程题

题一

题意

给一个N*M矩阵,站在一个固定点,一开始有一把长度为L的大刀，每个格点有个不同值V，如果大刀能砍到这个格点,大刀长度加V问最后大刀的长度。

当时做法:

把固定点到其他点的距离排序，从小到大贪心即可。

题二

题意

有N个数，一开始每个数在一个不同集合里，有如下三种操作
1.把X和Y所在两个集合合并。
2.把X从当前集合分离。
3.输出X所在集合大小。
进行M次操作

当时做法

开N个vector。
操作一:小的集合合并到大的集合里
操作二:把X当前集合尾元素交换，然后把X放到空集合里
操作三:直接输出当前集合的大小。

题三

题意

给一个n个数的集合A,构造一个错排序列B(每个元素与原序列的位置不同)
有注:inx为该元素下标
求最小的sum。

当时做法

dfs暴力搜索+剪枝

一面

笔试AK，收到了面试通知。

自我介绍

我叫XXX,XXX大学，大三在读。有2年ACM经验....还介绍了下自己初中的开***的经历。

直接手撕代码

字符串匹配

1.手撕暴力(5分钟不到
2.嘴撕KMP(主要是太久没写了，忘记了，所以变成了嘴撕

K个有序链表合并

10分钟左右随便手撕了个做法。(写完后发现没用链表，用了数组，面试官说没关系

基础知识

1.进程和线程
2.new在什么情况下会抛出异常
注:没问什么基础，手撕代码的时候用些STL，边写边分析复杂度，关键我基础不太懂，面试官也看出来了。

结束

面试官让我问了他些问题，就提了些实习安排之类的。
面试官:暑期实习只有一次面试，你在我这边编码能力合格了，要看HR，应该在5-7个工作日告诉你结果(还说主要看重编写代码能力之类的吧。

结果

已收到offer~nice