一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 6756|回复: 63
收起左侧

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

  [复制链接] |只看干货 |刷题, leetcode
我的人缘0

升级   50%


分享帖子到朋友圈
李浩泉 | 显示全部楼层 |阅读模式
本楼: 👍   17% (6)
 
 
82% (28)   👎
全局: 👍   92% (1336)
 
 
7% (107)    👎
7月

脸书DE5 昂赛被拒,
亚麻BIE6被降级为5,我果断拒了亚麻

8月闭关刷题两周后,今天约了虾图两个小伙伴PK PYTHON算法,mock interview,一个是亚麻的SDE,另一个是微软的SDE。结果我把他们KO了,好开心。复盘如下:

You have a histogram. Try to find size of the biggest rectangle you can build out of the histogram bars in 15 minutes.

Input: List of all rectangles heights in histogram

Output: Area of the biggest rectangle




largest_histogram([5]) == 5
largest_histogram([5, 3]) == 6
largest_histogram([1, 1, 4, 1]) == 4
largest_histogram([1, 1, 3, 1]) == 4
largest_histogram([2, 1, 4, 5, 1, 3, 3]) == 8

corner case

histogram = [70,60,67,78,89,87,74,40,100,24,66,84,11,99,4,34,21,23,66,34,47,54,51,88,53,7,94,72,28,59,30,44,0,17,96,34,63,6,81,61,26,96,72,5,32,57,1,3,47,13,97,96,9,7,80,5,89,77,7,75,63,59,90,88,16,48,93,33,70,35,57,15,61,81,63,83,33,3,55,63,86,33,94,45,76,99,86,14,96,81,33,32,76,37,56,54,63,11,82,41,90,81,53,42,89,75,98,74,18,73,7,30,10,14,67,59,25,56,41,90,80,17,84,16,45,6,29,87,79,56,33,94,73,72,31,18,30,17,81,64,92,3,94,12,65,23,50,54,52,16,19,39,26,12,75,19,11,69,48,25,64,6,22,19,19,29,41,90,43,41,36,66,91,23,28,4,15,94,89,6,87,4,98,19,12,54,3,66,84,83,28,95,3,55,44,64,86,15,15,37,89,65,100,9,11,6,38,26,62,89,14,29,81,94,47,63,71,56,31,96,68,30,96,77,32,28,82,39,75,67,73,83,70,70,74,50,89,98,27,50,2,42,46,11,59,60,96,90,20,14,92,20,59,8,16,23,69,41,7,64,66,38,30,47,87,82,73,12,82,0,45,100,59,10,42,19,21,22,17,67,33,69,12,100,14,11,20,43,30,20,93,43,14,28,68,55,89,57,48,97,95,88,4,41,61,45,91,0,22,57,40,18,21,97,51,36,67,14,22,6,57,11,31,48,45,83,97,60,14,32,27,65,24,48,94,63,25,50,52,91,55,81,96,33,89,82,21,8,100,93,100,47,18,80,88,81,1,10,81,25,68,95,81,95,53,93,79,23,9,87,63,95,4,68,42,73,16,29,27,44,3,48,90,92,46,66,81,58,98,64,90,95,64,46,73,40,74,67,32,59,61,89,96,42,47,97,70,22,78,70,2,67,39,59,76,78,41,23,84,52,88,89,88,4,17,48,3,41,30,14,30,92,65,87,79,84,21,57,19,62,19,50,13,27,21,83,25,19,72,50,40,12,4,43,60,41,46,45,92,93,16,54,29,38,42,53,93,2,44,98,79,25,34,3,69,74,21,100,92,61,100,22,23,74,70,76,18,10,50,68,96,83,95,69,90,49,61,93,51,55,47,87,53,50,80,31,76,0,64,74,68,11,18,85,99,67,71,88,87,72,10,58,31,82,49,70,10,84,79,23,5,53,25,36,9,33,71,48,4,14,51,71,58,44,17,53,87,62,41,80,90,0,36,48,75,67,28,82,34,75,93,63,66,72,54,41,68,67,82,77,36,74,16,4,96,39,61,64,92,78,86,21,87,43,81,94,76,31,18,50,59,66,57,34,77,27,57,66,65,17,25,90,78,23,52,31,28,71,93,95,62,23,99,48,36,85,22,13,33,13,33,67,63,100,52,94,97,83,45,88,65,9,31,30,97,9,71,45,39,15,39,79,25,62,69,1,30,26,25,74,35,5,22,72,25,3,15,52,94,87,37,46,9,58,90,14,46,39,44,60,53,5,18,12,69,25,55,37,85,3,43,75,20,9,35,1,60,58,83,77,60,75,7,91,76,95,48,91,83,50,3,85,42,31,68,48,94,37,96,89,43,40,24,43,72,8,49,93,26,74,82,63,41,82,74,58,46,39,30,3,58,84,68,84,1,18,26,26,18,40,59,29,22,73,1,74,33,62,73,12,1,43,72,33,44,24,63,18,65,93,18,28,91,87,15,24,84,96,87,6,48,14,99,79,75,25,68,53,26,27,63,74,75,96,94,7,100,91,77,96,32,34,42,19,2,0,68,21,55,21,20,48,84,1,63,96,2,52,53,99,90,82,50,46,23,49,33,26,55,100,37,92,11,70,60,61,30,35,26,10,69,90,54,46,58,96,65,49,8,89,74,52,29,60,93,51,47,27,72,42,12,51,36,34,26,62,13,81,20,97,52,25,44,41,90,18,7,34,99,98,40,49,100,16,84,93,10,35,75,78,96,13,83,38,66,61,26,83,34,13,59,89,22,35,41,45,25,42,69,95,40,43,1,65,44,18,25,81,87,86,43,90,64,16,88,49,6,21,80,89,71,63,25,47,91,93,8,42,61,67,22,67,96,69,45,100,41,48,72,96,3,18,30,37,85,51,84,75,10,99,74,84,91,58,6,8,13,50,94,39,19,73,70,96,0,18,58,29,100,84,92,91,46,48,4,33,60,35,14,45,43,6,42,30,91,0,71,100,55,14,9,99,100,31,83,6,37,48,57]

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x

评分

参与人数 1大米 +2 收起 理由
14417335 + 2

查看全部评分


上一篇:GitHub 推出学生大礼包,各种免费subscription
下一篇:用了几年leetcode了,突然发现竟一直是月付。。
我的人缘0

升级   39%

失败痛哭 2020-8-18 02:03:10 | 显示全部楼层
本楼: 👍   100% (91)
 
 
0% (0)   👎
全局: 👍   97% (522)
 
 
2% (14)    👎
本帖最后由 失败痛哭 于 2020-8-18 02:04 编辑

lz你要这么比地里的new grad刷子们都能秒flag L6+

评分

参与人数 9大米 +12 收起 理由
小丸几 + 2 给你点个赞!
Hatschek + 1 给你点个赞!
cks2009899 + 1 给你点个赞!
12farmers + 2 秀儿坐下
leefreeman2017 + 1 赞一个
externaldrive + 1 给你点个赞!
davidxu + 2 给你点个赞!
ju40268 + 1 赞一个
HallOfFame + 1 说的太对了!

查看全部评分

回复

使用道具 举报

我的人缘0

升级   7.57%

lyyc 2020-8-17 18:14:48 | 显示全部楼层
本楼: 👍   100% (21)
 
 
0% (0)   👎
全局: 👍   97% (42)
 
 
2% (1)    👎
这题不是lc84吗😂单调栈可以做到O(N)
回复

使用道具 举报

我的人缘0

升级   50%

 楼主| 李浩泉 2020-8-18 02:37:36 | 显示全部楼层
本楼: 👍   70% (17)
 
 
29% (7)   👎
全局: 👍   92% (1336)
 
 
7% (107)    👎
本帖最后由 李浩泉 于 2020-8-18 02:44 编辑
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的能力?!

评分

参与人数 2大米 +3 收起 理由
biorainy + 1 赞一个
potplus + 2 赞一个!

查看全部评分

回复

使用道具 举报

我的人缘0

升级   50%

 楼主| 李浩泉 2020-8-17 13:15:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (1336)
 
 
7% (107)    👎
亚麻SDE的解法(Corner Case 测试:用时8秒钟!!!)

[Python] 纯文本查看 复制代码
def largest_histogram(histogram):
    result, width = 0, len(histogram) + 1
    for i in range(1, width):
        for j in range(width - i):
            rect = i * min(histogram[j:][:i])
            result = max(result, rect)
    return result


回复

使用道具 举报

我的人缘0

升级   50%

 楼主| 李浩泉 2020-8-17 13:16:27 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (1336)
 
 
7% (107)    👎
微软SDE的解法(Corner Case 测试:用时6秒钟!!!)

[Python] 纯文本查看 复制代码
def largest_histogram(histogram):
    lgth = len(histogram)
    ans = max(histogram)
    for i in range(2,lgth+1):
        s = [min(histogram[k:k+i])*i for k in range(lgth-i+1)]
        s.append(ans)
        ans = max(s)
    return ans


回复

使用道具 举报

我的人缘0

升级   50%

 楼主| 李浩泉 2020-8-17 13:18:27 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (1336)
 
 
7% (107)    👎
我的解法(Corner Case 测试:用时1秒钟!!!

[Python] 纯文本查看 复制代码
def largest_histogram(histogram):
    result = 0
    for i in range(len(histogram)):
        w = 0
        for j in range(len(histogram[i:])):
            if histogram[i] <= histogram[i:][j]: 
                w += 1
            else: break
        for k in reversed(range(len(histogram[:i]))):
            if histogram[i] <= histogram[:i][k]: 
                w += 1
            else: break  
        result = max(result,histogram[i]*w)
    return result


回复

使用道具 举报

我的人缘0

升级   81.05%

magicsets 2020-8-17 14:26:49 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (1208)
 
 
0% (8)    👎
楼主你把那个corner case的定义后面再加一行:
histogram_100 = histogram * 100

那么 largest_histogram(histogram_100) 大概会一个小时都跑不完.. 因为这三个方法都是 n^3 时间(如果Python像R一样支持Copy-on-write的话,这三个方法则可以到O(n^2)时间,可惜并不)

而这道题的目标一般是O(N),换句话说 histogram_100 至少要做到100毫秒以内.. 最优解要涉及一些non-trival的子数组上的性质,属于组合优化类问题,用data analytics一些常规operator(比如array slicing、list comprehension)来表达然后还要比性能的话就比较尴尬

评分

参与人数 1大米 +2 收起 理由
小丸几 + 2 正解!

查看全部评分

回复

使用道具 举报

我的人缘0

升级   26.25%

godblessyou 2020-8-17 20:59:59 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
牛了,拒了亚麻竟然
回复

使用道具 举报

我的人缘0

升级   97.14%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (746)
 
 
1% (8)    👎
啥意思啊……
回复

使用道具 举报

我的人缘0

升级   73.43%

jerry4013 2020-8-17 21:53:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (503)
 
 
3% (17)    👎
本帖最后由 jerry4013 于 2020-8-17 21:58 编辑

把lc的最优的答案贴在这里,O(n),仅供大家参考。 至于楼主的三种解法,我个人认为都是O(n^2),如果说得不对请大家指正。
[Java] 纯文本查看 复制代码
public class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack < Integer > stack = new Stack < > ();
        stack.push(-1);
        int maxarea = 0;
        for (int i = 0; i < heights.length; ++i) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
                maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
            stack.push(i);
        }
        while (stack.peek() != -1)
            maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() -1));
        return maxarea;
    }
}

看到有人说是O(n^3),我对python内部原理不熟悉,也可能数组切片的操作也要花n?那就变成O(n^3)了。不过直觉上个人感觉python不会那么蠢。。。

评分

参与人数 3大米 +6 收起 理由
格林匹施ZELQ + 2 切片是O(N)
xh_pku + 3 给你点个赞!
PandasPan + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0

升级   19.86%

PandasPan 2020-8-17 22:12:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (210)
 
 
0% (0)    👎
jerry4013 发表于 2020-8-17 21:53
把lc的最优的答案贴在这里,O(n),仅供大家参考。 至于楼主的三种解法,我个人认为都是O(n^2),如果说得不 ...

对的, python里数组切片是要花时间的,复杂度取决于你切多少,假设取K,时间复杂度就是O(K)。

优化方法也有,就是传起始的index而不是整个切片。

如果还有其他优化方法,欢迎分享

评分

参与人数 1大米 +1 收起 理由
jerry4013 + 1 谢谢!

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表