《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 23084|回复: 58
收起左侧

Airbnb Onsite

  [复制链接] |试试Instant~ |关注本帖
wegnahz 发表于 2015-11-4 04:45:46 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Airbnb - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
上周面的airbnb已挂,既然你不给我offer那我就把题说了……语文不好题难描述请见谅……

三个coding面两个core value面。

1. 见下图 。给你一个字符对的转换matrix,表示这个字符对会转化成一个字符(但是有的字符对可能有多个能够转化成的字符,原文是nondeterministic)。以及若干个合法的终点(最顶上那一个点)状态,多次询问,每次一个字符串如果有一个方法能够走到合法状态就算是YES,否则NO.鐣欏璁哄潧-涓浜-涓夊垎鍦
解法:记忆化搜索,记录所有中间状态。因为转化矩阵和合法终点都是固定的,某个字符串要不永远是YES,要不永远是NO。最好写个类因为他后来说的……

2. N个员工,每个员工有若干个interval表示在这段时间是忙碌的。
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

但是我当时也不知道是脑抽了还是脑子太好用了,弄了个堆的,堆里N个元素,存每个员工的下一个端点,如果堆顶是某个员工的左端点就busy_employees加1,否则减1。这样好处是时间复杂度低了一点点,坏处是给面试官讲了半天而且代码不是太好写……不建议这么做. Waral 鍗氬鏈夋洿澶氭枃绔,


3. 见图,忘了这东西叫什么名字了。每次给你一个(x, y, iter),问你在iter这张图中在(x, y)坐标的点是第几个?. from: 1point3acres.com/bbs
解法:从大往小左,逐渐细化。每次先算出当前点在当前iter是在第几象限,先加上前面那些跳过去的象限里的点。然后找到这个点在这个象限的相对坐标新(x,y),但是还不够!对于三四象限的点,因为方向变了,需要做镜面映射,把(x,y)映射成(y,x) (第三象限) 或 (M-y, M-x) (第四象限),M是象限的长宽。

core value面完全就是问些莫名其妙的东西,比如你想去哪旅游。当然有一点要注意,Airbnb的优点不少在于便宜!而是在于能够更好的了解local culture,不管你认不认同都要这么说……

游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

补充内容 (2015-11-4 04:46):
最后一句话打错了,是“不是在于便宜”

评分

15

查看全部评分

本帖被以下淘专辑推荐:

jennyHappy 发表于 2017-4-25 11:29:21 | 显示全部楼层
第一题的记忆化搜索有一个重要的前提。让我们看一个例子
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
X        Y
B  D/C   A
A  B     C    D

如果 AB -> D 并且 AB->C。但是 BD->X,  CA -> Y。 那么ABC->X, BCD->Y,虽然我们可以记录这样的结论,但却不能说  ABCD->XY,因为  BD->X, CA->Y,C和D不能同时存在。除非题目中提到可以混用。否则记忆化搜索是无法进行的。
回复 支持 1 反对 2

使用道具 举报

gy21 发表于 2016-11-1 12:51:59 | 显示全部楼层
第一题看的我实在不明白 网上搜了搜,应该是这个。

给定一个固定的表比如:
                 (right). Waral 鍗氬鏈夋洿澶氭枃绔,
               __A__B___C_
            A |  B  AC  A
(left)     B |  C  A   C.鐣欏璁哄潧-涓浜-涓夊垎鍦
            C |  B  C   A

. 鍥磋鎴戜滑@1point 3 acres
这个表就意思是两个字母的组合的下一个结果。比如AC组合,结果查表可得出是A。. Waral 鍗氬鏈夋洿澶氭枃绔,
如果是BC组合,查表是AB,则说明结果可以是A或者B。


有了这个表,我们可以决定一个字符串如何往下推演直到只有一个字母。
比如给一个字符串"AC",很明显,推演结果直接就是"A"。
比如字符串"ABCC",第一轮我们每两个字母查表一次得出下一个字母。因为有的表中内
容是有多个字母,也就是有多个可能,所以整个推演结构会有不同的结果。
拿ABCC举例,结果如下(从下往上看):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
   A
  A B
A C A
A B C C 或者
.鏈枃鍘熷垱鑷1point3acres璁哄潧

   C
  A B
C C A
A B C C 等等。


现在要求给一个这样的表,一个初始字符串和终止结果(字母),要求反悔有没有可能
从初始字符串推到给定的终止结果。
比如ABCC, A。则返回true
AC, B。则返回false。

补充内容 (2016-10-31 20:53):. from: 1point3acres.com/bbs
这个例子感觉给错了,第二个第三行应该是ACA

补充内容 (2016-11-1 09:31):
应该还是CCA。因为表中的对应是A或者C,所以ACA或者CCA都可以。刚开始以为是and。。。
. more info on 1point3acres.com
补充内容 (2016-11-2 10:21):
写了下 ~
import java.util.*;;

public class pyramidsTransitionMatrix {
        public boolean checkIfOneLetter(char target, String input){
                List<String> res = new ArrayList<>();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                helper(res, inpu...
回复 支持 1 反对 0

使用道具 举报

 楼主| wegnahz 发表于 2015-11-17 04:55:53 | 显示全部楼层
woaibai 发表于 2015-11-13 06:58
a家onsite说是现场编程必须一遍过?可以自己看bug 但是如果通过跑测试再调程序就基本没戏了?

基本上是这样的,但其实脸也很重要
回复 支持 0 反对 1

使用道具 举报

gy21 发表于 2016-11-4 00:55:22 | 显示全部楼层
yucheyang2 发表于 2016-11-2 20:29
亲你的例子是不是有点儿错啊, ABCC 怎么到ACA 呀,感觉是每次两个相邻的边成一个字符?那就应该是ACC or ...

AB -> A or C; BC -> C;  CC -> A; 你去看lz画的图。。。我也是那么推出来的。
回复 支持 1 反对 0

使用道具 举报

woaibai 发表于 2015-11-4 12:26:47 | 显示全部楼层
没有design?
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-4 12:27:16 | 显示全部楼层
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
没有,简历都不怎么问
回复 支持 反对

使用道具 举报

mobileworld 发表于 2015-11-4 14:09:01 | 显示全部楼层
wegnahz 发表于 2015-11-4 12:27
没有,简历都不怎么问

感觉楼主答得可以啊,air家这么挑剔?
回复 支持 反对

使用道具 举报

lijing2441 发表于 2015-11-4 15:52:00 | 显示全部楼层
第三题是hilbert curve吧。。。
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-5 01:12:51 | 显示全部楼层
mobileworld 发表于 2015-11-4 14:09
感觉楼主答得可以啊,air家这么挑剔?

代码写的不是很顺利,第三题我当时自己也没完全弄明白太绕了
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-5 01:13:04 | 显示全部楼层
lijing2441 发表于 2015-11-4 15:52. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第三题是hilbert curve吧。。。

对我就想不起这个名字……
回复 支持 反对

使用道具 举报

mobileworld 发表于 2015-11-5 01:16:51 | 显示全部楼层
wegnahz 发表于 2015-11-5 01:12
代码写的不是很顺利,第三题我当时自己也没完全弄明白太绕了

对,确实很绕!
. Waral 鍗氬鏈夋洿澶氭枃绔,
对了,我过了电面,要准备onsite. 看他们家的面经,似乎觉得onsite的题目一般比电面的要难一点。不知道你有没有这个感觉? 多谢!
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-5 04:39:19 | 显示全部楼层
mobileworld 发表于 2015-11-5 01:16
对,确实很绕!

对了,我过了电面,要准备onsite. 看他们家的面经,似乎觉得onsite的题目一般比电面的 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
有,确实要难一点,而且一不小心写出bug就很囧。我个人觉得编译错误什么的无所谓, 但是bug就不大好。
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-5 04:39:32 | 显示全部楼层
mobileworld 发表于 2015-11-5 01:16
对,确实很绕!

对了,我过了电面,要准备onsite. 看他们家的面经,似乎觉得onsite的题目一般比电面的 ...

有,确实要难一点,而且一不小心写出bug就很囧。我个人觉得编译错误什么的无所谓, 但是bug就不大好。
回复 支持 反对

使用道具 举报

lijing2441 发表于 2015-11-5 17:40:09 | 显示全部楼层
wegnahz 发表于 2015-11-5 04:39
有,确实要难一点,而且一不小心写出bug就很囧。我个人觉得编译错误什么的无所谓, 但是bug就不大好。

个人感觉不是逻辑bug就还好,小bug倒是没关系,当场不用他提醒就自己改过来就ok。我三轮有一轮,index总是忘了加1或者忘了减1 ,不过最后也过了。.鏈枃鍘熷垱鑷1point3acres璁哄潧

当然,如果是逻辑bug就没什么好说的了。
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-11-6 00:18:54 | 显示全部楼层
第一题我有些没看明白,所谓合法的终点到底在你的图例中是否指的是A,B,C,D的上面那一排?
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-6 01:47:58 | 显示全部楼层
zhouyoung1124 发表于 2015-11-6 00:18. 1point 3acres 璁哄潧
第一题我有些没看明白,所谓合法的终点到底在你的图例中是否指的是A,B,C,D的上面那一排?
. visit 1point3acres.com for more.
终点就是只剩下一个字符的时候。在图里如果这个字符是C或者D就算合法的
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-11-6 11:40:21 | 显示全部楼层
lz能不能细说一下第一题是什么意思. 完全没看懂...input,output分别是什么?为什么图中有个accept?那个是矩阵,是input吗?
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-6 16:58:38 | 显示全部楼层
nothingtrouble 发表于 2015-11-6 11:40
lz能不能细说一下第一题是什么意思. 完全没看懂...input,output分别是什么?为什么图中有个accept?那个是 ...

可以想象成一个类,构造函数会把矩阵和accept传进去,然后每次的input是一个字符串。这个字符串经过若干次变换,每次变换长度减1,最后变成只有一个字符。Accept里面的任何一个字符都可以成为一个合法的最终状态
回复 支持 反对

使用道具 举报

hzding621 发表于 2015-11-6 17:40:04 | 显示全部楼层
第一题其实就是NFA to DFA transformation
回复 支持 反对

使用道具 举报

大傻杨 发表于 2015-11-8 19:14:43 | 显示全部楼层
同跪,同跪,同跪,
回复 支持 反对

使用道具 举报

woaibai 发表于 2015-11-13 06:58:24 | 显示全部楼层
a家onsite说是现场编程必须一遍过?可以自己看bug 但是如果通过跑测试再调程序就基本没戏了?
回复 支持 反对

使用道具 举报

woaibai 发表于 2015-11-17 05:21:32 | 显示全部楼层
wegnahz 发表于 2015-11-16 15:55. more info on 1point3acres.com
基本上是这样的,但其实脸也很重要

意思是长得难看的可以不用试了吗
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-25 12:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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