May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1690|回复: 11
收起左侧

全新谷歌full time电面

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

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

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

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

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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
我的想法是先遍历一遍这一对(parent,child)对,然后用一个set放leaf,一个map放(child,parent)对,然后set里面的leaf用dfs向上找
parent,找最大的ancestor的值,这过程中可以用一个hashmap记录每个node的最大的ancestor,来避免重复寻找
回复 支持 1 反对 0

使用道具 举报

AndrewFish 发表于 2015-10-30 04:13:57 | 显示全部楼层
关注一亩三分地微博:
Warald
深度优先遍历的同时 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
深度优先遍历的同时 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 自己是否是叶子节点
然后,每一个新加的节点(parent, child),做这些: parent.leaf = false, child.maxval = max(parent.maxval, child.val),child.leaf = true
最后只要遍历leaf=true的即可. 鍥磋鎴戜滑@1point 3 acres
但我不知道这代码怎么写。。。。

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

使用道具 举报

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

补充内容 (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题。
其它方法复杂 ...
. 1point3acres.com/bbs
这种建树只是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()
  6.         parentMap = {}

  7.         # construct parentMap and leaf set
  8.         # {10: 5, 15: 5, 5: 8, 6: 8, 7: 6}, set([10, 15, 7])
  9.         for parent, child in edges:
  10.             parentMap[child] = parent
  11.             if parent in leaves:
  12.                 leaves.remove(parent)
  13.             if child not in allNodes:
  14.                 leaves.add(child)
  15.             allNodes.add(parent)
  16.             allNodes.add(child). more info on 1point3acres.com

  17.         # Search for each leaf in the leaf set. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  18.         for leaf in leaves:
  19.             curMax = leaf
  20.             node = leaf
  21.             while node in parentMap:
  22.                 node = parentMap[node].鏈枃鍘熷垱鑷1point3acres璁哄潧
  23.                 curMax = max(node, curMax)
  24.             curMax = max(node, curMax)
  25.             print leaf, curMax
复制代码
建树,然后DFS:
  1. class TreeNode:
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.children = []

  5. class Tree:. From 1point 3acres bbs
  6.     def __init__(self):
  7.         self.root = None
  8.         self.possibleRoots = set() 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9.         self.nodes = {}
  10. . 1point3acres.com/bbs
  11.     def insertEdge(self, parent, child):
  12.         if not self.root:.1point3acres缃
  13.             parentNode = TreeNode(parent)
    . From 1point 3acres bbs
  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:.1point3acres缃
  20.             if parent in self.nodes and child in self.nodes:-google 1point3acres
  21.                 self.nodes[parent].children.append(self.nodes[child]). from: 1point3acres.com/bbs
  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. Waral 鍗氬鏈夋洿澶氭枃绔,
  27.                 self.nodes[parent].children.append(childNode)
  28.             elif parent not in self.nodes and child in self.nodes:
  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]). visit 1point3acres.com for more.
  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. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  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). 1point 3acres 璁哄潧

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

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-5-27 14:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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