一亩三分地论坛

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

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

Snapchat 电面

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

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

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

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

x
1. 数独VERIFIER
2.判断一个图是不是. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
   bipartite: https://en.wikipedia.org/wiki/Bipartite_graph

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

                Set<Node> neighbors;
        }

        static class Graph {
                Set<Node> nodes;
. 1point 3acres 璁哄潧
                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 | 显示全部楼层
majiamajia 发表于 2015-10-5 02:44. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
BFS + 染色

正解。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;
  5.             Set<Node> first = new HashSet();    // always point to
  6.             Set<Node> second = new HashSet();
  7.             for (Node nd : nodes){
  8.                 if (first.contains(nd) || second.contains(nd)) continue;
  9.                 if (!addToSet(nd, first, second)) return false;
  10.             }
  11.             return true;
  12.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.         . 鍥磋鎴戜滑@1point 3 acres
  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 | 显示全部楼层
.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主,求详细代码啊,怎么染色啊?
回复 支持 反对

使用道具 举报

sevensevens 发表于 2015-12-5 05:16:59 | 显示全部楼层
majiamajia 发表于 2015-10-5 02:44. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
BFS + 染色

垅主好腻害!!!!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 06:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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