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


一亩三分地论坛

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

全新谷歌full time电面

[复制链接] |试试Instant~ |关注本帖
leoyue 发表于 2015-10-30 02:45:43 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 本科 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
给一堆(int, int)的input表示一个tree(不一定binary),前一个int表示parent,后一个表示child,对所有的leaf node,print自己的val 和 所有ancestor 的val中的最大值。面试官没讲清input的格式,太紧张没读懂题,估计黑了。

Ex. 5 10 表示 10是5的child 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
     5  15 表示 15 是 5 的另一个child
     output:
10 10
15 15

评分

2

查看全部评分

本帖被以下淘专辑推荐:

宝贝忆彼岸 发表于 2015-11-1 06:43:21 | 显示全部楼层
我的想法是先遍历一遍这一对(parent,child)对,然后用一个set放leaf,一个map放(child,parent)对,然后set里面的leaf用dfs向上找
parent,找最大的ancestor的值,这过程中可以用一个hashmap记录每个node的最大的ancestor,来避免重复寻找
回复 支持 1 反对 0

使用道具 举报

AndrewFish 发表于 2015-10-30 04:13:57 | 显示全部楼层
深度优先遍历的同时 maintain 路径上的最大节点应该可以解决吧?
回复 支持 反对

使用道具 举报

yanguango 发表于 2015-10-30 04:31:15 | 显示全部楼层
应该是首先建立二叉树,需要一个 HashMap 来记录 int -> node,然后 dfs
回复 支持 反对

使用道具 举报

 楼主| leoyue 发表于 2015-10-30 04:35:10 | 显示全部楼层
AndrewFish 发表于 2015-10-30 04:13. from: 1point3acres.com/bbs
深度优先遍历的同时 maintain 路径上的最大节点应该可以解决吧?

啊我后来想得是直接用map<int, int>来存,child做key, parent做value,一个个往回search,然后用一个vector吧来记所有的leaf node,每插入一个node就看有没有leaf node变成了非leaf。
回复 支持 反对

使用道具 举报

 楼主| leoyue 发表于 2015-10-30 04:40:14 | 显示全部楼层
另:如果可能的话求其它公司内推。。
回复 支持 反对

使用道具 举报

muancy 发表于 2015-11-1 10:00:16 | 显示全部楼层
LeetCode course schedule 的变种吧?
回复 支持 反对

使用道具 举报

dong882205 发表于 2015-11-1 23:53:17 | 显示全部楼层
额还没怎么刷LC,大神莫喷,但貌似不是Topological Sort,像是DP
我们给每个节点多包一层,储存: 自己的val, 目前为止从root到自己路径上最大的maxval, bool leaf 自己是否是叶子节点. more info on 1point3acres.com
然后,每一个新加的节点(parent, child),做这些: parent.leaf = false, child.maxval = max(parent.maxval, child.val),child.leaf = true. From 1point 3acres bbs
最后只要遍历leaf=true的即可
但我不知道这代码怎么写。。。。.1point3acres缃

补充内容 (2015-11-1 23:58):
噢存储的时候,不需要存父-子pair,用一个unordered_map<Node>存所有点即可,每次输入更新parent点和child点
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-2 02:01:36 | 显示全部楼层
这题应该正常方法解:就是建立一个树,然后DFS遍历。这题就是考你基本功。应该是warm up题。. from: 1point3acres.com/bbs
其它方法复杂,要好好想想才行。而且复杂度一样。. 1point3acres.com/bbs
你想复杂了。

补充内容 (2015-11-2 02:07):
比如:一个简单例子。1->2->3. 输入顺序是(2,3),(1,2)。.鐣欏璁哄潧-涓浜-涓夊垎鍦
你要怎样建立这个child-》parent的tree?
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-11-3 23:57:02 | 显示全部楼层
maomaoxiong 发表于 2015-11-2 02:01
这题应该正常方法解:就是建立一个树,然后DFS遍历。这题就是考你基本功。应该是warm up题。
其它方法复杂 ...

这种建树只是warm up么。。我觉得要处理顺序关系就好复杂,不是几行就能解决的呀。。
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-11-4 00:22:34 | 显示全部楼层
不建树:
  1. class SolutionWithoutTreeConstruction:
  2.     def getLeafMax(self, edges):
  3.         if not edges: return
  4.         leaves = set()
  5.         allNodes = set().鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.         parentMap = {}
  7. -google 1point3acres
  8.         # construct parentMap and leaf set. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  9.         # {10: 5, 15: 5, 5: 8, 6: 8, 7: 6}, set([10, 15, 7])
  10.         for parent, child in edges:
  11.             parentMap[child] = parent
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  12.             if parent in leaves:
  13.                 leaves.remove(parent)
  14.             if child not in allNodes:
  15.                 leaves.add(child)
    . 鍥磋鎴戜滑@1point 3 acres
  16.             allNodes.add(parent). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  17.             allNodes.add(child)

  18.         # Search for each leaf in the leaf set
  19.         for leaf in leaves:
  20.             curMax = leaf. 1point 3acres 璁哄潧
  21.             node = leaf
  22.             while node in parentMap:
  23.                 node = parentMap[node]
  24.                 curMax = max(node, curMax)
  25.             curMax = max(node, curMax)
  26.             print leaf, curMax
复制代码
建树,然后DFS:
  1. class TreeNode:
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.children = []
  5. . 1point3acres.com/bbs
  6. class Tree:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  7.     def __init__(self):
  8.         self.root = None
  9.         self.possibleRoots = set()
  10.         self.nodes = {}

  11.     def insertEdge(self, parent, child):
  12.         if not self.root:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.             parentNode = TreeNode(parent)
  14.             childNode = TreeNode(child)
  15.             self.possibleRoots.add(parentNode)
  16.             parentNode.children.append(childNode)
  17.             self.nodes[parent] = parentNode
  18.             self.nodes[child] = childNode
  19.         else:
  20.             if parent in self.nodes and child in self.nodes:. Waral 鍗氬鏈夋洿澶氭枃绔,
  21.                 self.nodes[parent].children.append(self.nodes[child])
  22.                 if self.nodes[child] in self.possibleRoots:
  23.                     self.possibleRoots.remove(self.nodes[child])
  24.             elif parent in self.nodes and child not in self.nodes:
  25.                 childNode = TreeNode(child)
  26.                 self.nodes[child] = childNode
  27.                 self.nodes[parent].children.append(childNode). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  28.             elif parent not in self.nodes and child in self.nodes:. from: 1point3acres.com/bbs
  29.                 parentNode = TreeNode(parent)
  30.                 self.nodes[parent] = parentNode
  31.                 self.nodes[parent].children.apped(self.nodes[child])
  32.                 if self.nodes[child] in self.possibleRoots:
  33.                     self.possibleRoots.remove(self.nodes[child])
  34.                 self.possibleRoots.add(self.nodes[parent])
  35.             else:
  36.                 parentNode = TreeNode(parent)
  37.                 childNode = TreeNode(child). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  38.                 self.possibleRoots.add(parentNode)
  39.                 parentNode.children.append(childNode) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  40.                 self.nodes[parent] = parentNode. from: 1point3acres.com/bbs
  41.                 self.nodes[child] = childNode
  42.         if len(self.possibleRoots) == 1:
  43.             self.root = list(self.possibleRoots)[0]

  44.     def getLeafMax(self):
  45.         node = self.root
  46.         self.dfs(node, node.val)

  47.     def dfs(self, node, curMax):
  48.         if not node.children:
  49.             print node.val, curMax
  50.             return
  51. . From 1point 3acres bbs
  52.         for child in node.children:
  53.             self.dfs(child, max(curMax, child.val))
复制代码
回复 支持 反对

使用道具 举报

jxyfwrj 发表于 2015-11-4 03:07:00 | 显示全部楼层
额,感觉这题是不是可以拿并查集union find来做?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-19 16:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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