Airbnb 2018年春季E6 package

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1656|回复: 16
收起左侧

狗狗家昂赛

[复制链接] |试试Instant~ |关注本帖
我的人缘0
NANA1123 发表于 2017-11-14 06:17:27 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (31)
 
 
0% (0)  踩

2017(7-9月) 码农类General 硕士 全职@Google - 网上海投 - Onsite  | Pass | 在职跳槽

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

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

x
面经. from: 1point3acres
1. 判断数组中是否有value和index都递增的三个数
2. 一个8x8的board,空出第[0][0]格,如何用一个L形的板子把剩余位置都填满。L形板子占3格,形状是俄罗斯方块里的那个三个块组成的拐角。数据结构和表示自己设计。follow up是空出board上的任意一格,如何用L形板子填满. 围观我们@1point 3 acres
3. leetcode应该有类似的但是记不清了,转了几个弯,本质问题是stringA,stringB, 判断stringB是否包含stringA里的所有字母。
4. 专业面,但其实也是做题,比较开放也没啥代表性就不说了
5. leetcode里狗狗tag有的飞不同城市,求最大vacation day的数目
-google 1point3acres
最后是我想说的,去狗家onsite过两次,感觉狗家面试看面经用处实在不大,看到一些奇怪的题不会做反而会扰乱心绪。
狗家不会因为一场面试情况不好而拒人(我onsite第二面感觉面得挺差也给过了,听hr的意思是有几个strong hire)。
去纠结一些面经里出现一两次的题不如踏踏实实刷leetcode,基础打扎实了到场上随机应变。面狗狗还是得靠硬实力,毕竟碰到原题的概率实在不大。

最后祝各位都能拿到大offer!

评分

参与人数 4大米 +12 收起 理由
famillerose + 3 给你点个赞!
tomorrow203 + 3 很有用的信息!
k1938slll + 1 给你点个赞!
nsbdsxh + 5 很有用的信息!

查看全部评分


上一篇:打车公司实习电面第一轮
下一篇:空气床新鲜面经

本帖被以下淘专辑推荐:

我的人缘0
reliveinfire 发表于 2017-11-15 10:16:32 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
Urumic 发表于 2017-11-14 12:39
抛砖引玉啊,我先分享一下我第二题的想法吧,第二道题应该就是把矩阵每个点遍历一遍。 因为每个L都占三格, ...

第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满

再考虑4*4, 可以切成 4个2*2, (0,0)占用的那个2*2, 可以补满,

再用一个L各占用 右上2*2, 左下2*2, 右下2*2 的一格
化成row/col座标, 是用一个L放在4*4的 (2,1) (1,2) (2,2). 牛人云集,一亩三分地

8*8用4*4去延伸.即可.
程式码的话用divide and conquer 切块, 应该可以.1point3acres网

我也是看过才知道这样做, 自己也是想不出来...
回复

使用道具 举报

我的人缘0
张欣 发表于 2017-11-14 10:32:21 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  68% (54)
 
 
31% (25)  踩
先恭喜啦 翻译一下第一题是找是否存在一个上升子序列长度大于等于3? 感谢楼主 第二题可以讲下数据结构和表示思路吗 感谢
回复

使用道具 举报

我的人缘0
 楼主| NANA1123 发表于 2017-11-17 05:19:02 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (31)
 
 
0% (0)  踩
reliveinfire 发表于 2017-11-14 10:54
请问第一题怎么做呢?

用stack, O(N) 是否可行?

第一题有几种解法,题目要求三个数不一定是连续的

1. 暴力O(n^3)
2. 从前往后遍历,用数组pre[n]存储在i位时 0到i-1的最小值;
    从后往前遍历,用数组after[n]存储在i位时 i+1到n-1的最大值;
    再遍历一遍数组看是否存在pre < array < after
    O(n)time O(n) space
3. 遍历时存储前面元素的最小值min1,和第二小值min2, 和canidata_min, min1和min2要满足index递增,
    当前元素大于min1 小于min2时更新min2;当前元素小于min1时更新candidate_min; 当前元素大于
    candidate_min小于min2时更新min1,min2;当前元素大于min2返回true
    O(n)time O(1) space
   
回复

使用道具 举报

我的人缘0
Urumic 发表于 2017-11-14 12:39:21 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (39)
 
 
0% (0)  踩
抛砖引玉啊,我先分享一下我第二题的想法吧,第二道题应该就是把矩阵每个点遍历一遍。 因为每个L都占三格,所以当前格 (i, j) 会有三种情况(在L不旋转的情况下, 处于L的三个部位)。然而,不知道L能不能旋转,或者做镜面,这样的话就会有更多种情况,我没数清楚就先说是有N种情况吧。所以一个格子(i, j), 就有N种不同的L的摆法。每摆一次,就验证是否合法,如果合法,就把了当前L所占用的所有格子都标记下来。如果不合法,就回溯去掉当前L,换个姿势再摆。一直到所有格子都被标记。
. Waral 博客有更多文章,
怎么知道所有个字都标记呢,我们可以一边标记一边把当前合法的L的占用的格子数累加起来。到最后看看是不是等于8 x 8 - 1 (第一格不能用)。

求大家的做法。
回复

使用道具 举报

我的人缘0
reliveinfire 发表于 2017-11-14 10:54:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
请问第一题怎么做呢?
. 一亩-三分-地,独家发布
用stack, O(N) 是否可行?
还是需要像longest increase subsequence, O(N^2)?
回复

使用道具 举报

我的人缘0
丑猪宝 发表于 2017-11-15 10:28:06 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (32)
 
 
0% (0)  踩
谢谢楼主分享,请问面完多久通知过hc的?
回复

使用道具 举报

我的人缘0
cj.zheng 发表于 2017-11-15 11:07:58 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (23)
 
 
4% (1)  踩
reliveinfire 发表于 2017-11-15 10:16
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满

再考虑4*4, 可以切成 4个2*2, ( ...

如果要空出任意一格,divide&conquer能怎么分割?
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
nsbdsxh 发表于 2017-11-15 16:09:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (131)
 
 
4% (6)  踩
求解答,两个L型套在一起是形成2*2还是2*3
回复

使用道具 举报

我的人缘0
siranjoy119 发表于 2017-11-16 12:18:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (76)
 
 
6% (5)  踩
reliveinfire 发表于 2017-11-14 20:16. 留学申请论坛-一亩三分地
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满.留学论坛-一亩-三分地

再考虑4*4, 可以切成 4个2*2, ( ...
. 牛人云集,一亩三分地
好方法!follow up也可以这么解决。。。膜!
回复

使用道具 举报

我的人缘0
570468837 发表于 2017-11-16 12:24:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (24)
 
 
4% (1)  踩
reliveinfire 发表于 2017-11-15 10:16
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满

再考虑4*4, 可以切成 4个2*2, ( ...

2333那这道题岂不是不用coding了。。。
回复

使用道具 举报

我的人缘0
penggeqiang 发表于 2017-11-16 15:22:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (73)
 
 
9% (8)  踩
第2题, 可以暴力dfs吗
回复

使用道具 举报

我的人缘0
JohnnyHuo 发表于 2017-11-17 03:43:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
reliveinfire 发表于 2017-11-15 10:16
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满
. 围观我们@1point 3 acres
再考虑4*4, 可以切成 4个2*2, ( ...

followup 空出任意一格,怎么做呢?
回复

使用道具 举报

我的人缘0
 楼主| NANA1123 发表于 2017-11-17 05:02:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (31)
 
 
0% (0)  踩
reliveinfire 发表于 2017-11-15 10:16
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满.本文原创自1point3acres论坛

再考虑4*4, 可以切成 4个2*2, ( ...
. 牛人云集,一亩三分地
这个思路是对的,divide and conquer,用小L拼成大L,L型块是可以旋转的。用递归来解决。可惜我当时花了很久才想到这个思路也没写出完整的代码
回复

使用道具 举报

我的人缘0
Benbenbird 发表于 2017-11-17 05:27:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  0% (0)
 
 
0% (0)  踩
the first problem is 334. Increasing Triplet Subsequence? . 1point3acres
sorry, no chinese input right now.
回复

使用道具 举报

我的人缘0
 楼主| NANA1123 发表于 2017-11-17 05:38:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (31)
 
 
0% (0)  踩
Benbenbird 发表于 2017-11-17 05:27
the first problem is 334. Increasing Triplet Subsequence?
sorry, no chinese input right now.

没错,难怪当时看的觉得眼熟
回复

使用道具 举报

我的人缘0
YHYbrilliant123 发表于 2017-11-17 12:55:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (28)
 
 
3% (1)  踩
reliveinfire 发表于 2017-11-15 10:16
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满
. from: 1point3acres
再考虑4*4, 可以切成 4个2*2, ( ...

厉害厉害!膜拜
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-7-17 15:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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