落榜的DE编程打败了微软和亚麻的SDE！！！请为我鼓掌！

jerry4013 发表于 2020-8-17 21:53
把lc的最优的答案贴在这里，O(n)，仅供大家参考。 至于楼主的三种解法，我个人认为都是O(n^2)，如果说得不 ...

亚麻SDE5的解法是：O（N^3），两个FOR循环是O（N^2），再加上循环中求数列中的MIN（），又是一个O（N），最后复杂度是指数级的，O（N^3）。

微软SED62的解法也是：O（N^3），区别是他用了正则表达式，效率稍微高一点点，本质上没有区。

我的算法是：O（N^（N+N））= O（N^2N）= O（N^2）。

1. def largest_histogram(histogram):
   
2.     maxarea = 0
   
3.     for i in range(len(histogram)):
   
4.         if i+1<len(histogram) and histogram[i] <= histogram[i+1]:
   
5.             continue
   
6.         temp = histogram[i]
   
7.         for j in range(i,-1,-1):
   
8.             temp = min(temp,histogram[j])
   
9.             area = temp*(i-j+1)
   
10.             maxarea = max(maxarea,area)
    
11.     return maxarea

复制代码

[/i][/i]

失败痛哭 发表于 2020-08-17 11:03:10
lz你要这么比地里的new grad刷子们都能秒flag L6+

仔细一想我这么水的人在刷题方面能好像能略秒jeff bezos?

失败痛哭 发表于 2020-8-18 02:03
lz你要这么比地里的new grad刷子们都能秒flag L6+

所以对于5年以上经验的在职跳槽，就不应该在像录取毕业生一样刷题啦！

我的看法是，时间复杂度O（N）很难实现，如果实现了也是牺牲了空间复杂度的基础上，空间换时间意义不大。因为本质上这是二维空间问题，二维问题的标准时间复杂度度应该是O（N^2），三维应该是O（N^3）。一维线性的线性是可以O（N）解决的。如果用时间复杂度O（N）解决二维或者三维的问题，一定是牺牲空间复杂度才能实现。

理论上，应该不存在时间复杂度O（N），空间复杂度O（N），就能解决三维空间问题的方案。也不存在时间复杂度O（N），空间复杂度O（1）能解决二维平面问题的方案。
对于这道题来说，在保持空间复杂度O（1）不变的情况下，O（N^2）就是最优解了。不会有时间复杂度O（N）空间复杂度O（1）的解法。欢迎一起交流，如果你有更好的方案，请分享PYTHON代码。

1. def largestRectangleArea(height):
   
2.     height.append(0)
   
3.     stack = [-1]
   
4.     ans = 0
   
5.     for i in range(len(height)):
   
6.         while height[i] < height[stack[-1]]:
   
7.             h = height[stack.pop()]
   
8.             w = i - stack[-1] - 1
   
9.             ans = max(ans, h * w)
   
10.         stack.append(i)
    
11.     height.pop()
    
12.     return ans

复制代码

potplus 发表于 2020-8-18 02:15
仔细一想我这么水的人在刷题方面能好像能略秒jeff bezos?

如果马云和姐夫去面试，一样过不了的刷题这道关。我发帖的目的就是置疑刷题面试的合理性。已经2020年了，大学SAT都取消了，为什么资深人士在职跳槽还要刷题面试？？？那些面试官自己盲做，也不能100%过吧！！！

我的工作就是把business metrics变成SQL里面的语句，工作第一年在crystal report和SP里面写SQL，后面5年在ETL SSIS里面写SQL，最近1年在AWS data pipeline里面写SQL，作为资深后台开发者，精通各种前端BI工具（power bi，tableau，qliksense，SAP BO）。我就是想从非大厂跳槽到一线大厂做同样的工作。你们onsite面试不考我怎么做dashboard，怎么写SQL，反而让我刷3SUM，合理吗？？？然后因为我15分钟内写不出3SUM，就否定了我写SQL做Dashboard的能力？！

李浩泉 发表于 2020-08-17 11:37:36
如果马云和姐夫去面试，一样过不了的刷题这道关。我发帖的目的就是置疑刷题面试的合理性。已经2020年了，大学SAT都取消了，为什么还要刷题面试？？？那些面试官自己盲做，也不能100%过吧！！！

你说的有道理，只是大家还没想出来比考刷题成本更低/更有效率的筛选面试者的办法。 我记得08年以前微软还喜欢考脑筋急转弯，这么一对比leetcode显得科学多了

李浩泉 发表于 2020-8-18 02:37
如果马云和姐夫去面试，一样过不了的刷题这道关。我发帖的目的就是置疑刷题面试的合理性。已经2020年了， ...

题目和怎么评判答案不能混为一谈

有经验的人没写出最优解也可能拿到大offer

Fb DE什么时候开始面算法了？ic5面算法？

不考刷题怎么区别你是真有能力还是只是纸上谈兵呢？当然，还有系统设计，ood和behavior问题作为辅助。这些加起来，误判率应该就会小很多了