📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 15
跳转到指定楼层
上一主题 下一主题
收起左侧

门冲电面compare tree diff

   
🔗
匿名用户-NSORH  2021-7-17 14:31:33 |倒序浏览

2021(7-9月) 码农类General 硕士 全职@doordash - 网上海投 - 技术电面  | | Pass | 在职跳槽

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 匿名 于 2021-7-17 02:33 编辑

经典面经题目,面试官结束的时候还夸了一波第一次见到有人一次写对的。面过之后三小时通知进入下一轮。

题目:给定两个n叉树,求这两个树之间有多少个节点差异。

您好!
本帖隐藏的内容需要积分高于 166 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 166 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies


附上鄙人的一个解法
您好!
本帖隐藏的内容需要积分高于 266 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 266 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies


希望帮到的看官加加米。

评分

参与人数 25大米 +45 收起 理由
cccrrr + 1 给你点个赞!
Eric0009 + 1 欢迎分享你知道的情况,会给更多积分奖励!
匿名用户-LS4YX + 12
guiguia + 1 很有用的信息!
stormrecluse + 1 给你点个赞!

查看全部评分


上一篇:LinkedIn Infra 电面+VO 过经
下一篇:WeRide OA4新鲜挂经

本帖被以下淘专辑推荐:

地里匿名用户
推荐
匿名用户-7O50L  2021-7-20 11:46:41
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

评分

参与人数 5大米 +14 收起 理由
cccrrr + 1 给你点个赞!
starrymao + 1 很有用的信息!
优优呦呦5 + 1 给你点个赞!
匿名用户-LS4YX + 10
youziwry + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

推荐
niubuzhi 2021-10-25 09:45:11 | 只看该作者
全局:
A very succinct solution using Python (please add rice if you like it !!!)
  1. class TreeNode(object):

  2.     def __init__(self, key, value):
  3.         self.key = key  # this should be unique; int
  4.         self.value = value # int
  5.         self.children = [] # list of TreeNodes
  6.         
  7. class Solution(object):

  8.     def countNodes(self, node):
  9.         if node is None:
  10.             return 0

  11.         count = 1
  12.         
  13.         for child in node.children:
  14.             count += self.countNodes(child)
  15.        
  16.         return count

  17.     def findDiffNodes(self, root1, root2):
  18.         
  19.         if root1 is None and root2 is None:
  20.             return 0
  21.         
  22.         if root1 is None or root2 is None or root1.key != root2.key:
  23.             return self.countNodes(root1) + self.countNodes(root2)
  24.         
  25.         diffCount = 0
  26.         
  27.         if root1.value != root2.value:
  28.             diffCount += 2
  29.             
  30.         childsMap1 = { child.key: child for child in root1.children }
  31.         childsMap2 = { child.key: child for child in root2.children }
  32.         
  33.         childsAllKeys = set(childsMap1.keys()).union(set(childsMap2.keys()))
  34.         
  35.         for childKey in childsAllKeys:
  36.             diffCount += self.findDiffNodes(childsMap1.get(childKey), childsMap2.get(childKey))
  37.             
  38.         return diffCount
复制代码

评分

参与人数 2大米 +2 收起 理由
CestSiBon + 1 很有用的信息!
zjspm + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

地里匿名用户
推荐
匿名用户-7O50L  2021-7-19 06:28:25
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

评分

参与人数 1大米 +8 收起 理由
匿名用户-LS4YX + 8

查看全部评分

回复

使用道具 举报

地里匿名用户
🔗
匿名用户-OXRJH  2021-7-18 03:04:40
楼主也是看了面经才过的吧?
回复

使用道具 举报

🔗
左飞机626 2021-7-18 15:37:50 | 只看该作者
全局:
楼主你要的查看积分能稍微低点吗?帮你加米
回复

使用道具 举报

🔗
lifengyi 2021-7-20 04:59:08 | 只看该作者
全局:
这题的follow up可以做的相当有难度
回复

使用道具 举报

全局:
匿名用户 发表于 2021-07-18 15:28:25
我也不夠分看答案, 但根自己對題目和要求的理解寫了以下的code

class TreeNode {
今天也碰到这题了,层主的解法有个问题。不能用sort,而是要转成hashmap找相同的key。比如abc和bc,单纯sort比的不对
回复

使用道具 举报

全局:
phmhmt2016 发表于 2021-7-19 20:19
今天也碰到这题了,层主的解法有个问题。不能用sort,而是要转成hashmap找相同的key。比如abc和bc,单纯so ...

请问children里如果多个node有相同的key怎么办呢?普通使用hashmap的话不好做呀。。
回复

使用道具 举报

全局:
taoyuanming886 发表于 2021-07-22 22:42:25
请问children里如果多个node有相同的key怎么办呢?普通使用hashmap的话不好做呀。。
这是个好问题,要问面试官,答案是key是唯一的
回复

使用道具 举报

🔗
yanzhufanchen 2021-7-24 04:57:39 | 只看该作者
全局:
phmhmt2016 发表于 2021-7-19 20:19
今天也碰到这题了,层主的解法有个问题。不能用sort,而是要转成hashmap找相同的key。比如abc和bc,单纯so ...

sort完之后用类似merge sort的two pointer办法就可以了吧
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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