一亩三分地论坛

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

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

16年1月Snapchat电面

[复制链接] |试试Instant~ |关注本帖
Kidsplay 发表于 2016-1-16 08:40:11 | 显示全部楼层 |阅读模式

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

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

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

x
1月14面了Snapchat电面。那天状态不好,准备得也不足。这道题不难,但还是写得特别烂。目测等一下就要收拒信了,而且也没签NDA,发出来让大家讨论一下吧~欢迎大牛贴思路
给一行String input,其中包括了若干条数据。每个数据的格式是(X,Y),代表一条从X指向Y的边。
要求是根据这样的输入,构建并打印二叉树的in-order traversal。注意只用打印就好。
同时,如果输入不合法,停止并打印错误。错误包括:有环,有大于两个子节点,有多个父节点,输入包含重复的边,等等。
. from: 1point3acres.com/bbs
其实不难,注意判断各种错误,而且打印的是中序遍历。注意时间和空间复杂度。注意代码整洁度。


今天还面了空气床,过两天收拒信了一起贴面经。
最近挂好多啊,求人品求米。

评分

1

查看全部评分

haoxuango 发表于 2016-1-16 09:40:10 | 显示全部楼层
楼主, 输入是标准输入中读进来吗
回复 支持 反对

使用道具 举报

 楼主| Kidsplay 发表于 2016-1-16 20:29:23 | 显示全部楼层
haoxuango 发表于 2016-1-15 20:40 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
楼主, 输入是标准输入中读进来吗

对的.鏈枃鍘熷垱鑷1point3acres璁哄潧
就是标准输入
回复 支持 反对

使用道具 举报

lrn0304 发表于 2016-1-17 00:01:09 | 显示全部楼层
所以楼主是先建树, 判断合法之后再打印的么
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-1-17 00:11:33 | 显示全部楼层
我怎么觉得此题甚难。。。
回复 支持 反对

使用道具 举报

chm34 发表于 2016-1-17 01:58:51 | 显示全部楼层
请问如何只根据(x,y)来判断y是x的左子树还是右子树呢
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-17 14:07:52 | 显示全部楼层
有问题请教一下LZ 1. undirected or directed? 2. 怎么判断左子树 or 右子树? 3. 多个connected components怎么办 4. snapchar 要自己处理IO 吗? 用google handout 面吗?
回复 支持 反对

使用道具 举报

haifengc 发表于 2016-1-18 02:16:00 | 显示全部楼层
楼主能不能讲讲怎么中序遍历的?谢谢。
回复 支持 反对

使用道具 举报

 楼主| Kidsplay 发表于 2016-1-18 05:54:47 | 显示全部楼层
haifengc 发表于 2016-1-17 13:16
楼主能不能讲讲怎么中序遍历的?谢谢。

肯定得构建图/树啊,构建好了以后直接递归 left child, self, right child就好了
回复 支持 反对

使用道具 举报

hakusama1024 发表于 2016-1-19 09:58:14 | 显示全部楼层
住楼主好运。请问能讲详细点不。输入的边是怎么构建树的。谢啦。
回复 支持 反对

使用道具 举报

 楼主| Kidsplay 发表于 2016-1-19 13:34:08 | 显示全部楼层
hakusama1024 发表于 2016-1-18 20:58
住楼主好运。请问能讲详细点不。输入的边是怎么构建树的。谢啦。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
比如(A,B)表示A是B的父节点
回复 支持 反对

使用道具 举报

 楼主| Kidsplay 发表于 2016-1-19 13:36:11 | 显示全部楼层
say543 发表于 2016-1-17 01:07
有问题请教一下LZ 1. undirected or directed? 2. 怎么判断左子树 or 右子树? 3. 多个connected components ...

1.directed
2.先出现的边就是左子树的边,不过这个可以跟面试官确定
3.非法
4.要的,是的
回复 支持 反对

使用道具 举报

 楼主| Kidsplay 发表于 2016-1-19 13:37:23 | 显示全部楼层
chm34 发表于 2016-1-16 12:58
请问如何只根据(x,y)来判断y是x的左子树还是右子树呢

可以跟面试官确定,不过他说如果先出现(x,y)再出现(x,z),就规定y是左结点z是右结点
回复 支持 反对

使用道具 举报

 楼主| Kidsplay 发表于 2016-1-19 13:38:26 | 显示全部楼层
lrn0304 发表于 2016-1-16 11:01. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
所以楼主是先建树, 判断合法之后再打印的么

是的呀,不过打印的时候发现不合法终止打印也可以,要求比较低。当然如果能牛到不建树直接on the fly打印也可以,不过听起来不太现实
回复 支持 反对

使用道具 举报

hitowings 发表于 2016-2-1 11:01:44 | 显示全部楼层
Kidsplay 发表于 2016-1-19 13:38
是的呀,不过打印的时候发现不合法终止打印也可以,要求比较低。当然如果能牛到不建树直接on the fly打印 ...

请问楼主建树的思路是怎样  感觉挺难啊
回复 支持 反对

使用道具 举报

syftalent 发表于 2016-2-10 03:51:17 | 显示全部楼层
有没有有思路如何判断有环? 难道要node有一个father属性一路回溯看有没有一样的?
回复 支持 反对

使用道具 举报

 楼主| Kidsplay 发表于 2016-2-18 12:37:48 | 显示全部楼层
syftalent 发表于 2016-2-9 14:51
有没有有思路如何判断有环? 难道要node有一个father属性一路回溯看有没有一样的?

判断有环方法很多的。。
.1point3acres缃
我现在已经记不太清了,比如你可以用表。对于这道题其实可以更简单,打印的时候发现点超了就可以认为是有环了
回复 支持 反对

使用道具 举报

lotustree86 发表于 2016-3-3 14:45:31 | 显示全部楼层
这个题其实就是leetcode graph valid tree的变形,要求更严了必须是二叉树,也就是1.任何一个node的max outdegree is 2, indegree is 0 or 1, and only 1 node has 0 indegree.
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-4-15 11:17:04 | 显示全部楼层
这题主要就是处理输入构造树比较烦吧,得看输入,随便写了一个
import java.util.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;
class Untitled {-google 1point3acres
        public static void main(String[] args) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                if(constructTreeUtil("(x,y), (x,z), (z,w)")) {
                        inorderPrint(root);
                }
        }-google 1point3acres
       
        static class tNode {
                String value;
                List<tNode> children = new ArrayList<>();.鐣欏璁哄潧-涓浜-涓夊垎鍦
                int indegree;-google 1point3acres
                int outdegree;. Waral 鍗氬鏈夋洿澶氭枃绔,
                public tNode(String x) { value = x; }
               
                @Override
                public boolean equals(Object obj) {
                        if(obj == this) return true;
                        if(obj == null || obj.getClass() != this.getClass()) return false;
                        tNode node = (tNode) obj;
                        return node.value == this.value;. Waral 鍗氬鏈夋洿澶氭枃绔,
                }
        }
       
        public static HashMap<String, tNode> tree = new HashMap<String, tNode>();
        public static tNode root;

        public static boolean constructTreeUtil(String s) {. from: 1point3acres.com/bbs
                List<List<String>> list = new ArrayList<>();
                List<String> edges = new ArrayList<String>();
                Pattern regex = Pattern.compile("\\((.*?)\\)");
                Matcher regexMatcher = regex.matcher(s); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                while (regexMatcher.find()) { //Finds Matching Pattern in String
                        edges.add(regexMatcher.group(1)); //Fetching Group from String
                }
                System.out.println(edges);
                for(String edge : edges) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        String[] nodes = edge.split(",");
                        if(!tree.containsKey(nodes[0])) tree.put(nodes[0], new tNode(nodes[0]));
                        if(!tree.containsKey(nodes[1])) tree.put(nodes[1], new tNode(nodes[1]));. From 1point 3acres bbs
                        tNode pNode = tree.get(nodes[0]);
                        tNode cNode = tree.get(nodes[1]);
                        if(pNode.equals(cNode) || cNode.children.contains(pNode) || cNode.indegree >= 2) return false;
                        pNode.children.add(cNode);
                        cNode.indegree += 1;
                        pNode.outdegree += 1;
                }
                int cc = 0; // num of connected components
                for(tNode n : tree.values()) {
                        if(n.indegree == 0) {
                                root = n;
                                cc++;
                        }
                }
                return cc == 1;
        }
       
        public static void inorderPrint(tNode root) {
                if(root == null) return;
                if(root.children.size() > 0) inorderPrint(root.children.get(0)); // get left
                System.out.println(root.value);
                if(root.children.size() > 1) inorderPrint(root.children.get(1)); // get right
        }
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 14:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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