谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 4680|回复: 18
收起左侧

16年1月Snapchat电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
Kidsplay 发表于 2016-1-16 08:40:11 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

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

其实不难,注意判断各种错误,而且打印的是中序遍历。注意时间和空间复杂度。注意代码整洁度。


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

评分

参与人数 1大米 +3 收起 理由
hjx447297354 + 3 感谢分享!

查看全部评分


上一篇:Amazon Intern OA
下一篇:[G家]新鲜面经

本帖被以下淘专辑推荐:

我的人缘0
haoxuango 发表于 2016-1-16 09:40:10 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主, 输入是标准输入中读进来吗
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Kidsplay 发表于 2016-1-16 20:29:23 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
haoxuango 发表于 2016-1-15 20:40
楼主, 输入是标准输入中读进来吗

. from: 1point3acres 对的
就是标准输入
回复 支持 反对

使用道具 举报

我的人缘0
lrn0304 发表于 2016-1-17 00:01:09 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
所以楼主是先建树, 判断合法之后再打印的么
回复 支持 反对

使用道具 举报

我的人缘0
gjxwin 发表于 2016-1-17 00:11:33 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
我怎么觉得此题甚难。。。
回复 支持 反对

使用道具 举报

我的人缘0
chm34 发表于 2016-1-17 01:58:51 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
请问如何只根据(x,y)来判断y是x的左子树还是右子树呢
回复 支持 反对

使用道具 举报

我的人缘0
say543 发表于 2016-1-17 14:07:52 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
有问题请教一下LZ 1. undirected or directed? 2. 怎么判断左子树 or 右子树? 3. 多个connected components怎么办 4. snapchar 要自己处理IO 吗? 用google handout 面吗?
回复 支持 反对

使用道具 举报

我的人缘0
alex.chan 发表于 2016-1-18 02:16:00 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主能不能讲讲怎么中序遍历的?谢谢。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Kidsplay 发表于 2016-1-18 05:54:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
haifengc 发表于 2016-1-17 13:16
楼主能不能讲讲怎么中序遍历的?谢谢。
. Waral 博客有更多文章,
肯定得构建图/树啊,构建好了以后直接递归 left child, self, right child就好了
回复 支持 反对

使用道具 举报

我的人缘0
hakusama1024 发表于 2016-1-19 09:58:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
住楼主好运。请问能讲详细点不。输入的边是怎么构建树的。谢啦。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Kidsplay 发表于 2016-1-19 13:34:08 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hakusama1024 发表于 2016-1-18 20:58
住楼主好运。请问能讲详细点不。输入的边是怎么构建树的。谢啦。
. 一亩-三分-地,独家发布
比如(A,B)表示A是B的父节点
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Kidsplay 发表于 2016-1-19 13:36:11 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
say543 发表于 2016-1-17 01:07
有问题请教一下LZ 1. undirected or directed? 2. 怎么判断左子树 or 右子树? 3. 多个connected components ...

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

使用道具 举报

我的人缘0
 楼主| Kidsplay 发表于 2016-1-19 13:37:23 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
chm34 发表于 2016-1-16 12:58. Waral 博客有更多文章,
请问如何只根据(x,y)来判断y是x的左子树还是右子树呢

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

使用道具 举报

我的人缘0
 楼主| Kidsplay 发表于 2016-1-19 13:38:26 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
lrn0304 发表于 2016-1-16 11:01
所以楼主是先建树, 判断合法之后再打印的么

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

使用道具 举报

我的人缘0
hitowings 发表于 2016-2-1 11:01:44 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Kidsplay 发表于 2016-1-19 13:38
是的呀,不过打印的时候发现不合法终止打印也可以,要求比较低。当然如果能牛到不建树直接on the fly打印 ...

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

使用道具 举报

我的人缘0
syftalent 发表于 2016-2-10 03:51:17 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
有没有有思路如何判断有环? 难道要node有一个father属性一路回溯看有没有一样的?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Kidsplay 发表于 2016-2-18 12:37:48 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
syftalent 发表于 2016-2-9 14:51
有没有有思路如何判断有环? 难道要node有一个father属性一路回溯看有没有一样的?

判断有环方法很多的。。

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

使用道具 举报

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

使用道具 举报

我的人缘0
wangmengcathy 发表于 2016-4-15 11:17:04 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这题主要就是处理输入构造树比较烦吧,得看输入,随便写了一个
import java.util.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;
class Untitled {
        public static void main(String[] args) {
                if(constructTreeUtil("(x,y), (x,z), (z,w)")) {. 围观我们@1point 3 acres
                        inorderPrint(root);
                }
        }
       
        static class tNode {
                String value;
                List<tNode> children = new ArrayList<>();
                int indegree;
                int outdegree;. 1point 3acres 论坛
                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;
                }
        }
       
        public static HashMap<String, tNode> tree = new HashMap<String, tNode>();
        public static tNode root;.留学论坛-一亩-三分地

        public static boolean constructTreeUtil(String s) {
                List<List<String>> list = new ArrayList<>();
                List<String> edges = new ArrayList<String>();
. more info on 1point3acres                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) {
                        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]));
                        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);.1point3acres网
                        cNode.indegree += 1;
                        pNode.outdegree += 1;
                }. From 1point 3acres bbs
                int cc = 0; // num of connected components
                for(tNode n : tree.values()) {
                        if(n.indegree == 0) {
                                root = n;
                                cc++;
                        }
                }
                return cc == 1;.1point3acres网
        }. 围观我们@1point 3 acres
       
        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);. more info on 1point3acres
                if(root.children.size() > 1) inorderPrint(root.children.get(1)); // get right. 牛人云集,一亩三分地
        }. From 1point 3acres bbs
}
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-6-25 06:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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