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


一亩三分地论坛

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

狗家实习新鲜面经

[复制链接] |试试Instant~ |关注本帖
江渚散人 发表于 2017-11-11 04:44:08 | 显示全部楼层 |阅读模式

2018(7-9月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚面完2轮背靠背,即将再面NVIDIA2轮背靠背,赶紧来地里攒人品。

1.given a binary tree, delete the bad edge. follow up given a binary search tree
bad edge要想,哪些情况。一面估计跪了。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
2. given a target node in a directed graph, find the shortest cycle including this node, return the whole path.
输入可以自己随便设计。
国人姐姐全程不交流不给提示。。愣是最后做出来了。。但是不是最优解,空间复杂度高了点。但是也要怪我,才知道面试hint要自己去要的。

攒人品求offer,呜呜呜呜



补充内容 (2017-11-11 04:44):. more info on 1point3acres.com
还有求大米么么哒

评分

4

查看全部评分

本帖被以下淘专辑推荐:

张欣 发表于 2017-11-14 08:50:05 | 显示全部楼层
江渚散人 发表于 2017-11-11 15:18
bad edge就是会导致二叉树不对的edge,面试官的想法应该是让我自己想有哪些情况。。。
第二题bfs用hashm ...

请问楼主 hashmap存前继节点 难道不会又key冲突的情况?不知道是什么个存法诶 感谢
回复 支持 0 反对 1

使用道具 举报

qpalzm0827 发表于 2017-11-11 06:20:18 | 显示全部楼层
第一题bad edge是什么意思?
第二题是用BFS, 然后找到第一个visited的node? 这样空间复杂度是O(|V|), 怎么优化呢?
回复 支持 反对

使用道具 举报

fanlala 发表于 2017-11-11 09:54:39 | 显示全部楼层
同求问第一题啥意思啊
回复 支持 反对

使用道具 举报

570468837 发表于 2017-11-11 11:29:53 | 显示全部楼层
已加米。想问下LZ,
第一题的bad edge只有一个吗?tree的数据结构是只有left, right节点吗?如果是的话,bad edge是不是就是形成环的edge?.鐣欏璁哄潧-涓浜-涓夊垎鍦
Follow up的binary search tree的bad edge有什么区别吗?
回复 支持 反对

使用道具 举报

Lizard squad 发表于 2017-11-11 13:11:32 | 显示全部楼层
楼主能仔细说一下第一题吗?还有第二题该怎么做?如果直接用bfs, 那怎么输出那条最短路径?还是得用backtrack来找最短路径吧,但是这样复杂度确实就很高了。
回复 支持 反对

使用道具 举报

 楼主| 江渚散人 发表于 2017-11-11 15:17:33 | 显示全部楼层
qpalzm0827 发表于 2017-11-11 06:20
第一题bad edge是什么意思?
第二题是用BFS, 然后找到第一个visited的node? 这样空间复杂度是O(|V|), 怎么 ...

bad edge就是会导致二叉树不对的edge,面试官的想法应该是让我自己想有哪些情况。。。
回复 支持 反对

使用道具 举报

 楼主| 江渚散人 发表于 2017-11-11 15:18:36 | 显示全部楼层
Lizard squad 发表于 2017-11-11 13:11
楼主能仔细说一下第一题吗?还有第二题该怎么做?如果直接用bfs, 那怎么输出那条最短路径?还是得用backtr ...

bad edge就是会导致二叉树不对的edge,面试官的想法应该是让我自己想有哪些情况。。。
第二题bfs用hashmap存前继结点,然后找到最短circle,倒着走一下就好
回复 支持 反对

使用道具 举报

 楼主| 江渚散人 发表于 2017-11-11 15:19:01 | 显示全部楼层
570468837 发表于 2017-11-11 11:29
已加米。想问下LZ,. 1point3acres.com/bbs
第一题的bad edge只有一个吗?tree的数据结构是只有left, right节点吗?如果是的话,b ...

bad edge应该有2个,结点有2个parent,还有成环
回复 支持 反对

使用道具 举报

 楼主| 江渚散人 发表于 2017-11-11 15:19:38 | 显示全部楼层
fanlala 发表于 2017-11-11 09:54. from: 1point3acres.com/bbs
同求问第一题啥意思啊

看其他回复~
回复 支持 反对

使用道具 举报

xinxinzhenbang 发表于 2017-11-13 10:20:07 | 显示全部楼层
楼主您好,
1.两个parent就是成环了。
2.是有一个bad edge还是有很多bad edge?. visit 1point3acres.com for more.
3.BST
   1
  / \
2    3
去除完应该是13还是null呢
祝曹叔叔早日拿到offer
回复 支持 反对

使用道具 举报

 楼主| 江渚散人 发表于 2017-11-13 10:22:36 | 显示全部楼层
应该只有一个。BST应该不是构造错误而是同样bad edge。这个我和面试官也没有讨论到
回复 支持 反对

使用道具 举报

 楼主| 江渚散人 发表于 2017-11-13 10:44:22 | 显示全部楼层
xinxinzhenbang 发表于 2017-11-13 10:20
楼主您好,. 1point3acres.com/bbs
1.两个parent就是成环了。
2.是有一个bad edge还是有很多bad edge?

应该只有一个。BST应该不是构造错误而是同样bad edge。这个我和面试官也没有讨论到
还有。你是谁!
回复 支持 反对

使用道具 举报

张欣 发表于 2017-11-14 08:47:24 | 显示全部楼层
qpalzm0827 发表于 2017-11-11 06:20
第一题bad edge是什么意思?
第二题是用BFS, 然后找到第一个visited的node? 这样空间复杂度是O(|V|), 怎么 ...

. 1point 3acres 璁哄潧应该不是找到第一个visited的node就结束吧,因为有可能给定的node不在环里,所以应该是又visit到给定node才对吧 ?
回复 支持 反对

使用道具 举报

 楼主| 江渚散人 发表于 2017-11-14 08:57:21 | 显示全部楼层
张欣 发表于 2017-11-14 08:50
请问楼主 hashmap存前继节点 难道不会又key冲突的情况?不知道是什么个存法诶 感谢

你访问过的结点直接跳过,所以key不会冲突。
回复 支持 反对

使用道具 举报

三根呆毛 发表于 2017-11-16 09:48:41 | 显示全部楼层
強啊(布丁布丁布丁
回复 支持 反对

使用道具 举报

lxc0694 发表于 4 天前 | 显示全部楼层
感觉用DFS 会不会更清楚点呢  一直往下搜索 遇到visit的结点跳过,到了没有邻接点 (for循环结束)就返回 知道找到目标结点。这样也更容易输出整个路径上的结点
回复 支持 反对

使用道具 举报

 楼主| 江渚散人 发表于 4 天前 | 显示全部楼层
lxc0694 发表于 2017-11-21 04:59
感觉用DFS 会不会更清楚点呢  一直往下搜索 遇到visit的结点跳过,到了没有邻接点 (for循环结束)就返回 知 ...

但是要找的是最短的路径呀,这样bfs比dfs好吧
回复 支持 反对

使用道具 举报

Corey_Lancer 发表于 4 天前 | 显示全部楼层
江渚散人 发表于 2017-11-21 05:46
但是要找的是最短的路径呀,这样bfs比dfs好吧
. 鍥磋鎴戜滑@1point 3 acres
LZ有结果了么。。
回复 支持 反对

使用道具 举报

 楼主| 江渚散人 发表于 4 天前 | 显示全部楼层
Corey_Lancer 发表于 2017-11-21 08:16-google 1point3acres
LZ有结果了么。。

被拒了字数字数
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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