查看: 2045|回复: 11
收起左侧

2西格玛失败面经

|只看干货
匿名用户-0D3  2022-7-2 00:02:37 |阅读模式
本楼: 👍   100% (2)
 
 
0% (0)   👎

2022(4-6月) 码农类General 博士 全职@TwoSigma - 内推 - Onsite  | 😐 Neutral 😣 HardFail | 在职跳槽

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

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

x


几天前面的,三轮coding,题目都是地里见过的,是我自己学艺不精,但确实没想到三轮里面两轮design。

第一轮:design sql,实现create,insert,select功能。我是按照写一个class准备的,但是面试官强烈建议写两个class,我当时一头雾水,问他是不是把metadata放在一个class里面,value放另一个class。他不置可否,最后也没写出来。
第二轮:currency conversion,我用backtracking写了,超时的部分是准备用memoization做的,没想到lru_cache竟然还是超时,自己写memo没通过
第三轮:mouse抓cheese design,这个题其实比较绕,地里以前描述的不是很清楚,我觉得有必要说一下。因为看起来现在他们特别喜欢这种问题。这个题目就是要设计一个框架,让玩家在这个框架下面编程,记住是玩家编程让程序自动控制老鼠朝cheese方向移动,最后找到cheese。玩家并不直接操纵老鼠,玩家并不知道老鼠坐标和cheese位置,只有每一轮的距离信息,并根据距离
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
这种比较open的问题面试起来的问题在于,一旦和对方想得不一样,除非你最后做出来,都会出现一个让对方跟你的思路走,或者跟对方的思路走的问题,这种情况下思路一旦被打断都很难接回来,最后很容易挂掉。前车之鉴吧,还是希望大家多准备这种题目。



评分

参与人数 3大米 +7 收起 理由
Pandamo + 1
rumblewarrior + 1 很有用的信息!
清道神君 + 5

查看全部评分


上一篇:丢盒子VO
下一篇:金子人| Coderpad | SDE
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (167)
 
 
0% (1)    👎
zixunjian 发表于 2022-7-26 15:19
请问有没有什么 maximum k stops 这种限制?还有input 是什么? 是类似 (USD -> EUR: 0.98) 这种吗?

...

是np complete。

类似TSP,暴力搜所有permutation是n!,可以用DP改进到n^2*2^n,n超过8后优势明显(https://www.wolframalpha.com/input?i=plot+n%21+and+2%5En*n%5E2+from+n%3D1+to+n%3D12)

参考https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
本帖最后由 zixunjian 于 2022-7-26 00:30 编辑
jinyu500 发表于 2022-7-25 13:43
是。给定A B 找出A到B最大的rate

请问有没有什么 maximum k stops 这种限制?还有input 是什么? 是类似 (USD -> EUR: 0.98) 这种吗?

这题是np-hard啊。。 因为是longest path in undirected graph,或者说shortest path in undirected graph with negative edges, 不能用djikstra 也不能用bellman ford, 只能dfs, 但是应该是O(V * (V+E))。 够难得
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
本帖最后由 zixunjian 于 2022-7-26 03:04 编辑
zixunjian 发表于 2022-7-26 00:19
请问有没有什么 maximum k stops 这种限制?还有input 是什么? 是类似 (USD -> EUR: 0.98) 这种吗?

...

我又想了想,如果问题guarantee no negative cycles,也就是说不可能arbitrage, 用bellman-ford可以。 想不出来dfs/backtracking怎么可能memo。 感觉backtrack只能暴力。
回复

使用道具 举报

地里的匿名用户
匿名用户-A6B  2022-7-2 00:12:22
本楼: 👍   0% (0)
 
 
0% (0)   👎
好难,完全不知道怎么做
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (22)
 
 
0% (0)    👎
想问一下,楼主你有说target level吗,他家是没有system design的嘛?我过几天面他家,也是3轮,邮件里说都是coding,感觉过了之后应该就是3轮BQ了,但是我target senior level
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (16)
 
 
11% (2)    👎
657843069 发表于 2022-07-06 10:12:18
想问一下,楼主你有说target level吗,他家是没有system design的嘛?我过几天面他家,也是3轮,邮件里说都是coding,感觉过了之后应该就是3轮BQ了,但是我target sen
说实话我不知道我的target level,应该是进去后再分的。先过了coding再说吧,加油。
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
currency conversion 我到现在都没搞懂你怎么memo。 每一次选择都是不一样的, 你先选 CNY->USD 和 先 USD->CNY 是不一样的结果。
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (121)
 
 
0% (0)    👎
currency conversion我用的一个dfs和memoization,不知道对不对
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
currency conversion 这题具体是什么内容? 是要找best exchange rate是吗? 是这个题吗 https://leetcode.com/discuss/int ... o-currency2/1009696
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (16)
 
 
11% (2)    👎
zixunjian 发表于 2022-07-24 15:30:47
currency conversion 这题具体是什么内容? 是要找best exchange rate是吗? 是这个题吗 https://leetcode.com/discuss/interview
是。给定A B 找出A到B最大的rate
回复

使用道具 举报

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

本版积分规则

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