近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 11124|回复: 46
收起左侧

Zenefits skype

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

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

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

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

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)))
. 1point 3acres 璁哄潧
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.
. from: 1point3acres.com/bbs
The list of errors with their codes is as follows:

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Error Code      Type of error
E1                 More than 2 children-google 1point3acres
E2                 Duplicate Edges
E3                 Cycle present
E4                 Multiple roots. visit 1point3acres.com for more.
E5                 Any other error   

Input Format:. 1point3acres.com/bbs
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.

Output:.鏈枃鍘熷垱鑷1point3acres璁哄潧
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

(A(B(D(E(G))))(C(F))).鏈枃鍘熷垱鑷1point3acres璁哄潧
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
补充内容 (2015-4-16 09:04):
咋没人给我个米啥的。。。唉:-(

评分

10

查看全部评分

本帖被以下淘专辑推荐:

lzd1127 发表于 2015-5-1 05:45:21 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
  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;-google 1point3acres
  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]) {. 鍥磋鎴戜滑@1point 3 acres
  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;.1point3acres缃
  20.                         for (int j = 0; j < 26; j++) {
  21.                                 if (graph[i][j]) {
  22.                                         count++;
  23.                                 }
  24.                         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  25.                         if (count > 2) {
  26.                                 return "E1";
  27.                         }. visit 1point3acres.com for more.
  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++) {
  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.                         }
  47.                 }. 鍥磋鎴戜滑@1point 3 acres
  48.                 if (numOfRoots == 0) return "E3";
  49.                 if (numOfRoots > 1) return "E4";

  50. . Waral 鍗氬鏈夋洿澶氭枃绔,
  51.                 return getSexpression(root, graph);

  52.         }
  53. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  54.         private boolean detectCycle(char c, boolean[][] graph, boolean[] visited) {
  55.                 if (visited[c - 'A']) return true;

  56.                 visited[c - 'A'] = true;
  57.                 for (int i = 0; i < 26; i++) {
  58.                         if (graph[c -'A'][i]) {
  59.                                 if (detectCycle((char)('A' + i), graph, visited)) {. 1point 3acres 璁哄潧
  60.                                         return true;
  61.                                 }
  62.                         }
  63.                 }. From 1point 3acres bbs
  64.                 return false;
  65.         }

  66.         private String getSexpression(char root, boolean[][] graph) {. From 1point 3acres bbs

  67. -google 1point3acres
  68.                 String left = "";
  69.                 String right = "";
  70.                 for (int i = 0; i < 26; i++) {
  71.                         if (graph[root - 'A'][i]) {. 鍥磋鎴戜滑@1point 3 acres
  72.                                 left = getSexpression((char)('A' + i), graph);
  73.                                 for (int j = i + 1; j < 26; j++) {
  74.                                         if (graph[root - 'A'][j]) {
  75.                                                 right = getSexpression((char)('A' + j), graph);
  76.                                                 break;
  77.                                         }
  78.                                 }
  79.                                 break;
  80.                         }. 1point3acres.com/bbs
  81.                 }
  82. . 1point3acres.com/bbs

  83.                 return "(" + root + left + right + ")";

  84. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  85.         }
复制代码
面前写一写。。 写得搓死了
. 1point3acres.com/bbs
补充内容 (2015-5-1 05:47):
输入是. Waral 鍗氬鏈夋洿澶氭枃绔,
"(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 | 显示全部楼层
关注一亩三分地微博:
Warald
我想既然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. From 1point 3acres bbs
我想既然input是node pairs,判断E3的话可不可以直接就是 number of nodes = number of edges + 1, 如果不 ...

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

补充内容 (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.
如果是返回任意一个错误即可的话就简单一些了。. 1point 3acres 璁哄潧
回复 支持 反对

使用道具 举报

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

使用道具 举报

tyr034 发表于 2015-4-17 03:20:10 | 显示全部楼层
averillzheng 发表于 2015-4-16 12:53. more info on 1point3acres.com
这题就是吓唬吓唬人而已。很简单的。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
大神指点下
回复 支持 反对

使用道具 举报

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
额。。能不能详细说说,谢啦
.1point3acres缃
我写了一个,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
请问一下如果用邻接矩阵的话,怎么判断E3呢?是判断每个点的入度是否大于一么?望指正..

它的例子里有一个有cycle。意思是说把tree看做是无向图有cycle。
回复 支持 反对

使用道具 举报

ohohgod 发表于 2015-4-19 16:09:46 | 显示全部楼层
averillzheng 发表于 2015-4-19 09:24
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。
。所以说穿了就是一个无向图的dfs方法。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-29 08:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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