回复: 11
收起左侧

阅后即焚 虚拟现场

匿名用户-HPH2E  2021-4-23 06:38:15
本楼:   👍  0
0%
0%
0   👎

2021(1-3月) 码农类General 硕士 全职@snapchat - 内推 - Onsite  | Other | 在职跳槽

注册一亩三分地论坛,查看更多干货!

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

x
电面面经在这里:https://www.1point3acres.com/bbs/thread-741033-1-1.html
他家onsite跟有些面经说的一样,真的是每个面试官都要聊经验/简历20分钟至少,到最后真是说得自己都想吐了。。。聊完然后开始做题,每轮感觉时间都很紧,稍微卡壳的话就会做不完。


第一轮 SD:国人小哥,非常nice; 聊项目聊了将近40分钟, 然后开始system design... Story Read Receipt, 要求:1. global un
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
有点奇怪,不过能听懂。sliding window median, 直接给出two heaps的思路,解释了有window size和没有window size的差异,感觉小哥期望的是另一个解法,跟他解释了很久这个方法的可行性和正确性,最后时间所剩无几了才让开始写,所以没写完。。这轮肯定是挂了。

总体来说基本还是面经题,自己准备得有点不够充分。。 觉得有用的话可加米:)

评分

参与人数 10大米 +17 收起 理由
huangya2 + 1 很有用的信息!
Jamchaser + 1 欢迎分享你知道的情况,会给更多积分奖励!
Luptior + 2 很有用的信息!
guanhoo + 2 很有用的信息!
funmastermike + 2 很有用的信息!

查看全部评分


上一篇:水果公司VR Engineer 电面
下一篇:【面经】生物本科生投哈佛医学院教学院技术员
地里匿名用户
匿名用户-HPH2E  2021-4-23 11:16:21
本楼:   👍  1
100%
0%
0   👎
noi10 发表于 2021-4-23 10:53
第二轮 2k个点,不是一共有2k-1条path吗?这样?

1----2-----3

我一开始也是这么理解的,但是只需要两两相连就行!(这么说来不该叫"path"...).

比如:
1..1.
1....
1....
...11
.....

只需要输出: [[(0,0), (0,1), (0,2), (0,3)], [(1,0), (2,0)], [(3,3), (3,4)]]
回复

使用道具 举报

風行烈 2021-4-23 11:35:51 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   704
95%
5%
35
noi10 发表于 2021-4-23 10:46
我昨天面别的公司,也面到第五题,也是用two heaps,但先写了一个不slide的,然后slide的时候interviewer表 ...
  1. class Solution:
  2.     def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
  3.         
  4.         def move(h1, h2):
  5.             x, i = heapq.heappop(h1)
  6.             heapq.heappush(h2, (-x, i))
  7.         def getMedian(h1, h2, k):
  8.             return h2[0][0] * 1. if k % 2 == 1 else (h2[0][0]-h1[0][0]) / 2.
  9.         
  10.         small, large = [], []
  11.         for i, x in enumerate(nums[: k]):
  12.             heapq.heappush(small, (-x, i))
  13.             
  14.         for _ in range(k - (k >> 1)):
  15.             move(small, large)
  16.         
  17.         ans = [getMedian(small, large, k)]
  18.         
  19.         for i, x in enumerate(nums[k:]):
  20.             if x >= large[0][0]:
  21.                 heapq.heappush(large, (x, i + k))
  22.                 if nums[i] <= large[0][0]:
  23.                     move(large, small)
  24.             else:
  25.                 heapq.heappush(small, (-x, i + k))
  26.                 if nums[i] >= large[0][0]:
  27.                     move(small, large)
  28.             while small and small[0][1] <= i:
  29.                 heapq.heappop(small)
  30.             while large and large[0][1] <= i:
  31.                 heapq.heappop(large)
  32.             ans.append(getMedian(small, large, k))
  33.         return ans
复制代码


Why is deletion for 2 heaps O(n)? This solution uses lazy deletion for both small heap and large heap, but removal from a heap should still be O(logN) right?

Here is my other solution using SortedList. sortedcontainers is not a standard library in python but it's included in leetcode environment. I believe java has treeset and cpp has multiset which does similar things.
  1. class Solution:
  2.     def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
  3.         from sortedcontainers import SortedList
  4.         result = []
  5.         sortedList = SortedList()
  6.         start = nums[: k]
  7.         for a in start:
  8.             sortedList.add(a)
  9.             
  10.         def getMedian(sortedList):
  11.             if k % 2 == 1:
  12.                 return sortedList[k // 2]
  13.             else:
  14.                 return (sortedList[k // 2] + sortedList[k // 2 - 1]) / 2.0
  15.         
  16.         result.append(getMedian(sortedList))
  17.         n = len(nums)
  18.         for i in range(n - k):
  19.             to_remove_index = sortedList.bisect_left(nums[i])
  20.             sortedList.pop(to_remove_index)
  21.             sortedList.add(nums[i + k])
  22.             result.append(getMedian(sortedList))
  23.         
  24.         return result
复制代码
[/i][/i][/i]

评分

参与人数 1大米 +2 收起 理由
BreeKKK + 2 很有用的信息!

查看全部评分

扫码关注一亩三分地求职移民公众号
更多干货内容等你发现
回复

使用道具 举报

地里匿名用户
匿名用户-HPH2E  2021-4-23 22:18:52
本楼:   👍  0
0%
0%
0   👎
noi10 发表于 2021-4-23 14:10
请问76的最优解是什么?我是用HashMap加two pointer做的,没在discussion里找到更好的了。。。

我指的solution里的解法2:

Algorithm

We create a list called filtered\_Sfiltered_S which has all the characters from string SS along with their indices in SS, but these characters should be present in TT.


  1. S = "ABCDDDDDDEEAFFBC" T = "ABC"
  2.   filtered_S = [(0, 'A'), (1, 'B'), (2, 'C'), (11, 'A'), (14, 'B'), (15, 'C')]
  3.   Here (0, 'A') means in string S character A is at index 0.

复制代码



We can now follow our sliding window approach on the smaller string filtered\_Sfiltered_S.

评分

参与人数 1大米 +2 收起 理由
noi10 + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

noi10 2021-4-23 10:46:26 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   281
90%
10%
30
我昨天面别的公司,也面到第五题,也是用two heaps,但先写了一个不slide的,然后slide的时候interviewer表示remove(object)需要O(N),他希望有更好的
讨论了半天在他的引导下说出BST,然后我也挂了
回复

使用道具 举报

noi10 2021-4-23 10:53:25 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   281
90%
10%
30
第二轮 2k个点,不是一共有2k-1条path吗?这样?

1----2-----3
    7       |
  /          |
4--5-------6
回复

使用道具 举报

noi10 2021-4-23 12:00:37 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   281
90%
10%
30
KaWing 发表于 2021-4-23 11:35
[mw_shl_code=python,true]class Solution:
    def medianSlidingWindow(self, nums: List, k: int) -> ...

和这个solution一样是吗?
https://leetcode.com/problems/sl ... ing-two-Tree-Sets-O(n-logk

这题我前不久才刷过,然而面的时候没想起来。。。
回复

使用道具 举报

noi10 2021-4-23 14:10:00 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   281
90%
10%
30
请问76的最优解是什么?我是用HashMap加two pointer做的,没在discussion里找到更好的了。。。
回复

使用道具 举报

noi10 2021-4-23 14:22:32 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   281
90%
10%
30
第二题不用遍历board,sort nodes either by row or column,然后按照sort好的顺序挨个连就行了
回复

使用道具 举报

sean900531 2021-4-24 00:49:50 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   23
96%
4%
1
感谢楼主的分享!!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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