狗家挂经 下次加油

zpppore 发表于 2021-9-16 14:54
我是recruiter提前邮件告诉的，每场面试官名字都有。可能是通过manage联系recruiter的原因。

学到了，原来还有这种情况的；我面试的时候就是开盲盒一样，进去才确定这轮的面试官

谷歌面试官还是比较考察思路的，如果你说你看到题下意识就想dfs，我觉得对方多半会认为你在套题套方法，而不是从逻辑出发去分析，这样可能已经扣了一半分了…

第三题感觉考得是能不能写出来 recurrence relation 大概是大二学离散数学的时候学的东西。 我想了一个recurrence relation感觉差不多 有三个base case
T(0)=1 T(1)=3 ,T(2)=7. T(N)= T(N-1)+2*T(N-2)+2*(T(N-3)+T(N-4)+...+T(0)). 楼主有兴趣可以一起讨论一下！

打扰了 楼主忽略我的答案， 我看成了不能有两个连续的A 和不能有两个连续的L

楼主 第二题删除一个node和它下面的subtree 和 幺幺幺零还是不一样的， 这题到底求什么？

可能狂喜被烙印看出来了， 烙印才使的坏。要是一脸无辜，可能放过。

那个dp的题是否可以这样
状态定义，开五个数组，A[i], LwA[i], LnA[i], OwA[i], OnA[i]  A[i]表示，在第i位为A的string可能数。LwA[i]表示在第i位为L 并且可以包含A的string的数目。LnA[i]表示是在第i位为L,但不包含A的string的数目。
状态转移：
A[i] = LnA[i-1] + OnA[i-1]
LwA[i] = A[i-1] + OwA[i] + OnA[i-1]
LnA[i] = OnA[i-1]
OwA[i] = A[i-1] + LwA[i-1] + LnA[i-1] + OwA[i-1] + OnA[i-1]

最后结果是 A[n-1] + LwA[n-1] + LnA[i-1] + OwA[i-1] + OnA[i-1]

粗浅的想法，大家斧正

lz oa多久以后收到vo邀请的啊请问

第三题
参考无无而，需要先分析出各种state，然后基于state的转换关系做DP。
state无非两个metrics，一个是多少个A(0个，1个)；然后结尾是否有L(0L, 1L), 然后画出类似下面的状态转移map做DP
----------------------------
        |     i
i - 1  | A -- L -- P --
-------------------
A0L0 | A1L0 A0L1 A0L0
A0L1 | A1L0  done A0L0
A1L0 | Done A1L1 A1L0
A1L1 | Done Done A1L0

delete subtree在年初的时候也被问到了。我也理解的是graph/tree的题，写完code面试官才说一开始讨论的input output和他最初想像的不一样，真的坑。到现在我都没搞明白这题考察的是什么...不知道有没有高人能指点一下。