gg onsite

上周一面的, 在sunnyvale。

  1. 华人阿姨, merge k sorted lists + 尬聊。

  2. 华人女, 给一串二维坐标点, 求形成的最小面积的corner rectangle的四个点。 follow up如果长方形内部不能有其他点该怎么办。

  3. 欧洲白人, 没出算法题,一道很奇怪的design题, 是他自己想的,。。做的也不太好,所以就不说了。 这轮非常的奇葩,面试官还问了我5分钟的简历。。

  4. 国人。 一个只有正整数的list, 其中插入+, * 或者(),求得到式子最大的值。
    e.g. [1,2,1,2 ] -> (1+2)*(1+2)=9. dp解, follow up, 如果有负数该怎么办, 如果想要拿到最大的式子该怎么办。

补充内容 (2018-10-21 00:10):
10.19 update 过了hc

dp[j] = max( dp[k] + dp[k+1][j], dp[k] * dp[k+1][j]) , i <= k < j

补充内容 (2018-10-21 04:51):
dp[j]

补充内容 (2018-10-21 04:52):
【i】都被吞了 这是什么bug

请问第二轮follow up什么思路啊?

求问第四题怎么做

第二题怎么做?暴力循环?

请问楼主第四题怎么用dp?

我的解法是先找到两个点确认为对角线,由此找另两个点, 是个O(n2)。