一亩三分地论坛

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

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

不龙伯格两轮游

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

2016(4-6月) 码农类 硕士 全职@Bloomberg - 网上海投 - Onsite |Failfresh grad应届毕业生

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

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

x
第一轮,先问简历。  
1: rotate linked list
2:binary tree path sum
设计:这儿说不太清楚, 是关于股票的数据结构, 用到了union find。 感觉这轮面的不错, design一把思路讲出来面官就懂了, 估计和他想的一样。

第二轮, 一个中国senior 和一个 欧洲口音senior。 中国人感觉挺友好的,欧洲人从头到尾一脸老子欠他一百万的样子。
一上来也是先问简历。
然后欧洲人说了个很傻逼的问题。
画了个杨辉三角形。
说你能不能想一个data structure 去返回第i 行第j 列的值。
我逼逼了一下突然反应到组合数, 就说了直接算组合数,这样不就O(1)了么。 . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
结果这个欧洲人说, 你能不能想想data structure呢? 如果这个第一行不是从 1 开始呢?
感觉日了狗了。 没想到什么好的解法, 除了暴力。
然后每一行因为是对称的,所以这里可以优化下。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
欧洲人一脸不屑的表情。。。显然不满意。
这时候时间没剩多少了。
中国大哥给了个设计餐馆订座系统的问题, 感觉也就是走走过场吧, 期间感觉到欧洲人已经不想浪费时间了。
然后被hr滚粗。
祝大家好运。
加分

评分

3

查看全部评分

何打发123 发表于 2016-8-18 23:51:22 | 显示全部楼层
第二题想不出来呀。。 现在除了想到用一个dp[][] 存每个位置的值 这样如果经常call就不用重复计算。。0.0 data structure想不出来。。 各位有什么想法吗 T T 楼主您的组合数是怎么做呢?0.0
回复 支持 反对

使用道具 举报

 楼主| omega094 发表于 2016-8-19 00:31:00 | 显示全部楼层
何打发123 发表于 2016-8-18 23:51
第二题想不出来呀。。 现在除了想到用一个dp[][] 存每个位置的值 这样如果经常call就不用重复计算。。0.0 d ...

组合数就是C(i,j), 这就是O(1) 解法了。
如果说数据结构的话。
因为每一行的只取决于前一行的。
所以我当时给的是个queue, 但这和brute force 其实没有什么区别。
所以我也不知道哪个欧洲人想要什么。
如果说这个问题本来就可以O(1) 解决掉,你让我设计个数据结构来解决。
又要时间又要空间的话。。。。那point 在哪里呢?
感觉这个问题本身就有问题。。。。
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-19 00:38:46 | 显示全部楼层
omega094 发表于 2016-8-19 00:31
组合数就是C(i,j), 这就是O(1) 解法了。
如果说数据结构的话。
因为每一行的只取决于前一行的。
...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
对的 我去lc上看了看 的确是有一个题目是要求用O(K)的办法来优化这个问题  但是如果需要call 很多次的话 每一次计算都要算一次  所以二维的话 就是用空间换时间啦 至今没有get到面试官的考点在哪里。。。  以及 中国大哥没有帮你嘛!!  以及。。 楼主我还是没有弄懂这题和排列组合有什么关系啊 T T    求举个栗子好吗  [.1point3acres缃
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
[1,4,6,4,1]
]
回复 支持 反对

使用道具 举报

 楼主| omega094 发表于 2016-8-19 00:46:02 | 显示全部楼层
何打发123 发表于 2016-8-19 00:38
对的 我去lc上看了看 的确是有一个题目是要求用O(K)的办法来优化这个问题  但是如果需要call 很多次的话  ...

第n行的m个数可表示为 C(n-1,m-1),即为从n-1个不同元素中取m-1个元素的组合数。
我觉得中国大哥那时候估计也看到大势已去了,帮也没啥用了。。。。
而且我觉得这两个人是分别出题的。。。。中国大哥之前也不知道这个欧洲人会出这个题目。。。
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2016-9-18 12:13:50 | 显示全部楼层

如果是考虑到大量重复利用的话。
最直观就来个HashMap得了。Key是坐标(行和列),value就是其值
然后做个记录,这个hashMap 存到了第几行的第几个数字。
如果要求的新坐标大于记录范围,则从记录点开始一直计算到新坐标。
考虑边界成本,这就是O(1)..1point3acres缃
然后可以利用楼主的对称优化只存一半数据。

计算组合数本身也是有运算时间的。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
要不把累乘的结果也存到DP中?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

a27400 发表于 2016-9-18 13:55:06 | 显示全部楼层
组合数不是O(1)的好吧…
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-9-18 23:27:47 | 显示全部楼层
alucardzhou 发表于 2016-9-18 12:13
如果是考虑到大量重复利用的话。. from: 1point3acres.com/bbs
最直观就来个HashMap得了。Key是坐标(行和列),value就是其值
.1point3acres缃 ...

如果是大量重复利用的话 那就直接用dp呀0.0 存储某个位置的值?
回复 支持 反对

使用道具 举报

 楼主| omega094 发表于 2016-9-18 23:37:10 | 显示全部楼层
a27400 发表于 2016-9-18 13:55
组合数不是O(1)的好吧…

你直接算当然不是O(1)................
你知道这个问题最大的row 和col . from: 1point3acres.com/bbs
然后用一个array 存1 到 max val 的prefix multiplication。
那不就可以直接通过这个array 返回1 到 max val 的factorial 了。。。这个不难想到吧我觉得? 我当时也和他们讲了。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-9-18 23:38:46 | 显示全部楼层
omega094 发表于 2016-9-18 23:37
你直接算当然不是O(1)................
你知道这个问题最大的row 和col
然后用一个array 存1 到 max v ...

看了楼主面经 觉得楼主能力很强。。去bb简直overqualified.. 祝楼主有更好的offer~~
回复 支持 反对

使用道具 举报

 楼主| omega094 发表于 2016-9-18 23:43:04 | 显示全部楼层
何打发123 发表于 2016-9-18 23:38 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
看了楼主面经 觉得楼主能力很强。。去bb简直overqualified.. 祝楼主有更好的offer~~

不敢当。。。
已经拿到其他家offer了。。不过bb 给我的面试体验真的比较negative。。。
你也会拿到好offer的 :)
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-9-18 23:44:56 | 显示全部楼层
omega094 发表于 2016-9-18 23:43. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
不敢当。。。. more info on 1point3acres.com
已经拿到其他家offer了。。不过bb 给我的面试体验真的比较negative。。。
你也会拿到好of ...
.1point3acres缃
哪家啊!! 摸爬滚打求refer  啊楼主>.< 画风变得太快了。。。
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2016-9-19 00:12:43 | 显示全部楼层
omega094 发表于 2016-9-18 10:43
不敢当。。。
已经拿到其他家offer了。。不过bb 给我的面试体验真的比较negative。。。
你也会拿到好of ...


恭喜楼主
回复 支持 反对

使用道具 举报

gumhisoka 发表于 2016-10-2 10:29:33 | 显示全部楼层
楼主,我有个想法不知道对不对。我猜他想考的数据结构是这个(Leetcode):Populating Next Right Pointers in Each Node II

这个TreeNode本来就像杨辉三角,给的条件i行j列也满足这个结构的条件,况且这题也属于BB考过的范畴……
回复 支持 反对

使用道具 举报

cicean 发表于 2016-10-7 06:14:31 | 显示全部楼层
楼主欧洲 人问的有没有可能是个binary tree?

补充内容 (2016-10-7 06:14):
index tree

补充内容 (2016-10-7 06:16):
Fenwick tree or binary Index tree
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 13:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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