查看: 3218|回复: 29
收起左侧

fb top kth这道题真的好难

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   57% (236)
 
 
42% (177)    👎

2022(10-12月) 码农类General 本科 实习@Facebook - 网上海投 - Onsite  | 🙁 Negative 😣 HardFail | 应届毕业生

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

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

x
加面被问top kth
刷题的时候直接quick select模板套上就没多想了 结果真考这道题 首先description不知道怎么说磕磕绊绊的 然后是dry run 在coderpad上 好几个指针 又是两个while loop + recursion.... 我现在也没想出来该怎么描述那个swap的逻辑(为什么swap swap干吗) 标准答案的描述应该是这样
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式 这道题communication真的好难 lc hard是想出来难 这道题应该是communication hard....

评分

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

查看全部评分


上一篇:2022 Software Engineer Intern OA | 暑期实习 OA
下一篇:microsoft data&applied science intern
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   97% (480)
 
 
2% (14)    👎
本帖最后由 安然的拐子 于 2021-10-21 16:36 编辑

这个我总结的经验就是最关键的点在partition function里的swap那一步。其实可以想象成每一次call partition需要把小于pivot的值甩到左边去,那么假设现在arr <= pivot_val我们就需要进行swap。然后select里主要就是要说清楚左右boundary update的情况。贡献一个自己总结的python快排模板,有问题一起讨论

        def select(l, r, k):
            # pay attention to the stopping criterion
            if 0 < k <= r-l+1:
                pivot_idx = partition(l, r)
                num_selected = pivot_idx-l+1
                if num_selected == k:
                    return nums[pivot_idx]
                elif num_selected < k:
                    return select(pivot_idx+1, r, k-num_selected)
                else:
                    return select(l, pivot_idx-1, k)
            
        def partition(l, r):
            # pivot = nums[r]
            # pivot_idx = l
            # optimized random pivot
            rand_idx = random.randint(l,r)
            nums[rand_idx], nums[r] = nums[r], nums[rand_idx]
            pivot = nums[r]
            pivot_idx = l
            
            for i in range(l, r):
                if nums <= pivot:
                    nums, nums[pivot_idx] = nums[pivot_idx], nums
                    pivot_idx += 1
            
            nums[pivot_idx], nums[r] = nums[r], nums[pivot_idx]
            return pivot_idx

评分

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

查看全部评分

回复

使用道具 举报

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   93% (5087)
 
 
6% (362)    👎
bhtocq 发表于 2021-10-21 15:48
面试官让我选 我就用最优解写了呗

我觉得 这种情况一定要选PQ的solution 快选解释起来很难 其实是给自己下绊子。。而且不同的template写出来的东西也不一样
回复

使用道具 举报

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (186)
 
 
0% (1)    👎
这题的partition是找到随机点的在排序好数组中的index,也就是说知道了这个点在排序好数组中的位置。
因为我们只想知道top K的元素,不需要sort整个array,通过这种方法我们可以通过不排序整个数组而找到top K的元素这样。

(不过其实我不太明白为什么时间是O(n),是因为上面的binary search是logN然后partition也是logN然后最后相乘得到的O(n)吗?)
lz想问一下这题有follow up吗?说实话我也一直都是做的快排方法heap都没太看。。。
回复

使用道具 举报

 楼主| bhtocq 2021-10-22 03:12:04 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   57% (236)
 
 
42% (177)    👎
外加它指针更新频繁 一时间没想到好方法能快速walk throught 我记得原来某offer的课是给讲怎么walk through的 我当时听还觉得浪费时间 T.T 想死
回复

使用道具 举报

地里的匿名用户
匿名用户-856  发表于 2021-10-22 04:00:45
本楼: 👍   0% (0)
 
 
0% (0)   👎
可以问下intern也有可能被加面吗 一般什么情况会加面呀
回复

使用道具 举报

 楼主| bhtocq 2021-10-22 04:02:39 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   57% (236)
 
 
42% (177)    👎
匿名者 发表于 2021-10-21 13:00
可以问下intern也有可能被加面吗 一般什么情况会加面呀

你要是问我 加面被挂的情况 那我就觉得就是想挂你的时候给你加面....我一个没人权的被面试者没有上帝视角不好意思
回复

使用道具 举报

地里的匿名用户
匿名用户-F27  发表于 2021-10-22 04:16:03
本楼: 👍   0% (0)
 
 
0% (0)   👎
本帖最后由 匿名 于 2021-10-21 16:17 编辑

我觉得quickselect最难解释的是每次partition的random pivot如何解释,这个感觉可以和面试官交流。有的面试官觉得麻烦可能会直接让你跳过partition的解释。 当真正掌握模板了,剩下的就是自己多模拟几次dry run一定要讲出来,才能知道原来会做和会说是两回事!Anyway,楼主加油!!
回复

使用道具 举报

 楼主| bhtocq 2021-10-22 05:02:39 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   57% (236)
 
 
42% (177)    👎
匿名者 发表于 2021-10-21 13:16
我觉得quickselect最难解释的是每次partition的random pivot如何解释,这个感觉可以和面试官交流。有的面试 ...

请问你都是怎么dry run的呢 感觉在coderpad上很不方便
回复

使用道具 举报

 楼主| bhtocq 2021-10-22 05:05:47 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   57% (236)
 
 
42% (177)    👎
安然的拐子 发表于 2021-10-21 13:35
这个我总结的经验就是最关键的点在partition function里的swap那一步。其实可以想象成每一次call partition ...

请问层主是怎么dry run的呢 在coderpad上移动指针 还是一行一行 记录output这种 层主好人 看了层主点拨明白了一些TAT 已加米
回复

使用道具 举报

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   95% (2313)
 
 
4% (97)    👎
quick select/quick sort这个题目的关键是在纸上能把思路解释清楚,然后算法很自然就出来了。刷了好几次这种题目才记住一点,靠背不可取。

1. choose pivot to sort;
2. swap so that left < pivot and right >= pivot。 这里面有好几种写法,挑一种最容易解释的多写几次
3. divide and conquer;

swap的原因当然是为了不需要额外的memory。这种题最好先解释清楚再写。。。

评分

参与人数 1大米 +1 收起 理由
bhtocq + 1 赞一个

查看全部评分

回复

使用道具 举报

 楼主| bhtocq 2021-10-22 05:17:12 来自APP | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   57% (236)
 
 
42% (177)    👎
lllxin37 发表于 2021-10-21 14:14:06
quick select/quick sort这个题目的关键是在纸上能把思路解释清楚,然后算法很自然就出来了。刷了好几次这种题目才记住一点,靠背不可取。

1. choose pivot to s
啊对是的 想起来了TAT  不知道为什么当时死活没想起来
回复

使用道具 举报

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

本版积分规则

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