當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3025|回复: 7
收起左侧

Snapchat 电面

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

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

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

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

x
1. 数独VERIFIER
2.判断一个图是不是
   bipartite: https://en.wikipedia.org/wiki/Bipartite_graph

   static class Node {
                public Node() {
                        neighbors = new HashSet<Node>();
                }

                Set<Node> neighbors;
        }
. From 1point 3acres bbs
        static class Graph {
                Set<Node> nodes;

                public Graph() {
                        nodes = new HashSet<Node>();
                }

                public void addEdge(Node a, Node b) {
                        a.neighbors.add(b);
                        b.neighbors.add(a);
                        nodes.add(a);
                        nodes.add(b);
                }

                public boolean isBipartite() {
                     // implement here
                     return false;
                }
        }

        public static void main(String[] args) {
                Node a = new Node();
                Node b = new Node();
                Node c = new Node();

                Graph g = new Graph();

                g.addEdge(a, b);
                g.addEdge(b, c);
                g.addEdge(c, a);

                System.out.println("is bipartite: " + g.isBipartite());
        }

评分

2

查看全部评分

kelvinzhong 发表于 2015-10-5 01:20:48 | 显示全部楼层
求问楼主第二题是怎么做的呢?
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-5 02:44:44 | 显示全部楼层
kelvinzhong 发表于 2015-10-5 01:20
求问楼主第二题是怎么做的呢?

BFS + 染色
回复 支持 反对

使用道具 举报

 楼主| yypturncoat 发表于 2015-10-6 22:49:51 | 显示全部楼层

正解。DFS也可以。
回复 支持 反对

使用道具 举报

kennethinsnow 发表于 2015-11-22 08:53:32 | 显示全部楼层
DFS代码比较简洁
  1.         public boolean isBipartite() {
  2.             // implement here
  3.             int len = nodes.size();. 留学申请论坛-一亩三分地
  4.             if (len < 3) return true;. From 1point 3acres bbs
  5.             Set<Node> first = new HashSet();    // always point to
  6.             Set<Node> second = new HashSet();
  7.             for (Node nd : nodes){. from: 1point3acres
  8.                 if (first.contains(nd) || second.contains(nd)) continue;
  9.                 if (!addToSet(nd, first, second)) return false;.本文原创自1point3acres论坛
  10.             }
    . visit 1point3acres for more.
  11.             return true;-google 1point3acres
  12.         }
  13.         
  14.         boolean addToSet(Node nd, Set<Node> first, Set<Node> second){
  15.             if (second.contains(nd)) return false;
  16.             if (first.contains(nd)) return true;
  17.             first.add(nd);
  18.             for(Node child : nd.neighbors){
  19.                 if (!addToSet(child, second, first)) return false;
  20.             }
  21.             return true;
  22.         }
  23.     }
复制代码
回复 支持 反对

使用道具 举报

he2004365 发表于 2015-11-25 23:40:04 | 显示全部楼层
majiamajia 发表于 2015-10-5 02:44. 牛人云集,一亩三分地
BFS + 染色

楼主,求详细代码啊,怎么染色啊?
回复 支持 反对

使用道具 举报

sevensevens 发表于 2015-12-5 05:16:59 | 显示全部楼层

垅主好腻害!!!!
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-20 20:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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