一亩三分地论坛

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

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

online test悲剧,实力太弱给跪。。

[复制链接] |试试Instant~ |关注本帖
狂暴CNM地 发表于 2014-11-21 02:13:42 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@C3 Energy - 网上海投 - 在线笔试 |Other

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

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

x
网上瞎投的一家公司,很快就发了一个programming puzzl. 1个小时3道题,公司比较小完全找不到面经,直接强做,果断悲剧,发上来看看大家有什么看法。

第一题,没见过。感觉是新题吧。. more info on 1point3acres.com

有一堆node,每个node可以指向一个node,包括他自己。
然后定义good node。
1.Node 1 本身是good node
2.指向node 1的node
3.指向good node 的node

给一个输入流,第一行代表了有多少个NODE. 之后每一行代表这个node指向哪个node.
比如
5
1
2
3.鏈枃鍘熷垱鑷1point3acres璁哄潧
4
5

表示一共5个node,node依次指向1,2,3,4,5. 1point 3acres 璁哄潧

让写一个程序从stdin里面parse出每一行,然后返回需要多少次操作让每一个node都成为good node

第二题,distinct substrings of a string
. 鍥磋鎴戜滑@1point 3 acres
LZ知道要用suffix tree. 可是。。 我感觉20分钟真的写不出来啊..
于是就hash set暴力了,果断几个case 超时+out of memory
除了suffix tree还有什么好的方法么?

第三题,leetcode上的买卖stock第一种,一维DP,比较好做
差不多就是这样吧。。感觉一小时来把这三道题全部AC超出了LZ目前的能力, 太弱了。。。不知道大家怎么看。。-google 1point3acres



. visit 1point3acres.com for more.
补充内容 (2014-11-21 02:59):
第一题每次操作可以修改一个node指向的node

评分

1

查看全部评分

Adeath 发表于 2014-11-21 02:24:26 | 显示全部楼层
感觉略难。。而且只有一个小时
回复 支持 反对

使用道具 举报

yishi1215 发表于 2014-11-21 02:50:28 | 显示全部楼层
patpat~一切都会变好的
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-11-21 02:57:18 | 显示全部楼层
第二题这种比较经典的题目,可以网上搜一搜acm题目的模版。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
话说第一题,一次操作可以做什么事,不太明白题意
回复 支持 反对

使用道具 举报

 楼主| 狂暴CNM地 发表于 2014-11-21 03:03:17 | 显示全部楼层
1guangnian 发表于 2014-11-21 02:57
第二题这种比较经典的题目,可以网上搜一搜acm题目的模版。。。
话说第一题,一次操作可以做什么事,不太 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
这个直接复制个suffix tree进来是不是有点假。。 而且也不一定直接能用. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一题每次操作可以修改一个node指向的node
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-11-21 03:04:57 | 显示全部楼层
那第一题就是把bad node都指向1就好了,就是问你多少个bad node, 把指向关系反一下,原来A指向B, 现在变成B指向A,从1开始bfs,不能访问到的就是bad node啦
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-11-21 03:07:12 | 显示全部楼层
狂暴CNM地 发表于 2014-11-21 03:03
这个直接复制个suffix tree进来是不是有点假。。 而且也不一定直接能用
第一题每次操作可以修改一个node ...

是有点,不过能过了这关多混点经验也好。。。
回复 支持 反对

使用道具 举报

 楼主| 狂暴CNM地 发表于 2014-11-21 03:23:36 | 显示全部楼层
1guangnian 发表于 2014-11-21 03:04. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
那第一题就是把bad node都指向1就好了,就是问你多少个bad node, 把指向关系反一下,原来A指向B, 现在变成B ...

这样应该不行 比如一堆bad node 构成一个环, 只需要让其中一个指向1就所有都是goode node了。。
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-11-21 03:32:40 | 显示全部楼层
狂暴CNM地 发表于 2014-11-21 03:23
这样应该不行 比如一堆bad node 构成一个环, 只需要让其中一个指向1就所有都是goode node了。。

对哦,那就还要缩点啦。。。lol,真是残忍啊这个online test
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-11-21 03:33:44 | 显示全部楼层
狂暴CNM地 发表于 2014-11-21 03:23
这样应该不行 比如一堆bad node 构成一个环, 只需要让其中一个指向1就所有都是goode node了。。

对哦,那就还要缩点啦。。。lol,真是残忍啊这个online test
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-11-21 03:41:46 | 显示全部楼层

第一题楼主举得例子:
5
1
2
3
4
5. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这个是node 1-5都指向他们自己吗?
回复 支持 反对

使用道具 举报

 楼主| 狂暴CNM地 发表于 2014-11-21 03:57:37 | 显示全部楼层
圆梦梦剧场 发表于 2014-11-21 03:41
第一题楼主举得例子:
5
1

恩 比如
5
1
1
1
1
1
就表示所有都指向1
回复 支持 反对

使用道具 举报

Protoss_Dragon 发表于 2014-11-21 04:11:13 | 显示全部楼层
1guangnian 发表于 2014-11-21 03:33
对哦,那就还要缩点啦。。。lol,真是残忍啊这个online test
.鏈枃鍘熷垱鑷1point3acres璁哄潧
不需要吧,每个node只有一个指针,所以每个分块最多只有一个环,也只需要一次操作。第二题确实变态。。一小时写出来的只能是搞ACM的吧。。。
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-11-21 04:11:21 | 显示全部楼层
第一题是求最少改变几个吗?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
能否增加 指向关系?
回复 支持 反对

使用道具 举报

 楼主| 狂暴CNM地 发表于 2014-11-21 04:19:27 | 显示全部楼层
qiaokan 发表于 2014-11-21 04:11
第一题是求最少改变几个吗?
能否增加 指向关系?

只能改变。 比如 2 之前指向 3 可以改成指向1 但1个NODE只能指向最多一个NODE
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-11-21 04:21:52 | 显示全部楼层
狂暴CNM地 发表于 2014-11-21 04:19
只能改变。 比如 2 之前指向 3 可以改成指向1 但1个NODE只能指向最多一个NODE

那是求最小的次数吗?
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-11-21 04:27:15 | 显示全部楼层
第二题suffix array的话,代码会简单很多。不过依然 不是面试题难度。感觉这种难度,前两题在acm 的regional都不是水题。
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-11-21 04:29:01 | 显示全部楼层
第一题
对于一个node,如果她不是good node,那么他肯定在一个不包含node 1的环中,或者指向一个 处于这种不包含node 1的环 中的任意一个node
先找有几个环, 对于每一个环只要把环中任意一个node的指向改为指到node 1
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-11-21 04:38:03 | 显示全部楼层
Protoss_Dragon 发表于 2014-11-21 04:11
不需要吧,每个node只有一个指针,所以每个分块最多只有一个环,也只需要一次操作。第二题确实变态。。一 ...

对啊,观察的仔细!
回复 支持 反对

使用道具 举报

 楼主| 狂暴CNM地 发表于 2014-11-21 04:44:39 | 显示全部楼层
圆梦梦剧场 发表于 2014-11-21 04:29
第一题.鏈枃鍘熷垱鑷1point3acres璁哄潧
对于一个node,如果她不是good node,那么他肯定在一个不包含node 1的环中,或者指向一个 处于这种 ...

恩 差不多 吧 就是找有多少个没有连到1的 connected component。 就是一个小时要做三题,要很快的implement出来还没有bug还是比较困难。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 12:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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