【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

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

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

snapchat 电面

[复制链接] |试试Instant~ |关注本帖
wju 发表于 2016-11-10 10:39:11 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
给一个树的root node,返回same subtree及个数:
/*
                    10
                /        \
            8                3. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
          /  \            /     \
         4    5        8           5
             /       /   \        /
            3       4     5      3. 1point3acres.com/bbs
                         /
                        3
      Expects:
             8
            / \
           4   5      Count: 2
              /
             3

             5
            /         Count: 3
           3.鐣欏璁哄潧-涓浜-涓夊垎鍦
    */. 1point3acres.com/bbs
用递归的postorder traversal的方法+HashMap<String, Integer>()做,自下而上每个节点处得到一个关于以该节点为根的subtree的String,然后存入HashMap,最后根据HashMap判断.另外只有叶子的subtree不予考虑.

求加点大米,多谢. From 1point 3acres bbs

评分

2

查看全部评分

本帖被以下淘专辑推荐:

johnjavabean 发表于 2016-11-10 13:57:13 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
一个node的subtree算吗....其实这题考的就是serialise / deserialise binary tree? 至于要不要后续遍历其实无所谓吧...毕竟你所有节点开始的子树都要存一下的...

补充内容 (2016-11-10 14:46):
想了一下还是后序遍历省时间
回复 支持 1 反对 0

使用道具 举报

头像被屏蔽
幻灭天神 发表于 2016-12-19 08:55:07 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 1 反对 0

使用道具 举报

小A要当码农 发表于 2016-11-10 11:23:55 | 显示全部楼层
请问楼主,是说对每个节点preorder + inorder转成String一次么? 这样才能确定一棵树吧?
回复 支持 反对

使用道具 举报

在浙里 发表于 2016-11-10 11:32:13 | 显示全部楼层
感谢分享,感觉楼主能拿onsite
回复 支持 反对

使用道具 举报

工图新一 发表于 2016-11-10 11:50:52 | 显示全部楼层
小A要当码农 发表于 2016-11-10 11:23. 1point 3acres 璁哄潧
请问楼主,是说对每个节点preorder + inorder转成String一次么? 这样才能确定一棵树吧?

楼主的例子厘米有重复的node value,所以两个order转string结果不唯一,不能这样转
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-10 11:59:57 | 显示全部楼层
工图新一 发表于 2016-11-10 11:50
楼主的例子厘米有重复的node value,所以两个order转string结果不唯一,不能这样转

啥意思? 我对于null节点用“#”表示的话,两个order应该是可以转的吧?
回复 支持 反对

使用道具 举报

海盗包子 发表于 2016-11-10 12:19:26 | 显示全部楼层
小A要当码农 发表于 2016-11-10 11:59
啥意思? 我对于null节点用“#”表示的话,两个order应该是可以转的吧?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
null用#表示的话,只用存preorder,转string,就可以了吧?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-10 12:24:28 | 显示全部楼层
海盗包子 发表于 2016-11-10 12:19
null用#表示的话,只用存preorder,转string,就可以了吧?

对的。。我试了一下 好像可以
回复 支持 反对

使用道具 举报

 楼主| wju 发表于 2016-11-11 02:13:27 | 显示全部楼层
小A要当码农 发表于 2016-11-10 11:23. more info on 1point3acres.com
请问楼主,是说对每个节点preorder + inorder转成String一次么? 这样才能确定一棵树吧?
. 鍥磋鎴戜滑@1point 3 acres
只用postorder就行,但是把null node也表示出来,比如用"#"
回复 支持 反对

使用道具 举报

 楼主| wju 发表于 2016-11-11 02:17:26 | 显示全部楼层
海盗包子 发表于 2016-11-10 12:19. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
null用#表示的话,只用存preorder,转string,就可以了吧?

为什么用preorder?用postorder自下而上每到一个节点就可以得到一个string,在这个string的基础上再往上走就可以得到上一级节点的subtree的string
回复 支持 反对

使用道具 举报

海盗包子 发表于 2016-11-11 05:27:21 | 显示全部楼层
wju 发表于 2016-11-11 02:17
为什么用preorder?用postorder自下而上每到一个节点就可以得到一个string,在这个string的基础上再往上走 ...

我觉的preorder和postorder都可以的,做法一样的吧,用recursion写,唯一区别就是root值放前还是后
回复 支持 反对

使用道具 举报

Toby 发表于 2016-11-12 10:33:24 | 显示全部楼层
求问楼主收到onsite了吗?
回复 支持 反对

使用道具 举报

Jess. 发表于 2016-12-3 03:24:15 | 显示全部楼层
求问最后的输出 map 中的 key 是需要自己重新把 string 变回 node 存进去吗? 谢谢!
回复 支持 反对

使用道具 举报

 楼主| wju 发表于 2016-12-3 04:36:39 | 显示全部楼层
Jess. 发表于 2016-12-3 03:24
求问最后的输出 map 中的 key 是需要自己重新把 string 变回 node 存进去吗? 谢谢!

当时没做完,我的map里就存String,对于如何返回子树根节点,还没来得及做,你有什么方法吗
回复 支持 反对

使用道具 举报

豆虫 发表于 2016-12-3 10:58:12 | 显示全部楼层
谢谢楼主分享,感觉dfs+HashMap 可以做

补充内容 (2016-12-3 10:58):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
21 vector<pair<int,string> > CountSameTree(TreeNode *root){
22         unordered_map<string,int> Map;
23         vector<pair<int,string> > res;
24         dfs(Map,root);
25         for(auto it=Map.begin();it!=Map.end();it++){
26                 int SharpNum=0;
27                 for(char ch : it->first)if(ch=='#')SharpNum++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
28                 if(SharpNum==2)continue;   //single node leave
29                 if(it->second>1)res.push_back({it->second,it->first});. more info on 1point3acres.com
30         }
31         return res;
32 }
33
34 string dfs(unordered_map<string,int>& Map,TreeNode *cur){
35         if(!cur)return "#";
36         string res=to_string(cur->val)+"L:";. 鍥磋鎴戜滑@1point 3 acres
37         res+=dfs(Map,cur->left);
38         res+="R:";
39         res+=dfs(Map,cur->right);
40         Map[res]++;
41         return res;
42 }
回复 支持 反对

使用道具 举报

Jess. 发表于 2016-12-4 00:08:50 | 显示全部楼层
wju 发表于 2016-12-3 04:36
当时没做完,我的map里就存String,对于如何返回子树根节点,还没来得及做,你有什么方法吗

我想的是 map 存 string 和 node
回复 支持 反对

使用道具 举报

在浙里 发表于 2016-12-4 00:24:11 | 显示全部楼层
感谢分享,祝好运
回复 支持 反对

使用道具 举报

jyty 发表于 2016-12-30 01:37:26 | 显示全部楼层
幻灭天神 发表于 2016-12-19 08:55
用java写了下,求问Tree类的题目如何写test case比较快?

是不是可以单写一个TreeNode constructor 函数带三个value, 一个是自己的,另外两个是左右子树的
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-20 22:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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