一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2367|回复: 24
收起左侧

非死不可 10/7 电面

[复制链接] |试试Instant~ |关注本帖
fantasiasango 发表于 2016-10-8 03:05:12 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
11:45结束的电面。. more info on 1point3acres.com

面试官是个印度小哥,叫kaanb,是infrastructure组的。晚了几分钟打过来,道了个歉。问了简历,从旧的跟他说,说了十几秒就被打断让说最新的。

说了3分钟最新的就被打断说我知道怎么回事了。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后做题:.鏈枃鍘熷垱鑷1point3acres璁哄潧

想想小哥出的题目挺简单的。

显示让写了个binary search,平时都用while写。突然面试不知道为啥本能就写recursive,结果mid不相等之后忘记mid - 1了。主函数那里穿参数array.length应该是len-1自己发现了。这个mid - 1是小哥提示了才发现。。他开始说的是我有个什么建议,我以为是干嘛,后来才听懂是说这段有个错误,而且不是类似leetcode那种input == null那种。后来他指出来说这俩循环,就是call左边或者右边的,有什么问题。我看了一眼发现传递的是mid而不是mid - 1。

接下来3sum。先写了naive的方法。问了复杂度。然后说怎么优化。2sum是不排序的,3sum之前做的时候是排序的,但是很久了不太记得要排序了。但是隐约记得是two pointer。所以先fix了i1,然后想用two point不过卡住了,因为还是n立方。发现不对劲。

过了大概1分钟,小哥问我怎么想的,我说我之前做了2sum,方法是hashmap,我在想怎么利用2sum的结论来做这个题。

于是强行缓存一遍数组,然后fix i1, fixi2 check map。N^2复杂度, N的空间复杂度。

然后小哥又说了半天我才明白他说naive的是立方时间,常数空间,我现在想改进时间,允许比常数空间多一些。我说想一想,还是得fix i1, i2也是得fix,那不还是得找i3。突然发现他一开始问的是binary search,我说你不会是让我用binary search吧,那是n^2logn的时间复杂度。。

完了就让我问问题,我才问了俩就到45分钟了直接就被告知感谢感谢,nice taking to you,good luck了。。

感觉小哥很犀利,而且掌控力很强,从一开始的各种打断到最后这个直接掐时间不让问问题了就能看出来。

大家Fighting啊!楼主找了半年工作了,有点疲惫了。


补充内容 (2016-10-8 11:38):.鏈枃鍘熷垱鑷1point3acres璁哄潧
当天晚上收到follow up phone interview邀请

评分

1

查看全部评分

iPhD 发表于 2016-10-8 05:44:40 | 显示全部楼层
芥末青豆 发表于 2016-10-8 05:34
确实是,楼主抽到的两道题都蛮高频的,也是算法常考的考点,Binary Search建议在理解的基础上结合模板,写 ...

请问同学你知道哪里有不排序O(n2)解决3 Sum,并且去掉重复解的代码吗?谢谢谢谢
回复 支持 1 反对 0

使用道具 举报

zfrancica 发表于 2016-10-8 03:23:15 | 显示全部楼层
我本来也是今天要电面 强行往后推了QWQ 感觉没准备好呢
这个面试小哥看起来有点恐怖啊otz
回复 支持 反对

使用道具 举报

 楼主| fantasiasango 发表于 2016-10-8 03:26:26 | 显示全部楼层
zfrancica 发表于 2016-10-8 03:23. 1point 3acres 璁哄潧
我本来也是今天要电面 强行往后推了QWQ 感觉没准备好呢. 鍥磋鎴戜滑@1point 3 acres
这个面试小哥看起来有点恐怖啊otz
. From 1point 3acres bbs
强势了些 除了有点口音说的很快 其他感觉挺好的
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-10-8 03:50:09 | 显示全部楼层
谢谢分钟。恭喜。 两道题目。稳了
回复 支持 反对

使用道具 举报

 楼主| fantasiasango 发表于 2016-10-8 04:42:02 | 显示全部楼层
leixiang5 发表于 2016-10-8 03:50
谢谢分钟。恭喜。 两道题目。稳了

. more info on 1point3acres.com不知道在说什么 = =
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-8 04:55:49 | 显示全部楼层
这个3 Sum和LC上的3 Sum有什么区别吗?还是只是楼主太紧张了,没写好?
回复 支持 反对

使用道具 举报

sooorrr 发表于 2016-10-8 04:57:30 | 显示全部楼层
上面的人怎么都只捡好听的说?我知道找工作都不易,不过LZ的问题还是要指出来。我当恶人好了。虽然这个面试官是烙印,不过也没看出恐怖在哪,根据描述只是很普通的店面啊?从这个面经来看,LZ做题还很不够。

找了半年工作没有好好刷题么?这两题都算是easy的了,最多不超过medium的难度, LZ做的却是磕磕碰碰,我看不出有什么好恭喜的。说话难听,不过希望LZ能早日拿到好Offer,但是首先要加强做题能力,除非你别的地方很牛。
回复 支持 反对

使用道具 举报

 楼主| fantasiasango 发表于 2016-10-8 04:58:09 | 显示全部楼层
iPhD 发表于 2016-10-8 04:55
这个3 Sum和LC上的3 Sum有什么区别吗?还是只是楼主太紧张了,没写好?

你好 没有区别
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-8 04:58:53 | 显示全部楼层
. 1point 3acres 璁哄潧
那用不到binary search吧?就sort然后2 pointers做?小哥要求必须用binary search?
回复 支持 反对

使用道具 举报

 楼主| fantasiasango 发表于 2016-10-8 04:58:57 | 显示全部楼层
sooorrr 发表于 2016-10-8 04:57
上面的人怎么都只捡好听的说?我知道找工作都不易,不过LZ的问题还是要指出来。我当恶人好了。虽然这个面试 ...

你好 你说的是对的 我是容易慌的那种 一慌就空白了。
回复 支持 反对

使用道具 举报

 楼主| fantasiasango 发表于 2016-10-8 04:59:29 | 显示全部楼层
iPhD 发表于 2016-10-8 04:58
那用不到binary search吧?就sort然后2 pointers做?小哥要求必须用binary search?

那是follow up的问题。我记得还有其他面经是问你如果不sort怎么做
回复 支持 反对

使用道具 举报

芥末青豆 发表于 2016-10-8 05:34:53 | 显示全部楼层
确实是,楼主抽到的两道题都蛮高频的,也是算法常考的考点,Binary Search建议在理解的基础上结合模板,写得更快也不容易出错。3Sum的naive solution可以作为解题的出发点和Interviewer讨论(先不直接写代码),然后做相应的optimize, 比如为何先排序,如何exclude duplicate triplets等等。这些都讨论清楚了可以开始写。我记得其他面经里有问到过如果不用排序的话,如何做到O(N^2)的时间复杂度,楼主也可以去看看。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
气势上不能输,但是也要讲求方法。共勉~
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-8 08:28:25 | 显示全部楼层
iPhD 发表于 2016-10-8 05:44
请问同学你知道哪里有不排序O(n2)解决3 Sum,并且去掉重复解的代码吗?谢谢谢谢

hashset的就可以吧 借鉴2sum..0.0
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-8 08:50:49 | 显示全部楼层
iPhD 发表于 2016-10-8 05:44
请问同学你知道哪里有不排序O(n2)解决3 Sum,并且去掉重复解的代码吗?谢谢谢谢

好像不对。。忽略我 T T 第一个没法差有木有重复。。
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-8 09:06:25 | 显示全部楼层
芥末青豆 发表于 2016-10-8 05:34. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
确实是,楼主抽到的两道题都蛮高频的,也是算法常考的考点,Binary Search建议在理解的基础上结合模板,写 ...

同问如何去重+不排序 而且n^2
回复 支持 反对

使用道具 举报

minggr 发表于 2016-10-8 12:41:24 | 显示全部楼层
不排序之前有个贴子说过,找不到了。
用hashtable,大概这样代码:

  1. class Solution {.1point3acres缃
  2. public:
  3.     string get_key(int n1, int n2, int n3){
  4.         int min_val, max_val;
  5.         min_val = n1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  6.         max_val = n1;
  7.         
  8.         if (n2 < min_val)
  9.             min_val = n2;
  10.         if (n2 > max_val)
  11.             max_val = n2;

  12. . visit 1point3acres.com for more.
  13.         if (n3 < min_val)
  14.             min_val = n3;. from: 1point3acres.com/bbs
  15.         if (n3 > max_val)
  16.             max_val = n3;
  17.             
  18.         string key = to_string(min_val);. from: 1point3acres.com/bbs
  19.         key += "@" + to_string(max_val);
  20.         
  21.         return key;
  22.     }.1point3acres缃

  23.     vector<vector<int>> threeSum(vector<int>& nums) {
  24.         unordered_map <int, int> hash;
  25.         vector<vector<int>> result;
  26.         unordered_set<string> set;
  27.         
  28.         for (int i: nums)
  29.             hash[i]++;. visit 1point3acres.com for more.
  30.             
  31.         for (int i: nums) {
  32.             int target = -i; . Waral 鍗氬鏈夋洿澶氭枃绔,
  33.             
  34.             if (hash[i]-- == 1). 1point3acres.com/bbs
  35.                 hash.erase(i); .鐣欏璁哄潧-涓浜-涓夊垎鍦
  36.                
  37.             for (auto p: hash) {
  38.                 int key = target - p.first; .鏈枃鍘熷垱鑷1point3acres璁哄潧
  39.                
  40.                 if (hash.count(key)) {
  41.                     if (key != p.first || p.second > 1) {. from: 1point3acres.com/bbs
  42.                         string set_key = get_key(i, p.first, key);
  43.                         if (set.count(set_key) == 0) {
  44.                             result.push_back(vector<int>{i, p.first, key});
  45.                             set.insert(set_key);. 1point3acres.com/bbs
  46.                         }
  47.                     }
  48.                 }
  49.             }
  50.         }
  51.         -google 1point3acres
  52.         return result;
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  53.     }
  54. };
复制代码
回复 支持 反对

使用道具 举报

huai10 发表于 2016-10-8 16:17:25 | 显示全部楼层
minggr 发表于 2016-10-8 12:41
不排序之前有个贴子说过,找不到了。
. From 1point 3acres bbs用hashtable,大概这样代码:

你直接固定第一个数然后后面按2sum做不是更好更简洁么。
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-8 23:18:07 | 显示全部楼层
huai10 发表于 2016-10-8 16:17
你直接固定第一个数然后后面按2sum做不是更好更简洁么。
. visit 1point3acres.com for more.
第一个数有重复咋办 不能排序不能直接和前面比较啊。。
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-10-9 00:12:06 | 显示全部楼层
minggr 发表于 2016-10-8 12:41
不排序之前有个贴子说过,找不到了。
用hashtable,大概这样代码:
. 鍥磋鎴戜滑@1point 3 acres
这个办法很好,学习了!我也去用java写一下
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 20:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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