一亩三分地论坛

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

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

9/29 LinkedIn SF office onsite

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

2016(7-9月) 码农类 硕士 全职@Linkedin - 内推 - 技术电面 Onsite |Fail其他

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

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

x
一直从地里获取信息,今天第一次发帖,回馈地里,希望能够帮到大家。

电面:
1. LC 65, Valid Number
面试官对限制条件说得并不是很清楚,就说你写吧。跟他简单商量了一下,最后我只考虑了leading/trailing spaces和小数点,指数的情况我问了,他说不用考虑了。没有LC上的难。
.1point3acres缃
2. LC 170, Two Sum III
Discuss里有人讨论了不同方法的tradeoff,面试的时候就问到了,先写了一种方法,分析了复杂度,接着又写了另一种方法。原题,不难。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

电面完没几天就通知onsite。

onsite:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
SF的office今年三月份才开始使用,整个building都是他们的。面试是在一个小房间里,十六层,view特别好,视野开阔,有海有桥的。白板上写着"Welcome In XXX",还有小礼物,挺用心的。

先跟HR见了个面,说了说今天的安排,畅想了一下美好的未来,说是面完了2到5天就有结果啊,offer等着你啊,公司benefits好啊,你要放松啊,你要加油啊。。。

Coding 1
(1) 从一个数组里找出能够组成三角形的三个数。没见过。. 鍥磋鎴戜滑@1point 3 acres
当时脑子一时短路,一组数据也没试,给出了一种方法,其实是错的。有可能是当时我没说清楚,面试官说应该没问题,写完后他说貌似不对啊。。。我换了一种方法,two pointers,复杂度是O(n^2)。他说你再想想吧,有O(n)的,要是想不出来你就先写这个吧。想了半天想出来了,结果时间不够了,他说别写了,知道我懂了。
方法貌似不是很难。比如 1 2 3 3,1 + 2 == 3 <= 3, 这种情况下1就可以不考虑了,用到了不等式的性质。即使 1 3 3 是一个结果,2 3 3 也是一个结果,1 + 3 < 2 + 3,所以1就不用考虑了。

(2) LC 200, Number of Islands
原题。说了思路,算是常规吧,扫描,看到1加1,然后用dfs去flip。面试官一开始貌似没理解,试了几个例子,觉得没问题让我写了。.1point3acres缃

Coding 2
LC 265, Paint House II
这道题当天早上看面经看到了,心中窃喜。在Discuss里看到了大神给出的最优解,O(nk),constant space。我就把这种方法说了,结果悲剧了。有可能是我说不清楚,面试官一直没理解,我又举例子又画图的,将近半小时后面试官恍然大悟,让我写了。五分钟写完代码,在接下来的讨论中,我发现面试官其实还是没理解,我的哥。。。接下来先让我跑了个他的test,过了,他不服,当场想例子要challenge大神的最优解,结果可想而知啊。最后他应该是懂了,说了个“酷”。一个小时就这么过去了,只写了一道题。说实话啊,这个方法虽说比较巧妙,但还不至于辣么巧妙啊,我那天早上看的,看了看大神简短的解释和整洁的代码,二十分钟也就搞定了,不知道咋回事儿。.鐣欏璁哄潧-涓浜-涓夊垎鍦

我觉得大家面算法的时候一定要跟面试官解释清楚,确定面试官理解了再写,否则时间就白白浪费了。解释dp的时候还是先从比较直接的方法开始比较好,如果有需要再慢慢优化,一上来就给最优解有时确实不太好理解。

午餐
这个必须要提一下。一个中国小哥带我吃的,人特别好,给我推荐了好吃的饭菜和甜点。LinkedIn的食堂确实好啊,中餐的味道很不错。吃饭的时候小哥说了LinkedIn的很多好,能看出来在那工作还是很开心的,谈话的内容也为下午和manage聊提供了很多素材,赞一个。
. Waral 鍗氬鏈夋洿澶氭枃绔,
Manager
人很nice,比较好聊,问了些常规的问题,比如你在上一份工作里有没有得到什么mentorship啊,我也根据中午的聊天内容问了些问题。我看他一直在那写,你问的问题他也会做记录,不知道用来干啥。
.鏈枃鍘熷垱鑷1point3acres璁哄潧问了一道小设计题。大家知道有些工作在LinkedIn上能直接申请,点那个“Apply”按钮。问题是如果让你设计你会考虑那些问题。他就说你尽量想吧,想不出来告诉他一声。我就想到三个。考虑多少人会用,从而知道QPS。因为要把用户的信息发给第三方网站,感觉要考虑隐私。有的工作需要cover letter有的不需要,感觉需要考虑data format。他接着又问需要返回什么error。我也只想到了三个。我说有的job过期了,需要返回error。第三方网站挂了需要返回一下。各种network connection,比如前后端连接,service和db之间的连接。前两个他说行,第三个他就说还好。说实话不太知道他想问啥。。。. From 1point 3acres bbs

Technical Communication. 鍥磋鎴戜滑@1point 3 acres
讲了个project。小哥挺活泼的,简单问了问。有几个问题自己以前没仔细考虑过。最大的难点?在test过程中哪部分最容易出错?如果重来,你会对哪部分做修改?大家有时间可以考虑一下啊。

System Design
LinkedIn有个share功能,在里面会出现一些URL,问题是找出在过去一天,一小时,五分钟被share的top 5/10/...多的URL。. From 1point 3acres bbs

以前没面过这种,有点儿没底,还好面试官很nice,会给提示。

算是两部分吧。当用户分享的时候,这里有一个client-server。当用户query top 5/10/...多的URL的时候,这里还有一个client-server。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

先说第一部分。一开始说我们有10M users,我上过XX算法的系统设计,按照里面的方法,先算了QPS,面试官用自己的电脑给算的,大概150。没等我开口,面试官说要考虑Peak QPS哦,我说那就3X吧,450,他表示同意。我一看不是很高,感觉DB有很多选择,就先试试MySQL吧,还能跟面试官讨论一下。结果面试官说不用把这些数据存起来,第二天就不用了。感觉这是在给我提示。我说那就用in-memory key-value store吧,memcached,key是URL,value是count。说实话我不是很懂这些NoSQL的工具,没上手用过,这样瞎扯真是没底。DB算是先选好了。我接着说加个"URL Extractor"service吧,用户把请求发过来,这个service把URL找出来然后存到数据库里。他问如果想让用户得到快速的响应应该咋办。这里我也不太懂,他说你加个message queue,Kafka那种,类似producer-consumer。这个我是真不知道。然后就是如何把统计数据加起来了,这里也有点儿不太会。我的疑问是咋判断URL在过去的五分钟里出现过呢?他说你可以用好几个db。一开始真的没懂。他看我没懂,说第一个db存0~5min的,第二个db存6~10min的,等等,还有存过去一个小时的,一天的。我一开始还是没懂,比如说我想要3min~8min的咋办?一开始我没问,想了一会儿才问,他说不用太real time,忘跟你说了,不好意思。他说其实要做到3min~8min也行,你有60个db就好了,到时候一加就行了。

接下来就是咋找出来top5/10/...的URL了,窃以为要用heap啥的呢,面试官说memcached功能不太行啊,对value部分没啥操作啊,你换个别的吧。我一想那就Redis吧,听说那个比较厉害,有一些set操作啥的,直接找出top多的URL。面试官表示一拍即合,Redis应该是不错的选择。我说再加个service吧,用于处理这些请求。他说怎么处理这些请求呢?是直接从数据库里读数据还是咋办?我一想这是read-only啊,加个cache吧,另一个deamon定时去读数据库做计算,然后把算好的数据写到cache里,用户直接读cache就行了,反正也不用太real time。他表示同意,然后时间就到了。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我只能给出这么多了,只想出了working solution,都没问啥scale方面的,希望大神能做个补充,让我开阔一下眼界。

写得不是很好,大家凑和看看吧,主要是想给没面过system design的小伙伴们找找感觉。我在网上没找到比较具体的,所以准备的时候比较忐忑,只看到题目“LinkedIn有个share功能,在里面会出现一些URL,问题是找出在过去一天,一小时,五分钟被share的top 5/10/...多的URL。”表示很懵逼。我的这个面试官会一直给出提示,还挺好的。

周一接到电话说是跪了,feedback也没有,说是有更强的选手呢。

感觉LinkedIn是有题库的,面试题基本在面经里都出现过。
希望能够帮到大家。也希望自己在接下来的面试里能够好好表现,早日找到工作。

-google 1point3acres
补充内容 (2016-10-10 11:13):
三角形那道题,输入不是排好序的,面试官的意思是排好序后O(n)啊,大家联系语境感受一下吧,就那个意思啊。谢谢楼下指出。

评分

2

查看全部评分

wtcupup 发表于 2016-10-10 05:54:17 | 显示全部楼层
楼主事在职跳槽?
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-10-10 05:58:37 | 显示全部楼层
问下楼主技术电面前有没有和HR约电话,约了的话多久后给安排面试呢?谢谢
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-10-10 08:05:30 | 显示全部楼层
找三角形咋能O(n)? 给的是排序好的?
回复 支持 反对

使用道具 举报

 楼主| larry514 发表于 2016-10-10 11:05:57 | 显示全部楼层
houqingniao 发表于 2016-10-10 08:05
找三角形咋能O(n)? 给的是排序好的?

他的意思是排好序后扫描一遍,不好意思没说清楚,我马上去改。谢谢。
回复 支持 反对

使用道具 举报

 楼主| larry514 发表于 2016-10-10 11:07:56 | 显示全部楼层
jy_121 发表于 2016-10-10 05:58
问下楼主技术电面前有没有和HR约电话,约了的话多久后给安排面试呢?谢谢

约了。他问我想啥时候面,我故意拖了几天。具体忘了。不好意思啊。
回复 支持 反对

使用道具 举报

 楼主| larry514 发表于 2016-10-10 11:10:10 | 显示全部楼层
wtcupup 发表于 2016-10-10 05:54
楼主事在职跳槽?

算是吧,说来话长了。
回复 支持 反对

使用道具 举报

hunter12345654 发表于 2016-10-12 07:02:22 | 显示全部楼层
找三角形是随便找一组就行还是要找所有的呀?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-12 07:12:24 | 显示全部楼层
larry514 发表于 2016-10-10 11:07
约了。他问我想啥时候面,我故意拖了几天。具体忘了。不好意思啊。

请问楼主内推以后多久得到的回复呀?
回复 支持 反对

使用道具 举报

 楼主| larry514 发表于 2016-10-12 07:13:03 | 显示全部楼层
hunter12345654 发表于 2016-10-12 07:02
找三角形是随便找一组就行还是要找所有的呀?

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴找一组就行了。
回复 支持 反对

使用道具 举报

 楼主| larry514 发表于 2016-10-12 07:23:11 | 显示全部楼层
小A要当码农 发表于 2016-10-12 07:12
请问楼主内推以后多久得到的回复呀?

http://www.1point3acres.com/bbs/thread-198901-1-1.html
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这里找的内推。很快啊。不到一周吧。
回复 支持 反对

使用道具 举报

say543 发表于 2016-10-12 14:17:23 | 显示全部楼层
larry514 发表于 2016-10-10 11:05
他的意思是排好序后扫描一遍,不好意思没说清楚,我马上去改。谢谢。

LZ coding challenge 第一题 我想不出o(n)的方法 能说说解法吗 ? 只有o(n^2)...
回复 支持 反对

使用道具 举报

say543 发表于 2016-10-12 14:21:28 | 显示全部楼层
larry514 发表于 2016-10-10 11:05
他的意思是排好序后扫描一遍,不好意思没说清楚,我马上去改。谢谢。

後來看到只找一組  那是不是i =0 , j =0, k = length-1 然後一直內縮k-- 就能找到解 such nums+ nums[j] > nums[k]  ? 因为sort 过后nums[0], nums[1] 是最小的
回复 支持 反对

使用道具 举报

相位疯脸 发表于 2016-10-12 14:31:33 | 显示全部楼层
感觉LZ被第二轮面试官坑了,他家对速度要求非常高,只做一道题,哪怕是因为面试官没懂,绝对不是一件好事。。。
回复 支持 反对

使用道具 举报

 楼主| larry514 发表于 2016-10-13 09:53:00 | 显示全部楼层
相位疯脸 发表于 2016-10-12 14:31.1point3acres缃
感觉LZ被第二轮面试官坑了,他家对速度要求非常高,只做一道题,哪怕是因为面试官没懂,绝对不是一件好事。 ...

在以后的面试中还是得注意这些啊,还得顺着面试官来,尽量说得清楚一些。就当积累经验吧。
回复 支持 反对

使用道具 举报

 楼主| larry514 发表于 2016-10-13 09:59:56 | 显示全部楼层
say543 发表于 2016-10-12 14:21
後來看到只找一組  那是不是i =0 , j =0, k = length-1 然後一直內縮k-- 就能找到解 such nums+ nums[j]  ...

for (int i = 0; i < nums.size() - 2; ++i) {
    if (nums + nums[i + 1] > nums[i + 2]) {
        return vector<int>{nums, nums[i + 1], nums[i + 2]};
    }. Waral 鍗氬鏈夋洿澶氭枃绔,
}

return {};
.鐣欏璁哄潧-涓浜-涓夊垎鍦
1 2 3 3.鏈枃鍘熷垱鑷1point3acres璁哄潧
1和2最小,但不会是答案,只看最小的貌似不行,我一开始也是这么想的。

不知道我理解得对不对。
回复 支持 反对

使用道具 举报

woaibai 发表于 2016-10-13 10:55:03 | 显示全部楼层
三角形解法

//http://www.geeksforgeeks.org/find-number-of-triangles-possible/

        public int findNumberOfTriangles(int nums[])
        {
                int count = 0;. Waral 鍗氬鏈夋洿澶氭枃绔,
                Arrays.sort(nums);
                for (int i = 0; i < nums.length; i++) {
                        int j = i + 1;
                        int k = i + 2;
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷                        while (j < k && k < nums.length) {
                                int a = nums[i];. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                int b = nums[j];
                                int c = nums[k];
                                int sum = a + b;
                                if (sum > c) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                        count += k - j ;
                                        k++;. 1point 3acres 璁哄潧
                                } else j++;
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        }
                }
                return count;
        }
.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 反对

使用道具 举报

say543 发表于 2016-10-14 12:28:48 | 显示全部楼层
larry514 发表于 2016-10-13 09:59. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
for (int i = 0; i < nums.size() - 2; ++i) {-google 1point3acres
    if (nums + nums > nums) {
        return vector{ ...

写了下 先sort 然后依序找 测试如果只找一个因该行 楼主看看
  1. public  ArrayList<Integer> findAvaTrian(int [] values){
  2.    
  3.    
  4.     //bound
  5.     .鐣欏璁哄潧-涓浜-涓夊垎鍦
  6.    
  7.     Arrays.sort(values);
  8.     . 鍥磋鎴戜滑@1point 3 acres
  9.     ArrayList<Integer> res = new ArrayList<Integer>();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  10.     int i = 0;-google 1point3acres
  11.     int j = 1;
  12.     int k= j+1;
  13.     while (i < values.length && j < values.length && k < values.length){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  14.          if (values[i] + values[j] > values[k]){
  15.            res = new ArrayList<Integer>();
  16.            res.add(values[i]);. From 1point 3acres bbs
  17.            res.add(values[j]);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  18.            res.add(values[k]);
  19.            return res;
  20.          }else{
  21.            //[i, j] with folloiwng k cannot form a valid triangle due to sort propoerty
  22.            // also  value[j] >=[i] , replace i wtih j as the first index will not eliminate.鐣欏璁哄潧-涓浜-涓夊垎鍦
  23.            // possible solutions
  24.            //same condition applys [j] <=[k]
  25.            //in conclusion, basically [j, k] as the next [i, j] pair  
  26.            i = j;.1point3acres缃
  27.            j = k;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  28.            k = k+1;
  29.          } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  30.     }
  31.     -google 1point3acres
  32.     return res;
  33.     -google 1point3acres
  34.   }
复制代码
回复 支持 反对

使用道具 举报

say543 发表于 2016-10-14 14:33:42 | 显示全部楼层
想讨论一下system design 如果data 第二天就不用了 感觉没有DB 的必要 直接cache 做 可行 问题在于 如果是cache 怎么存 0-5min or 6min - 10min 感觉定点time 可以? 但是range 要survery一下..
回复 支持 反对

使用道具 举报

howeflguap 发表于 2016-10-17 06:07:40 | 显示全部楼层
第一题如果只要求其中任意一组解,那可以遍历排序后的数组,单纯只看三个连续相邻的元素,找到即输出,最终也没找到那解就为空。如果需要输出所有的解,那似乎不可能线性时间完成。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 04:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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