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


一亩三分地论坛

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

狗狗家昂赛

[复制链接] |试试Instant~ |关注本帖
跳转到指定楼层
垅头
NANA1123 发表于 2017-11-14 06:17:27 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

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

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

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货
x
面经.鐣欏璁哄潧-涓€浜?涓夊垎鍦?/font>
1. 判断数组中是否有value和index都递增的三个数
2. 一个8x8的board,空出第[0][0]格,如何用一个L形的板子把剩余位置都填满。L形板子占3格,形状是俄罗斯方块里的那个三个块组成的拐角。数据结构和表示自己设计。follow up是空出board上的任意一格,如何用L形板子填满
3. leetcode应该有类似的但是记不清了,转了几个弯,本质问题是stringA,stringB, 判断stringB是否包含stringA里的所有字母。
4. 专业面,但其实也是做题,比较开放也没啥代表性就不说了
5. leetcode里狗狗tag有的飞不同城市,求最大vacation day的数目. 涓€浜?涓夊垎-鍦帮紝鐙鍙戝竷

最后是我想说的,去狗家onsite过两次,感觉狗家面试看面经用处实在不大,看到一些奇怪的题不会做反而会扰乱心绪。
狗家不会因为一场面试情况不好而拒人(我onsite第二面感觉面得挺差也给过了,听hr的意思是有几个strong hire)。
去纠结一些面经里出现一两次的题不如踏踏实实刷leetcode,基础打扎实了到场上随机应变。面狗狗还是得靠硬实力,毕竟碰到原题的概率实在不大。

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

评分

3 查看全部评分

本帖被以下淘专辑推荐:

推荐
reliveinfire 发表于 2017-11-15 10:16:32 | 只看该作者
Urumic 发表于 2017-11-14 12:39-google 1point3acres
抛砖引玉啊,我先分享一下我第二题的想法吧,第二道题应该就是把矩阵每个点遍历一遍。 因为每个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去延伸.即可.. more info on 1point3acres.com
程式码的话用divide and conquer 切块, 应该可以

我也是看过才知道这样做, 自己也是想不出来...
回复 支持 2 反对 0 使用道具 举报
推荐
张欣 发表于 2017-11-14 10:32:21 | 只看该作者
先恭喜啦 翻译一下第一题是找是否存在一个上升子序列长度大于等于3? 感谢楼主 第二题可以讲下数据结构和表示思路吗 感谢
回复 支持 2 反对 0 使用道具 举报
推荐
Urumic 发表于 2017-11-14 12:39:21 | 只看该作者
抛砖引玉啊,我先分享一下我第二题的想法吧,第二道题应该就是把矩阵每个点遍历一遍。 因为每个L都占三格,所以当前格 (i, j) 会有三种情况(在L不旋转的情况下, 处于L的三个部位)。然而,不知道L能不能旋转,或者做镜面,这样的话就会有更多种情况,我没数清楚就先说是有N种情况吧。所以一个格子(i, j), 就有N种不同的L的摆法。每摆一次,就验证是否合法,如果合法,就把了当前L所占用的所有格子都标记下来。如果不合法,就回溯去掉当前L,换个姿势再摆。一直到所有格子都被标记。

怎么知道所有个字都标记呢,我们可以一边标记一边把当前合法的L的占用的格子数累加起来。到最后看看是不是等于8 x 8 - 1 (第一格不能用)。

求大家的做法。
回复 支持 1 反对 0 使用道具 举报
推荐
 楼主| NANA1123 发表于 2017-11-17 05:19:02 | 只看该作者
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.鏈枃鍘熷垱鑷?point3acres璁哄潧
    O(n)time O(1) space
   
回复 支持 1 反对 0 使用道具 举报
板凳
reliveinfire 发表于 2017-11-14 10:54:05 | 只看该作者
请问第一题怎么做呢?. Waral 鍗氬鏈夋洿澶氭枃绔?
.1point3acres缃慄/font>
用stack, O(N) 是否可行?
还是需要像longest increase subsequence, O(N^2)?
回复 支持 反对 使用道具 举报
下水道
丑猪宝 发表于 2017-11-15 10:28:06 | 只看该作者
谢谢楼主分享,请问面完多久通知过hc的?
回复 支持 反对 使用道具 举报
地基
cj.zheng 发表于 2017-11-15 11:07:58 | 只看该作者
reliveinfire 发表于 2017-11-15 10:16
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满
. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
再考虑4*4, 可以切成 4个2*2, ( ...

如果要空出任意一格,divide&conquer能怎么分割?
回复 支持 反对 使用道具 举报
nsbdsxh 发表于 2017-11-15 16:09:14 | 只看该作者
求解答,两个L型套在一起是形成2*2还是2*3
回复 支持 反对 使用道具 举报
9
siranjoy119 发表于 2017-11-16 12:18:32 | 只看该作者
reliveinfire 发表于 2017-11-14 20:16. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满
. from: 1point3acres.com/bbs
再考虑4*4, 可以切成 4个2*2, ( ...
. 涓€浜?涓夊垎-鍦帮紝鐙鍙戝竷
好方法!follow up也可以这么解决。。。膜!
回复 支持 反对 使用道具 举报
10
570468837 发表于 2017-11-16 12:24:51 | 只看该作者
reliveinfire 发表于 2017-11-15 10:16
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满
. more info on 1point3acres.com
再考虑4*4, 可以切成 4个2*2, ( ...

2333那这道题岂不是不用coding了。。。
回复 支持 反对 使用道具 举报
11
penggeqiang 发表于 2017-11-16 15:22:37 | 只看该作者
第2题, 可以暴力dfs吗
回复 支持 反对 使用道具 举报
12
JohnnyHuo 发表于 2017-11-17 03:43:19 | 只看该作者
reliveinfire 发表于 2017-11-15 10:16. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满

再考虑4*4, 可以切成 4个2*2, ( ...
. from: 1point3acres.com/bbs
followup 空出任意一格,怎么做呢?
回复 支持 反对 使用道具 举报
13
 楼主| NANA1123 发表于 2017-11-17 05:02:17 | 只看该作者
reliveinfire 发表于 2017-11-15 10:16
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满

. 涓€浜?涓夊垎-鍦帮紝鐙鍙戝竷再考虑4*4, 可以切成 4个2*2, ( ...

这个思路是对的,divide and conquer,用小L拼成大L,L型块是可以旋转的。用递归来解决。可惜我当时花了很久才想到这个思路也没写出完整的代码
回复 支持 反对 使用道具 举报
15
Benbenbird 发表于 2017-11-17 05:27:52 | 只看该作者
the first problem is 334. Increasing Triplet Subsequence?
sorry, no chinese input right now.
回复 支持 反对 使用道具 举报
16
 楼主| NANA1123 发表于 2017-11-17 05:38:18 | 只看该作者
Benbenbird 发表于 2017-11-17 05:27
the first problem is 334. Increasing Triplet Subsequence?
sorry, no chinese input right now.
. more info on 1point3acres.com
没错,难怪当时看的觉得眼熟
回复 支持 反对 使用道具 举报
17
YHYbrilliant123 发表于 2017-11-17 12:55:01 | 只看该作者
reliveinfire 发表于 2017-11-15 10:16
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满
. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
再考虑4*4, 可以切成 4个2*2, ( ...

厉害厉害!膜拜
回复 支持 反对 使用道具 举报
本版积分规则
关闭

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

手机版|小黑屋|一亩三分地论坛声明 GMT+8, 2017-11-25 11:36
Powered by Discuz! X3 © 2001-2013 Comsenz Inc. Design By HUXTeam
快速回复 返回顶部 返回列表