2西格玛失败面经

几天前面的，三轮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的问题面试起来的问题在于，一旦和对方想得不一样，除非你最后做出来，都会出现一个让对方跟你的思路走，或者跟对方的思路走的问题，这种情况下思路一旦被打断都很难接回来，最后很容易挂掉。前车之鉴吧，还是希望大家多准备这种题目。

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

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))。 够难得

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只能暴力。

好难，完全不知道怎么做

想问一下，楼主你有说target level吗，他家是没有system design的嘛？我过几天面他家，也是3轮，邮件里说都是coding，感觉过了之后应该就是3轮BQ了，但是我target senior level

657843069 发表于 2022-07-06 10:12:18
想问一下，楼主你有说target level吗，他家是没有system design的嘛？我过几天面他家，也是3轮，邮件里说都是coding，感觉过了之后应该就是3轮BQ了，但是我target sen

说实话我不知道我的target level，应该是进去后再分的。先过了coding再说吧，加油。

currency conversion 我到现在都没搞懂你怎么memo。 每一次选择都是不一样的， 你先选 CNY->USD 和 先 USD->CNY 是不一样的结果。

currency conversion我用的一个dfs和memoization，不知道对不对

currency conversion 这题具体是什么内容？ 是要找best exchange rate是吗？ 是这个题吗 https://leetcode.com/discuss/int ... o-currency2/1009696

zixunjian 发表于 2022-07-24 15:30:47
currency conversion 这题具体是什么内容？ 是要找best exchange rate是吗？ 是这个题吗 https://leetcode.com/discuss/interview

是。给定A B 找出A到B最大的rate