过了一面，没过二面。☹️
分享经验，继续努力。💪
简历情况
pre留学生实习
中下等985，计算机专业，大三
有ACM-ICPC竞赛经历
一面
40min笔试
室友只有2道题，给我的发了4个……掐点写完。
形式：发了个在线文档，内容如下。
说明
- 笔试总时间为40分钟。
- 语言用c/c++，直接在本文档中“白板coding”，不能编译、调试运行。
- 可以自己额外定义函数和实现。
- 在正确解答题目的前提下，算法复杂度、空间复杂度越低越好。
- 没有要求按顺序做，也没要求全部做完。
- 如提前作答完毕，可以提前告知提交。
———————文字交流区域，可以在此打字，我会及时回复—————————
coding中有，对题目疑问也可以在此打字。
test
可以自己再写个函数吗？ 说明3（可以）
可以调用sort函数吗？ 可以
题目一 - 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
/*** 结构的定义.
* struct TreeNode {
* int val;
* TreeNode *left;
* reeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right)
* : val(x), left(left), right(right) {}
* };
*/
bool is2TreeSymmetric(TreeNode* l, TreeNode* r) {
if (l == null && r == null) return true;
if (l == null || r == null) return false;
return (l.val == r.val && is2TreeSymmetric(l.left, r.right) && is2TreeSymmetric(l.right, r.left);
}
bool isSymmetric(TreeNode* root) {
//代码写这里
if (root == null) return true;
return is2TreeSymmetric(root.left, root.right);
}
二叉树 递归
被面试官问是不是写Java比较多？因为错将->写作.。
答主要C/C++，有时写Java。是笔误。
题目二 - 旋转
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
数据大小：
1 <= nums.length <= 2 * (10^4)
-(2^31) <= nums[i] <= (2^32) - 1
0 <= k <= 10^5
代码:
void rotate(vector<int>& nums, int k) {
//代码写这里
int len = nums.length();
int a[len];
for (int i = 0; i < nums.length(); i++) {
a[(i+k)%len] = nums[i];
}
for (int i = 0; i < nums.length(); i++) {
nums[i] = a[i];
}
}
数组
开始写错成swap(a[i], a[(i+k)%len])，最后5分钟改正。面试官也发现了此点并指出。
后问如果不开a数组，只在空间O(1)就如何实现？思考10s，未答上来。
题目三 - 装水
输入：
每个横坐标的高度。
输出：
能装水的体积。
举例：
见上图，输入是[0,1,0,2,1,0,1,3,2,1,2,1]，//黑色方块
答案是6。//蓝色方块
代码：
int trap(vector<int>& height) {
//代码写这里
int l = 0, r = height.length() - 1;
int maxl = height[l], maxr = height[r];
int ans = 0;
while (l < r) {
if (maxl < maxr) {
l++;
if (height[l] < maxl)
ans += maxl - height[l];
else
maxl = height[l];
} else {
r--;
if (height[r] < maxr)
ans += maxr - height[r];
else
maxr = height[r];
}
}
return ans;
}
贪心
这个题用时最长。
找所有极大值点中间差的部分。
l从左向右挪，r从右向左。maxl与maxr保存当前的从左向右和从右向左的最小值。
不断更新maxl、maxr或ans直到l与r相遇。
回答较顺，没多问什么。
题目四 - 硬币
有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：
每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。
Alice 将会取走硬币数量最多的那一堆。
你将会取走硬币数量第二多的那一堆。
Bob 将会取走最后一堆。
重复这个过程，直到没有更多硬币。
给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。
返回你可以获得的最大硬币数目。
示例 1：
输入：piles = [2,4,1,2,7,8]
输出：9
解释：选出 (2, 7, 8) ，Alice 取走 8 枚硬币的那堆，你取走 7 枚硬币的那堆，Bob 取走最后一堆。
选出 (1, 2, 4) , Alice 取走 4 枚硬币的那堆，你取走 2 枚硬币的那堆，Bob 取走最后一堆。
你可以获得的最大硬币数目：7 + 2 = 9.
考虑另外一种情况，如果选出的是 (1, 2, 8) 和 (2, 4, 7) ，你就只能得到 2 + 4 = 6 枚硬币，这不是最优解。
示例 2：
输入：piles = [2,4,5]
输出：4
示例 3：
输入：piles = [9,8,7,6,5,1,2,3,4]
输出：18
数据大小：
3 <= piles.length <= 10^5
piles.length % 3 == 0
1 <= piles[i] <= 10^4
int maxCoins(vector<int>& piles) {
//代码写这里
int n = piles.length() / 3;
int ans = 0;
sort(piles.begin(), piles.end(), greater<int>());
for (int i = 1; i <= 2 * n; i += 2) {
ans += piles[i];
}
return ans;
}
博弈论让每一组第二大的数最大。
从大到小排序，每一组构成为：第1大的、第2大的和一个从最小的那一堆里拿出来的一个。答案是数组中排第2、4、6……的数的和。
下标马虎写错为从0到2*n，被指出。
20min面试
形式：电话
自我介绍
略。
刚刚4个题的思路
具体见上。
C++
Q：C++指针与引用的区别？
A：指针是另开一个空间里面存要存的东西的地址，引用只是变量的一个别名。
Q：只有这一点吗？有补充吗？
A：指针C/C++都可以用，引用只有C++可以用。
操作系统
Q：进程与线程？
A：进程是程序运行的基本单位，一个进程可以包含很多线程。
Q：进程间的通讯？
A：P和V操作、信号量。（然后他那意思好像是他问的不是这）
Q：是否上过操作系统课？
A：是。
Q：是否了解blablablablabla（几个名词，忘了）？
A：不了解。
Q：栈？
A：一种数据结构数据栈是运行前把数据压栈，算完再弹出去。
网络
Q：描述从用浏览器打开一个网站之后发生的所有事？
A：访问DNS找到IP、TCP三次握手、HTTP协议。
Q：这些都结束后是否断开链接？
A：不，只有关闭网页之后才会断开。
（可能答错了，因为又被问了一遍“你确定吗”）
扒简历
Q：什么时间开始参加ACM竞赛？
A：大一参加校内，大二大三开始参加校外。
Q：CCPC女生赛是什么？
A：参赛的3个人都是女生。
Q：比赛是组队还是单人？
A：校内赛是个人，区域赛是3人一队。
Q：天梯赛是什么？
A：不同于ACM按过题数与时间排名，它用过题样例数计分（面试官：就是OI赛制喽！）。10人一队，但是各做各的，最后算总分。
Q：在队伍里负责什么？是否有分工？
A：没有明确分工，谁会谁写。擅长贪心、DP、搜索等。
算法
Q：DP？
A：动态规划，从一个状态推到另一个最后达到最终状态，得到答案。
Q：DP和搜索区别？
A：DP自底向上，搜索自顶向下。
Q：提出意见：记忆化搜索的dp是自顶向下的。
A：它更像搜索，只不过是一边搜索一边保存状态，以便后续访问。
反问
Q：什么时候来上班？
A：6月末～7月初。
Q：还有什么问题问他？
A：这个岗位具体做什么？还需要准备什么？
Q：就是刚才问的那些，C++、进程、网络。
A：什么时间出面试结果？
Q：不确定，要问问其他人。尽快，线下的面试也可以去参加试试。
结果
过了，约了下二面的时间。
二面
40min笔试
面试官说他要去接小朋友，先把题给我做，他到家了再给我打电话。
1、
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
123 + 456
L1 3 2 1
L2 6 5 4
ListNode
ListNode* next
int value
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2){
if (l1 == null) return l2;
if (l2 == null) return l1;
static int c = (l1 -> value + l2 -> value) / 10;
int sum = (l1 -> value + l2 -> value) % 10 + c;
ListNode* ans = new ListNode;
ans -> value = sum;
ans -> next = addTwoNumbers(l1 -> next, l2 -> next);
return ans;
}
大意了，l1 -> value + l2 -> value忘了+c，忘记判断最高位有进位的情况。
3、给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
int lengthOfLongestSubstring(char * s){
int len = strlen(s);
if (len == 0) return 0;
if (len == 1) return 1;
int ans = 0;
for (int i = 0; i < len - 1; i++) {
int tmp = 0;
for (int j = i + 1; j < len; j++) {
if (s[i] != s[j])//abca
tmp++;
else
break;
}
ans = max(ans, tmp);
}
return ans;
}
tmp应该初始化为1.
4、K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：
1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5//here
说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next; };
*/}
ListNode* reverseGroup(ListNode* head) {
ListNode* tmp1 = head -> next;
ListNode* tmp2 = tmp1 -> next;
head = null;
while (head -> next != null) {
tmp1 -> next = tmp2 -> next;
tmp2 -> next = head -> next;
head -> next = tmp2;
tmp2 = tmp1 -> next;
}
return tmp1;
}
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == null) return head;
//TODO
}
写了很长时间，做了一半没写完，就讲了思路：
每k个调用一下上面的函数翻转一下。
Q：不用递归怎么做？
A：循环。
5、给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
void rotate(int* nums, int numsSize, int k){
int a[numsSize];
for (int i = 0; i < numsSize; i++) {
a[(i+k)%numsSize] = nums[i];
}
return a;
}
没错，又来一遍。
35min面试
形式：微信电话
上面的题
比较大概（他也没像一面那样一直看我写代码），没有一面问得那么详细。
自我介绍
略
算法
Q：简历里参加了很多ACM比赛，讲讲具体干嘛，分工做什么？
A：梅开二度
Q：最短路？
A：简单说了Floyd和Dijkstra，SPFA用的少忘记了就只说了名。
课程
Q：大学学了哪些课程？
A：操作系统、计算机网络、数据库。
Q：学得怎么样？
A：还算……挺好的吧。
网络
Q：浏览器打开一个网址后发生什么？
A：梅开二度
Q：说得有点快，详细说说。DNS？
A：找IP的。
Q：如果有缓存？
A：先找缓存里的。
Q：详细讲TCP三次握手。
A：SYN、ACK。
Q：SEQ？
A：忘了。
Q：TCP慢启动？
A：超过阈值时拥塞窗口按指数增加。
Q：（几个没听过的词）是干嘛的？
A：不会。
Q：还学过啥讲讲。
A：拥塞控制用的滑动窗口协议。
操作系统
Q：进程、线程、协程？
A：梅开二度，协程用的少没太了解。
Q：内存管理？
A：没答到点上
Q：怎样学习的以上内容？
A：理解着背。
数据结构
Q：int、char、double底层如何实现？
A：int 8位（开始说错了，后纠正），double一位正负，后面是移动的位数和小数本身。
智力题
Q：海盗分金币？
A：97 0 1 0 2，从后往前递推。
评价
Q：网络回答的有点抽象，不像有其他同学那样有整体的概念，一层一层讲。
A：很多东西忘记了。
Q：为啥简历上选的是pre留学生面试？
A：想去香港读研，先实习积累经验。
Q：笔试比较好，面试不过关。有其他部门想去吗？客户端 or 前端？
A：客户端更感兴趣，但仍很多东西要学。前端不太会。
Q：反问？
A：梅开二度 & 什么时间出结果？
Q：梅开二度 & 总之我觉得不太行我的话会给不通过，今晚出。
结果
没过，简历被丢回简历池等待其他部门捞。（确实这次也答得不太好）
再面试的话再开个新的帖子写。
