1 笨笨的孩子慢慢学stay hungry stay foolish 2 学习，思考，实践，改变

0%

字节算法岗面试记录

发表于 更新于 分类于 Valine：

一面

面试官真的是很直接了，就出了道算法题。但整体来说这个面试官真的是超级好了啊，特别会引导，我觉得字节就是这点细节很好。

最大连续序列和。

如给一个Array： 1，-2，3，1，-1，5 。则是8 (3, 1, -1 , 5)

分析：设DP[k] 是表示以k结尾的最大的和。则递推公式为 DP[k] = max{DP[k-1] + A[k] ，A[k] }，要么是前一个连续和加上数组值（当前数组值为正），要么就是数组本身。这样最后只需要一遍遍历过去，找出以某个k结尾的最大和的那个DP值即为答案。

代入看：初始化DP[0] = 0 , DP[1] = max{1, 0} = 1 , DP[2] = max{-1, -2} = -1; ….

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxSequenceSum(int* matrix, int length){
  if(length < 0) return -1;
  int dp[length];
  dp[0] = 0;
  for(int i=1;i<length;i++){
    dp[i] = max(dp[i-1]+matrix[i], matrix[i]);
  }
  // get the max
  int res = 0;
  for(int i=0;i<length;i++){
    if(dp[i] > res) res = dp[i];
  }
  return res;
}

这里的时间复杂度是O (n)，空间复杂度也是O(n)，面试官引导进行优化空间。

思路就是用变量存上一个dp[i-1] 与最大的 dp值，直接返回即可。

1
2
3
4
5
6
7
8
9
10
11
int maxSequenceSum(int* matrix, int length){
  if(length < 0) return -1;
  int dp[length];
  int dp_max = matrix[0]; // store the max
  int dp_last = matrix[0]; // store the dp[i-1]
  for(int i=1;i<length;i++){
    dp_last = max(dp_last + matrx[i], matrix[i]);
    if(dp_last > dp_max) dp_max = dp_last;
  }
  return dp_max;
}

真的是有意思，我也没有刷完所有题，感觉自己思路还是有些慢，得再练哦。

二面

二面的技术leader有点像个稍严厉的大父亲，而且涉及很广居然包括博弈论，我虽然是学了很多博弈论的数学模型（还记得当时的考试，复习得可费劲了，得理解所有的啥完美，完全博弈啥概念，还得计算的）。在此记录一些问题吧。

1，优化问题

出了个问题是在给定的CTR和CVR之下，让用户尽量久的停留（停留时间长）。考虑最优化，写优化和约束和拉格朗日法。

max: t

s.t. CTR+r CVR > n

CTR和CVR的计算应该也是跟用户停留时间t有关的（现象上来看，用户停留时间越长，点击率和转化率可能越高），用最优化里的有约束的凸二次规划来看的话。

构建拉格朗日函数，对不等式约束引入拉格朗日乘子, $\alpha_i \geq 0$。

当然这里根据CTR和CVR的计算公式展开。根据拉格朗日对偶像，原始问题的对偶问题是极小极大问题。对所有实数域上的优化问题都有其对偶问题。

这里应该是对偶可以求一个 upper bound的。我一开始莽撞写错了不等式约束，然后后面联想SVM才改。在复习一下（图中f ,g 不要求是凸的）：

20200211Dual

2，广告拍卖模型

明拍（谁出的高就收谁的）和暗拍（相互不知道对方出价），各自的影响。

为什么拍卖？揭示信息并减少代理成本。当一个物品对买者的价值比卖者更清楚时，卖者一般不愿意首先提出价格，而采用拍卖方式获得可能的最高价格。

明拍：从最低价开始举牌逐渐升高。这里面可能涉及作弊问题，拍卖客户之间串通，以低价甚至是起拍底价成交的人，其他竞买人都不举牌与之竞争，再私下得到一些好处。

暗拍，是以出价最高的投标者获得拍卖品。并支付出价给卖者。（有一级密封拍卖，出价最高；二级密封拍卖，报价中的次高价）

2.1 一级拍卖

两个投标人，假设$b_i \geq 0$ 是投标人i的出价，$v_i$ 是拍卖品对投标人i的价值，可见$v_i$只有i自己知道（自己根据估计的真实价值进行出价，这个函数只与自己相关）。$v_i$ 独立地取自定义在区间$[0,1]$ 上的均匀分布函数。投标人i的效用（可以理解为我的收益）是：

假设投标人i的出价 $b_i(v_i)$ 是其价值 $v_i$ 的严格递增可微函数，肯定不会$b_i ＞1 > v_i$ 因为没人付比物品价值更高的出价。考虑对称的情况下出价策略 $b = b^{\star}(v)$ ，投标人i的预期支付是：

根据均匀分布有$k \in[0,1], \quad \operatorname{Pr} o b(\theta \leq k)=k$，即这里的$\Phi(b) = b^{*-1}(b)$

投标人面对的问题就是：

上面这个max最优化问题的一阶条件是：$-\Phi(b)+(v-b) \Phi^{\prime}(b)=0$

如果$b^{*}(\cdot)$ 是投标者i的最优策略，$\Phi(b)=v, then, v=(v-b) \frac{\mathrm{d} v}{\mathrm{d} b}$

积分$vb = \frac{1}{2}v^2$ 求得 $b^{\star}=v / 2$，即是这个博弈的贝叶斯均衡。

当有n个投标人时，每个投标人的价值$v_i$ 定义在【0，1】区间上且独立同分布。投标人i的预期支付函数是：

投标人越多，卖者能得到的价格就越高；当投标人数趋于无穷时，卖者几乎得到拍卖品价值的全部。因此，卖者希望更多的人加入竞标 。

2.2 二级拍卖

如果投标者想赢得投标，则他的效用是：

对每个参与人来说，自己只需要比其他人好一点点就行。即以他的估价进行投标的策略$\left(b_{i}=v_{i}\right)$ 弱优于其他策略。记$r_{i} \equiv \max _{j \neq i} b_{j}$ 即第二大出价。

$when: r_i \leq v_i $，以$v_i$投标则投标者获得效用是： $v_i - r_i$ （理解为其他所有人的出价都稍微小于自己心中对物品的估价，这样才可能获得正效用。）

当$r_i \geq b_i$ ，投标者i获得效用是0。当 则投标者i具有效用是 $v_i - r_i < 0$，若此时投标$v_i$ 则效用是0。

因此在二级密封价格拍卖中，投标者会以他们的估价进行投标 。

类比到互联网的广告拍卖里，其实也有广义第一价格GFP（实收价等于出价）和广义第二价格GSP（实收价等于第二出价），还有VGG竞价机制。

广义第一价格GFP（实收价等于出价）的影响，受广告主的出价影响，可能不稳定，可能高也坑可能低。GSP更能凸显出广告的真实价格。

2.3，概率生成器。

给一个不均分的硬币，投的正面概率是P（不是0.5），怎么用它来得到均匀（0.5）的结果。两次正面的概率是p，两次反面概率是（1-p）^2，一正一反的概率是 2p(1-p)，这里01、10的生成概率是相同的，基于此代表0，1来生成。

2020年1月23好不容易面完了二面，技术岗说后面HR联系，然后然后就没有然后了通知说岗位不匹配，就这样记录记录吧，每次面试都是一次学习总结的机会。

Reference

1，肖条军 《决策与博弈论》

2，封闭式拍卖)