脸熟 新鲜面巾

刚面完，趁还记得，写个面经。

全程国人面试官，一共4轮。最后加了一轮实验轮（是老外）
第一轮，国人大神，利口三菱要。老实说写得不是很熟，只知道bfs的解法。然后呢，说完解法，问了复杂度，我说，这个得指数级。大神说，恩，这有点慢，我们来试试有没有O（n）的吧。然后在大神耐心的指导下，基本写出了code。其间各种引导我跨越edge case。中间有个bug自己发现然后改了，然后follow up说还有没有可以inprove的地方，不过已经不够时间了所以就结束了。终于体验到什么叫全程带飞。
第二轮，还是国人大哥，问了利口就是一。然后呢，我各种试图把递推式过一遍。然后推着推着就乱了。后来想着想着又改过来了。最后写完code跟面试官确认了一下，才发现02这种输入是完全把这input string invalidate，所以改了改初始条件。
中饭：台湾大哥带吃，campus好大，大哥问我想吃啥，我说听说有珍珠奶茶能带我去喝吗？大哥说，这里有珍珠，有奶茶，不过不放一齐卖。我囧，然后我说就随便吃个中餐吧。吃完大哥还特意给我

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

(2017-6-26 23:02):
啊，泄漏了，第二轮还有一个followup：如果现在字符跟数字之间的map不是连续的怎么办，复杂度是多少。例如：1 -> 36， 2 -> 200之类的。我说如果我们有reverse map的话，还是可以o n，这里好虚

补充内容 (2017-7-4 06:05):
收到recruiter电话说过了...太特么的感动了...T_T...愿天下刷题人与心仪公司终成眷属...

见过一个follow up，但是限制最大是两位，可以用map来存一下，解法还是一样的。但是如果你这个不知道多少位的，就麻烦了

熟狗脸 发表于 2017-6-27 09:05
301 这个题咋做O(n) ? 我只知道个dfs

根据我之前看过的面经，fb问的remove parenthese都是只要一个正确答案，而不是所有，所以走一遍O(n)就行，如果要找出所有，不可能O（n）搞定吧。
第二个decode way不是经典面经题吗，应该5-10分钟秒掉,follow up也是面经里有的。按这两道题的难度每轮都应该做2-3题，每轮只做一道题有些危险。一般来说每轮做两道是基本要求，如果做出3道加分
楼主面经准备的不熟，按这两道题都应该5-10分钟瞬秒的题

mameko 发表于 2017-6-27 20:43
其实我才发现我的是简化版，不用输出所有删除以后合法串，输出一个就好了。用栈就能搞定...

Thanks for clarification. I think using a counter to maintain the count difference between '(' and ')' should be able to replace the stack. It's done in two passes (assuming the given string is only one char extra from valid string.)

1. string RemoveInvalidParantheses(string s) {
   
2.   int counter = 0;
   
3.   for (auto i = s.begin(); i < s.end(); ++i)
   
4.   {
   
5.     if (*i == '(') ++counter;
   
6.     else if (*i == ')' && --counter < 0)
   
7.       return s.erase(i), s;
   
8.   }
   
9. 
   
10.   counter = 0;
    
11.   for (auto i = s.end()-1; i >= s.begin(); --i)
    
12.   {
    
13.     if (*i == ')') ++counter;
    
14.     else if (*i == '(' && --counter < 0)
    
15.       return s.erase(i), s;
    
16.   }
    
17.   return s;
    
18. }
    

复制代码

1 -> 36， 2 -> 200之类的。  那就是可以有n，不仅仅限制于一位或者两位？这样还能O（n)?

facebook onsite后两个星期，还没有消息。知道是什么情况吗？

我也是每轮一题，多出时间聊天

感谢楼主分享，请问楼主，第三轮设计太噗呃head是什么东西？

shian2008 发表于 2017-6-27 05:53
感谢楼主分享，请问楼主，第三轮设计太噗呃head是什么东西？

太噗呃  = type

感谢分享，请问一下第一个题On的思路可以分享一下吗

楼主威武，就是一==941？ 巴士吧==848？

同求第一题O（n） 思路， 目前我只知道最优dfs的解法，O（n） 的话要怎么做呀？

感觉第一题 只能做到最优o(n) 最差o(n2)吧？