头条秋招春招失败的思考

Contents
  1. 1. 秋招后台岗
    1. 1.1. 一面
      1. 1.1.1. 数组中乘积最大连续子数组
    2. 1.2. 二面
      1. 1.2.1. 写个类似单调栈的玩意儿
      2. 1.2.2. 微信怎么拉取朋友圈信息
      3. 1.2.3. 服务器很少,流量很大,怎么负载均衡啊
    3. 1.3. 三面
    4. 1.4. 然后就没然后了啊
  2. 2. 春招算法岗
    1. 2.1. 一面
      1. 2.1.1. 二叉树最长路径长度
      2. 2.1.2. 脑筋急转弯
    2. 2.2. 二面
      1. 2.2.1. 复杂链表的复制
      2. 2.2.2. 机器学习
      3. 2.2.3. 一个奇怪的题
    3. 2.3. 三面
      1. 2.3.1. 24点游戏
    4. 2.4. 然后就又没然后了啊
  3. 3. 后记

毕设交了一波初稿,总算回来填坑了。回头想想,不得不说头条面试反映了我的心境变化。

秋招后台岗

一面

记得有2个题,其中一个应该非常水的题,没啥印象了。

数组中乘积最大连续子数组

这个现在就是一眼的dp,只怪刷了那么多题的我还是刷题太少了。

  • Old Solution
    直接暴力是$O(n^3)$的,所以就显然的前缀积优化到$O(n^2)$
    蓝儿因为有$0$,这里就会有些问题,为了避免除$0$要做一些处理
    不过实际上只要乘了$0$这一段乘积就是$0$了,所以把所有$0$的位置抠出来就可以了
    然后枚举每一段,就不会有事了,答案初始化为$0$就可以了,前提是有一个$0$。。
  • New Solution
    很简单的dp啊,,$f[i][0/1]:$=到$i$这个位置的连续乘积最大值/最小值
    就是套用最大连续子段和的套路,这破题我还被问过两遍
    $HR$又做了一个更复杂的的树形的,不过那个时候我一眼秒了。。
    就因为有负数嘛,所以就简单的维护下最小值就好了。。

二面

写个类似单调栈的玩意儿

印象中应该让写了一个支持push,pop,getMin的栈,所有操作$O(1)$

  • Solution
    这东西也很简单啊,就维护数字栈的之后再顺手维护一个单调栈,细节注意一下就好了
    我当时并没有想到单调栈,可能平时用的不多。不过还是有脑子的,随便一想就想到了。
    我记得这个破题剑指offer上有吧,虽然一直没注意。

微信怎么拉取朋友圈信息

这东西我真不会啊,就xjb说了一下,本地存个跟帐号有关的hashvalue表示已经拉取了多少
每次拉取的时候,服务器也生成一个,比对一下,不适最新的就拉取就好了。
当然你问我什么别人点赞评论啥的,我真的不会啊。。

服务器很少,流量很大,怎么负载均衡啊

不会啊,xjb扯淡啊,就随手说了一下缓存服务器,Nginx啥的(这东西我tm就听过名字。
讲道理啊,为啥不买设备啊喂!(大雾

三面

哇,这面跑不了啊,直接就问我后台技术栈啥的。
骗不过去了啊。然后就不知道啊。有点绝望啊。
意识不清醒了啊,打完比赛找不到工作一同交织在一起啊。
然后面试官问我读不读研啊。然后脑子一抽说想读啊。
然后我还耿直的去问头条有没有quit工作去读研啊
没见过比我更sb的人了
主要还是比赛打炸了,心态太差了。几个月都没调好。

然后就没然后了啊

春招算法岗

一面

扯扯淡啊,自我介绍啥的啊,ACM打的怎么样啊。。

二叉树最长路径长度

一看就当普通树做了啊,然后就无脑说两次dfs求直径就好了啊。
他说能不能一次啊,那就无脑dp求一下直径啊。
他说还能不能再简单一点啊。 (dp还不简单啊
哇 我又看了一下题,发现二叉树。
然后我就说那简化一下啊。

  • Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    struct Node{
    Node* ls, *rs;
    };
    const int INF = INT_MAX / 2;
    int maxd = -INF;
    int dfs(Node* cur){
    if(cur == nullptr) return 0;
    int ldep = dfs(cur->ls);
    int rdep = dfs(cur->rs);
    maxd = max(maxd, ldep + rdep + 1);
    return max(ldep, rdep) + 1;
    }

脑筋急转弯

有25个人,跑道一次只能跑5个人,问最少跑几次能得到冠亚季军啊。

  • Solution
    一眼看穿是多路归并啊,然后算了一下是8啊。。

二面

不记得问了啥啊,就扔了一个题,然后问了点儿机器学习的东西

复杂链表的复制

  • Description
    有一个链表L,其每个节点有2个指针,一个指针next指向链表的下个节点,另一个random随机指向链表中的任一个节点,可能是自己或者为空,写一个程序,复制这个链表

  • Solution
    剑指offer上有啊,看了一眼思路啊当时就,然后很慌啊。
    不过面了那么多面试啊,一下子就冷静了啊。然后就会了啊。
    就后面拷贝一份搞一搞啊。

  • Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    struct Node{
    int val;
    Node *nxt, *random;
    Node(){}
    Node(int val, Node *nxt, Node *random): val(val), nxt(nxt), random(random){}
    };
    Node* copyComplexList(Node *head){
    if(head == nullptr) return nullptr;
    for(Node *cur = head; cur != nullptr; cur = cur->nxt->nxt){
    Node *copied = new Node(cur->val, cur->nxt, cur->random);
    cur->nxt = copied;
    }
    for(Node *cur = head->nxt; cur != nullptr; cur = cur->nxt->nxt){
    cur->random = cur->random->nxt;
    }
    Node *nHead = head->nxt;
    for(Node *cur = head; cur != nullptr; cur = cur->nxt){
    Node *copied = cur->nxt;
    Node *copiedNxt = copied->nxt->nxt;
    Node *curNxt = cur->nxt->nxt;
    cur->nxt = curNxt;
    copied->nxt = copiedNxt;
    }
    return nHead;
    }

机器学习

  • 手推一下LR吧
    就直接把Hypothesis Function,Cost Function写一写,Gradient Decent推一推啊。
    然后我就推了一下啊,sigmoid函数的导数差点不会推啊。。有惊无险啊
  • 正则参数$\lambda$选取的影响啊
    大了会overfitting啊,小了会underfitting啊。

一个奇怪的题

  • Description
    对一个数组,有n个数据,找一个索引的位置k,使前k个数的方差var(k)和后面n-k个数的方差var(n-k)之和最小。

  • Solution
    不知道能不能$O(1)$啊,不会做啊,就暴力展开了一下方差啊
    然后$O(n)$枚举$k$,$O(1)$算答案,总复杂度$O(n)$

  • Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    /*
    var = \sum_{i=1}^n (x_i - avg)^2
    = \sum_{i=1}^n (x_i ^ 2 + avg^2 - 2*x_i*avg)
    = \sum_{i=1}^n (x_i ^ 2 + (sum / n)^2 - 2 * x_i * (sum / n))
    = \sum_{i=1}^n x_i^2 + sum^2 /n - 2*sum^2/n= \sum_{i=1}^n x_i^2 - sum^2/n
    */
    int findIndex(const vector<int>& v){
    int preSqSum = 0, totSqSum = 0;
    int preSum = 0, totSum = 0;
    pair<double, int> varAndIdx = {-1, -1};
    for(int i = 0; i < v.size(); ++i){
    totSqSum += v[i] * v[i];
    totSum += v[i];
    }
    for(int i = 0; i < v.size(); ++i){
    preSum += v[i];
    preSqSum += v[i] * v[i];
    int sufSqSum = totSqSum - preSqSum;
    int sufSum = totSum - preSum;
    double preVar = preSqSum - 1.0 * preSum * preSum / (i + 1);
    double sufVar = sufSqSum - 1.0 * sufSum * sufSum/ (v.size() - i - 1);
    varAndIdx = max(varAndIdx, {preVar + sufVar, i});
    }
    return varAndIdx.second;
    }

三面

24点游戏

  • Description
    给定4个整数0~9,给出是否能计算得到24,加减乘除括号,普通算术运算。精度他说1e-5

  • Solution
    以前写过啊,蓝儿没脑子了啊,连面了两面。
    就选择写暴力搜索所有表达式啊。
    然后就因为string v = "" + toChar(a) + toChar(b) + toChar(c) + toChar(d);
    这个垃圾代码不CE挂了啊。。我以为会CE的啊。结果最后半天才反应到这里。
    写了半个多小时,面试官他写了一个都写完了啊。。难受啊。。
    我当时好怂啊,不自信啊。。结果面试结束后几分钟就调通了啊。

  • My Code
    找不到最终版本了,就扔个有点小问题的吧。纪念一下我这个“C++大师”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
const string op = "+-*/";
int getPriority(char c) {
if(c == '+' || c == '-') return 1;
else if(c == '*' || c == '/') return 2;
return 0;
}
vector<string> inToPost(const string& expr) {
stack<char> opr;
vector<string> ret;
for(int i = 0; i < expr.size(); ++i) {
char c = expr[i];
if(c == '(') opr.push(c);
else if(c == ')') {
while(true) {
char top = opr.top(); opr.pop();
if(top == '(') break;
ret.push_back(string(1, top));
}
} else if(isdigit(c)) {
string digit;
for(; i < expr.size() && isdigit(expr[i]); ++i) digit += expr[i];
ret.push_back(digit);
--i;
} else {
int curP = getPriority(c);
for(; opr.size() && getPriority(opr.top()) >= curP; opr.pop())
ret.push_back(string(1, opr.top()));
opr.push(c);
}
}
for(; opr.size(); opr.pop()) ret.push_back(string(1, opr.top()));
return ret;
}
double calc(const vector<string>& post) {
stack<double> opd;
for(const auto& s : post) {
if(isdigit(s[0])) opd.push(stod(s));
else {
assert(opd.size());
double y = opd.top(); opd.pop();
assert(opd.size());
double x = opd.top(); opd.pop();
if(s[0] == '+') opd.push(x + y);
else if(s[0] == '-') opd.push(x - y);
else if(s[0] == '*') opd.push(x * y);
else opd.push(x / y);
}
}
return opd.top();
}
bool check(int dep, bool lftBracketed, string s) {
if(dep == s.size()) {
if(lftBracketed) s += ')';
// cout << s << endl;
if(abs(calc(inToPost(s)) - 24) < 1e-5) return true;
return false;
}
if(isdigit(s[dep])) {
if(dep > 0) {
for(int i = 0; i < 4; ++i) {
string ns = s;
ns.insert(dep, 1, op[i]);
if(check(dep + 2, lftBracketed, ns)) return true;
if(lftBracketed) {
ns.insert(dep + 2, 1, ')');
if(check(dep + 3, 0, ns)) return true;
} else {
ns.insert(dep + 1, 1, '(');
if(check(dep + 3, 1, ns)) return true;
}
}
} else if(check(dep + 1, lftBracketed, s)) return true;
} else if(check(dep + 1, lftBracketed, s)) return true;
return false;
}
bool twentyFour(int a, int b, int c, int d) {
auto toChar = [](int x) {return char('0' + x);};
string v = string("") + toChar(a) + toChar(b) + toChar(c) + toChar(d);
sort(v.begin(), v.end());
bool ok = false;
do {
ok |= check(0, 0, v);
} while(!ok && next_permutation(v.begin(), v.end()));
return ok;
}
int main() {
string test = "5*5-5/5";
//cout << calc(test) << endl;
cout << (calc(inToPost(test))) << endl;
cout << twentyFour(5, 5, 5, 5) << endl;
return 0;
}
  • Interviewer’s Code
    没仔细读这个代码啊,改天研究一下正确性,写一个bugfree的24点感觉不容易啊。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import itertools
def isEqual(v0, v1):
return abs(v0 - v1) < 1e-6
def expresssion(code, v0, v1):
if code == 0:
return v0 + v1
elif code == 1:
return v0 - v1
elif code == 2:
return v1 - v0
elif code == 3:
return v0 * v1
elif code == 4:
if isEqual(v1, 0):
return float('NaN')
return float(v0)/v1
elif code == 5:
if isEqual(v0, 0):
return float('NaN')
return float(v1)/v0
def printExpr(code, v0, v1):
if code == 0:
print '%s+%s' %(v0, v1)
if code == 1:
print '%s-%s' %(v0, v1)
if code == 2:
print '%s-%s' % (v1, v0)
if code == 3:
print '%s*%s' % (v0, v1)
if code == 4:
print '%s/%s' % (v0, v1)
if code == 5:
print '%s/%s' %(v1, v0)
def search(a, v):
if len(a) == 1:
return isEqual(a[0], v)
elif len(a) == 2:
for code in range(6):
if isEqual(expresssion(code, a[0], a[1]), v):
printExpr(code, a[0], a[1])
return True
return False
elif len(a) == 3:
for b in itertools.permutations(a):
for code in range(6):
if search([expresssion(code, b[0], b[1]), b[2]], v):
printExpr(code, b[0], b[1])
return True
return False
elif len(a) == 4:
for b in itertools.permutations(a):
for code in range(6):
if search([expresssion(code, b[0], b[1]), b[2], b[3]], v):
printExpr(code, b[0], b[1])
return True
return False
elif len(a) == 4:
for b in itertools.permutations(a):
for code in range(6):
if search([expresssion(code, b[0], b[1]), b[2], b[3]], v):
printExpr(code, b[0], b[1])
return True
return False
print search([3, 3, 8, 8], 24)

然后就又没然后了啊

后记

好好学习辣!然后要自信!失败了并不会失去什么。


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到