一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1107|回复: 11
收起左侧

全新谷歌full time电面

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

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

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

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

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:. more info on 1point3acres.com
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. 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 自己是否是叶子节点. 1point 3acres 璁哄潧
然后,每一个新加的节点(parent, child),做这些: parent.leaf = false, child.maxval = max(parent.maxval, child.val),child.leaf = true
最后只要遍历leaf=true的即可
但我不知道这代码怎么写。。。。

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

使用道具 举报

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

补充内容 (2015-11-2 02:07):.鏈枃鍘熷垱鑷1point3acres璁哄潧
比如:一个简单例子。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题。
其它方法复杂 ...
. 鍥磋鎴戜滑@1point 3 acres
这种建树只是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:. Waral 鍗氬鏈夋洿澶氭枃绔,
  14.                 leaves.add(child)
  15.             allNodes.add(parent).1point3acres缃
  16.             allNodes.add(child)

  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]
  23.                 curMax = max(node, curMax)
  24.             curMax = max(node, curMax)
  25.             print leaf, curMax
复制代码
建树,然后DFS:
  1. class TreeNode:. Waral 鍗氬鏈夋洿澶氭枃绔,
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.children = []

  5. class Tree:
  6.     def __init__(self):
  7.         self.root = None
  8.         self.possibleRoots = set(). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  9.         self.nodes = {}

  10.     def insertEdge(self, parent, child):
  11.         if not self.root:
  12.             parentNode = TreeNode(parent)
  13.             childNode = TreeNode(child)
  14.             self.possibleRoots.add(parentNode)
  15.             parentNode.children.append(childNode)
  16.             self.nodes[parent] = parentNode.鐣欏璁哄潧-涓浜-涓夊垎鍦
  17.             self.nodes[child] = childNode. 鍥磋鎴戜滑@1point 3 acres
  18.         else:
  19.             if parent in self.nodes and child in self.nodes:
  20.                 self.nodes[parent].children.append(self.nodes[child])
  21.                 if self.nodes[child] in self.possibleRoots:
  22.                     self.possibleRoots.remove(self.nodes[child])
  23.             elif parent in self.nodes and child not in self.nodes:
  24.                 childNode = TreeNode(child)
  25.                 self.nodes[child] = childNode
  26.                 self.nodes[parent].children.append(childNode)
  27.             elif parent not in self.nodes and child in self.nodes:
  28.                 parentNode = TreeNode(parent)
  29.                 self.nodes[parent] = parentNode
  30.                 self.nodes[parent].children.apped(self.nodes[child])
  31.                 if self.nodes[child] in self.possibleRoots:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  32.                     self.possibleRoots.remove(self.nodes[child])
  33.                 self.possibleRoots.add(self.nodes[parent])
  34.             else:
  35.                 parentNode = TreeNode(parent)
  36.                 childNode = TreeNode(child)
  37.                 self.possibleRoots.add(parentNode)
  38.                 parentNode.children.append(childNode)
  39.                 self.nodes[parent] = parentNode
  40.                 self.nodes[child] = childNode
  41.         if len(self.possibleRoots) == 1:
  42.             self.root = list(self.possibleRoots)[0]
    .鐣欏璁哄潧-涓浜-涓夊垎鍦

  43.     def getLeafMax(self):
  44.         node = self.root
  45.         self.dfs(node, node.val)
  46. -google 1point3acres
  47.     def dfs(self, node, curMax):
  48.         if not node.children:
  49.             print node.val, curMax
  50.             return

  51.         for child in node.children:
  52.             self.dfs(child, max(curMax, child.val))
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

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

custom counter

GMT+8, 2016-12-7 04:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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