一亩三分地论坛

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

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

Zenefits skype

[复制链接] |试试Instant~ |关注本帖
applepie11 发表于 2015-4-16 04:58:22 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 博士 全职@Zenefits - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
下午刚面的,我居然都没有把题目看完,就只看了前3行的题目,外加一个小图,根本就没注意还有滚动条,居然我也写了好几十行的代码,花了大概半个小时吧,然后面试官居然也没说什么,感觉他说话有气无力的,估计他一天没吃饭。。。。面试前半个小时刚收到amazon的offer,想去amazon了,这个也就那么回事儿了。

题目就一道如下,大家参考下吧

You are given a binary tree as a sequence of parent-child pairs. For example, the tree represented by the node pairs below:
(A,B) (A,C) (B,G) (C,H) (E,F) (B,D) (C,E)
may be illustrated in many ways, with two possible representations below:
     A   /  \  B    C / \  / \G  D  E   H       \            F        A   /  \  B    C / \  / \D  G H   E        /       F
Below is the recursive definition for the S-expression of a tree:

S-exp(node) = ( node->val (S-exp(node->first_child))(S-exp(node->second_child))), if node != NULL
                         = "", node == NULL
   where, first_child->val < second_child->val (lexicographically smaller)


This tree can be represented in a S-expression in multiple ways. The lexicographically smallest way of expressing this is as follows:
(A(B(D)(G))(C(E(F))(H)))
We need to translate the node-pair representation into an S-expression (lexicographically smallest one), and report any errors that do not conform to the definition of a binary tree.
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
The list of errors with their codes is as follows:
.1point3acres缃
Error Code      Type of error. Waral 鍗氬鏈夋洿澶氭枃绔,
E1                 More than 2 children
E2                 Duplicate Edges
E3                 Cycle present
E4                 Multiple roots
E5                 Any other error   

Input Format:
Input must be read from standard input.
Input will consist of on line of parent-child pairs. Each pair consists of two node names separated by a single comma and enclosed in parentheses. A single space separates the pairs.
. Waral 鍗氬鏈夋洿澶氭枃绔,
Output:
The function must write to standard output.
Output the given tree in the S-expression representation described above.
There should be no spaces in the output.

Constraints:
  • There is no specific sequence in which the input (parent,child) pairs are represented.
  • The name space is composed of upper case single letter (A-Z) so the maximum size is 26 nodes.
  • Error cases are to be tagged in the order they appear on the list. For example, if one input pair raises both error cases 1 and 2, the output must be E1.


Sample Input #00
(B,D) (D,E) (A,B) (C,F) (E,G) (A,C)
Sample Output #00
. From 1point 3acres bbs
(A(B(D(E(G))))(C(F)))
Sample Input #01
(A,B) (A,C) (B,D) (D,C)
Sample Output #01
E3
Explanation
Node D is both a child of B and a parent of C, but C and B are both child nodes of A. Since D tries to attach itself as parent to a node already above it in the tree, this forms a cycle.


补充内容 (2015-4-16 05:19):
明天还要epic onsite,发个面筋攒rp. From 1point 3acres bbs
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-4-16 09:04):
咋没人给我个米啥的。。。唉:-(

评分

10

查看全部评分

本帖被以下淘专辑推荐:

lzd1127 发表于 2015-5-1 05:45:21 | 显示全部楼层
  1. public String constructSExpression(String s) {
  2.                 boolean[][] graph = new boolean[26][26];
  3.                 Set<Character> set = new HashSet<Character>();
  4.                 boolean E2 = false;
  5.                 int numOfEdges = 0;
  6.                 for (int i = 1; i < s.length(); i += 6) {
  7.                         int x = s.charAt(i) - 'A';
  8.                         int y = s.charAt(i + 2) - 'A';
  9.                         if (graph[x][y]) {
  10.                                 E2 = true;
  11.                         }
  12.                         graph[x][y] = true;
  13.                         set.add(s.charAt(i));
  14.                         set.add(s.charAt(i + 2));
  15.                         numOfEdges++;
  16.                 }

  17.                 boolean E1 = false;
  18.                 for (int i = 0; i < 26; i++) {
  19.                         int count = 0;
  20.                         for (int j = 0; j < 26; j++) {
  21.                                 if (graph[i][j]) {
  22.                                         count++;. from: 1point3acres.com/bbs
  23.                                 }
  24.                         }
  25.                         if (count > 2) {
  26.                                 return "E1";
  27.                         }
  28.                 }
  29.                 if (E2) return "E2";

  30.                 int numOfRoots = 0;
  31.                 char root = ' ';
  32.                 System.out.println(set);
  33.                 for (Character c : set) {
  34.                         for (int i = 0; i < 26; i++) {. 1point3acres.com/bbs
  35.                                 if (graph[i][c - 'A']) {
  36.                                         break;
  37.                                 }
  38.                                 if (i == 25) {
  39.                                         numOfRoots++;
  40.                                         root = c;
  41.                                         boolean[] visited = new boolean[26];
  42.                                         if (detectCycle(c, graph, visited)) {
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  43.                                                 return "E3";
  44.                                         }
  45.                                 }
  46.                         }. 鍥磋鎴戜滑@1point 3 acres
  47.                 }
  48.                 if (numOfRoots == 0) return "E3";
  49.                 if (numOfRoots > 1) return "E4";

  50.                 return getSexpression(root, graph);. From 1point 3acres bbs

  51.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧

  52.         private boolean detectCycle(char c, boolean[][] graph, boolean[] visited) {.1point3acres缃
  53.                 if (visited[c - 'A']) return true;

  54.                 visited[c - 'A'] = true;
  55.                 for (int i = 0; i < 26; i++) {
  56.                         if (graph[c -'A'][i]) {
  57.                                 if (detectCycle((char)('A' + i), graph, visited)) {. From 1point 3acres bbs
  58.                                         return true;
  59.                                 }
  60.                         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  61.                 }
  62.                 return false;
  63.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  64.         private String getSexpression(char root, boolean[][] graph) {
  65. . 鍥磋鎴戜滑@1point 3 acres
  66.                 String left = "";
  67.                 String right = "";
  68.                 for (int i = 0; i < 26; i++) {
  69.                         if (graph[root - 'A'][i]) {.1point3acres缃
  70.                                 left = getSexpression((char)('A' + i), graph);
  71.                                 for (int j = i + 1; j < 26; j++) {. visit 1point3acres.com for more.
  72.                                         if (graph[root - 'A'][j]) {
  73.                                                 right = getSexpression((char)('A' + j), graph);
  74.                                                 break;
  75.                                         }
  76.                                 }
  77.                                 break;
  78.                         }
  79.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  80. -google 1point3acres
  81. . 1point 3acres 璁哄潧
  82.                 return "(" + root + left + right + ")";

  83.         }
复制代码
面前写一写。。 写得搓死了
. more info on 1point3acres.com
补充内容 (2015-5-1 05:47):
输入是. from: 1point3acres.com/bbs
"(A,B) (A,C) (B,G) (C,H) (E,F) (B,D) (C,E)"
"(B,D) (D,E) (A,B) (C,F) (E,G) (A,C)"
"(A,B) (A,C) (B,D) (D,C)"
回复 支持 1 反对 0

使用道具 举报

melody_qyao 发表于 2015-4-21 11:33:07 | 显示全部楼层
我想既然input是node pairs,判断E3的话可不可以直接就是 number of nodes = number of edges + 1, 如果不符合这个条件就有环。
回复 支持 1 反对 0

使用道具 举报

EchoO 发表于 2015-4-28 10:32:13 | 显示全部楼层
applepie11 发表于 2015-4-28 10:23
只有出度没入度的node

(′・ω・`)
是我犯二了
多谢~
回复 支持 0 反对 1

使用道具 举报

EchoO 发表于 2015-4-28 05:32:17 | 显示全部楼层
melody_qyao 发表于 2015-4-21 11:33
我想既然input是node pairs,判断E3的话可不可以直接就是 number of nodes = number of edges + 1, 如果不 ...

果然很机智,而且可以先排除掉前面有duplicate edge的那个错误再判断就肯定没错了。.1point3acres缃

补充内容 (2015-4-28 07:51):
无视我,有multi roots也不成立。
回复 支持 1 反对 0

使用道具 举报

 楼主| applepie11 发表于 2015-4-16 05:00:12 | 显示全部楼层
哎呀,tree没显示好,反正就是左右parent-child 那么插入,大家自行想象吧
回复 支持 反对

使用道具 举报

liushen 发表于 2015-4-16 05:40:41 | 显示全部楼层
非常感谢楼主面经!楼主有amazon的offer了,也估计不在乎Zenefits了吧。。。哈哈
对了,能问一下楼主是new grads吗?我找人内退了amazon,没人理我,打听说是amazon的new grads都招满了。。。
回复 支持 反对

使用道具 举报

limingli1991 发表于 2015-4-16 06:14:49 | 显示全部楼层
同问为什么Amazon没人鸟我。。。
回复 支持 反对

使用道具 举报

ohohgod 发表于 2015-4-16 07:03:02 | 显示全部楼层
有没有高手来解答。。。
回复 支持 反对

使用道具 举报

 楼主| applepie11 发表于 2015-4-16 09:04:08 | 显示全部楼层
liushen 发表于 2015-4-16 05:40
非常感谢楼主面经!楼主有amazon的offer了,也估计不在乎Zenefits了吧。。。哈哈
对了,能问一下楼主是new ...

是的啊,不过我没有oa什么的,是两轮phone+7轮的onsite,简直累惨了
回复 支持 反对

使用道具 举报

cuiyang36 发表于 2015-4-16 10:31:29 | 显示全部楼层
我觉得这题最蛋疼的是这个:
Error cases are to be tagged in the order they appear on the list. For example, if one input pair raises both error cases 1 and 2, the output must be E1.
.鐣欏璁哄潧-涓浜-涓夊垎鍦如果是返回任意一个错误即可的话就简单一些了。
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-4-16 12:53:16 | 显示全部楼层
这题就是吓唬吓唬人而已。很简单的。
回复 支持 反对

使用道具 举报

tyr034 发表于 2015-4-17 03:20:10 | 显示全部楼层
averillzheng 发表于 2015-4-16 12:53. 鍥磋鎴戜滑@1point 3 acres
这题就是吓唬吓唬人而已。很简单的。

大神指点下
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-4-17 09:17:53 | 显示全部楼层

搞个26 * 26的矩阵就可以把一切问题搞定。
回复 支持 反对

使用道具 举报

vincky 发表于 2015-4-17 09:28:26 | 显示全部楼层
averillzheng 发表于 2015-4-17 09:17
搞个26 * 26的矩阵就可以把一切问题搞定。

额。。能不能详细说说,谢啦
回复 支持 反对

使用道具 举报

faye_roll 发表于 2015-4-17 23:20:59 | 显示全部楼层
他们家Skype是要开视频么
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-4-18 03:51:32 | 显示全部楼层
vincky 发表于 2015-4-17 09:28
额。。能不能详细说说,谢啦
. Waral 鍗氬鏈夋洿澶氭枃绔,
我写了一个,code比较长,就不贴了。用2维array的方法是可行的。
回复 支持 反对

使用道具 举报

ohohgod 发表于 2015-4-18 15:13:43 | 显示全部楼层
averillzheng 发表于 2015-4-18 03:51
我写了一个,code比较长,就不贴了。用2维array的方法是可行的。

好像很麻烦的样子,怎样把二维矩阵转换成二叉树。。。
回复 支持 反对

使用道具 举报

ohohgod 发表于 2015-4-18 15:33:21 | 显示全部楼层
averillzheng 发表于 2015-4-18 03:51
我写了一个,code比较长,就不贴了。用2维array的方法是可行的。

忽略上一条,刚才sb了,这题真不难。
回复 支持 反对

使用道具 举报

lijl900805 发表于 2015-4-19 05:56:13 | 显示全部楼层
averillzheng 发表于 2015-4-17 09:17
搞个26 * 26的矩阵就可以把一切问题搞定。

请问一下如果用邻接矩阵的话,怎么判断E3呢?是判断每个点的入度是否大于一么?望指正..
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-4-19 09:24:21 | 显示全部楼层
lijl900805 发表于 2015-4-19 05:56
请问一下如果用邻接矩阵的话,怎么判断E3呢?是判断每个点的入度是否大于一么?望指正..

E3可以做dfs。 另外几个可做矩阵运算得到。
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-4-19 09:25:19 | 显示全部楼层
lijl900805 发表于 2015-4-19 05:56. Waral 鍗氬鏈夋洿澶氭枃绔,
请问一下如果用邻接矩阵的话,怎么判断E3呢?是判断每个点的入度是否大于一么?望指正..
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
它的例子里有一个有cycle。意思是说把tree看做是无向图有cycle。
回复 支持 反对

使用道具 举报

ohohgod 发表于 2015-4-19 16:09:46 | 显示全部楼层
averillzheng 发表于 2015-4-19 09:24.鏈枃鍘熷垱鑷1point3acres璁哄潧
E3可以做dfs。 另外几个可做矩阵运算得到。

E3在生成树的dfs里加一set就能做。
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-4-20 21:16:44 | 显示全部楼层
ohohgod 发表于 2015-4-19 16:09.鐣欏璁哄潧-涓浜-涓夊垎鍦
E3在生成树的dfs里加一set就能做。

验证E3的时候,根据楼主给的第三个例子看,要把树看做是一个无向图:意思就是从parent可以到child, 从child 也可以走到parent。. from: 1point3acres.com/bbs
。所以说穿了就是一个无向图的dfs方法。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 05:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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