聊聊在私立文理读cs的两年感受

一亩三分地论坛

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

Indeed OA Coding Test #6

[复制链接] |试试Instant~ |关注本帖
huangbow 发表于 2015-11-11 13:17:38 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类General 硕士 全职@Indeed - 网上海投 - 在线笔试  | Other | fresh grad应届毕业生

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

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

x
做的是OA Coding Test #6。
题目是球把一个node list中的全部node变成good node需要改变的node数目。说是list,其实就是一个array,每个位置就代表一个node,比如array[i]就表示第i个node。array[i]的值就表示它指向的node。node的数目在1到N之间,所以数组每个元素的值也在这个范围。.本文原创自1point3acres论坛
.1point3acres网

good node的定义是至少满足以下任意一点:
1.它是头节点(node 1)
2.它指向头节点
3.它指向一个good node. Waral 博客有更多文章,
. from: 1point3acres
题目输入为: N, array. 留学申请论坛-一亩三分地
输出为:需要改变的node的数目

例如:
Input: N = 5, array = {1, 2, 3, 4, 5}
Output: 4. 1point3acres
. 牛人云集,一亩三分地
因为要改变2, 3, 4, 5。比如都去指向1,或者1<-2<-3<-4<-5, etc.-google 1point3acres

. 一亩-三分-地,独家发布


评分

4

查看全部评分

zsz1990ustc 发表于 2016-2-24 02:01:21 | 显示全部楼层
haoxuango 发表于 2016-2-20 08:37
下标为0 的那个node使用了吗

用了啊,就是为0的那个不算进count。最后find parent不为0的那些是需要调节的。
回复 支持 0 反对 1

使用道具 举报

TR07 发表于 2015-12-4 12:39:47 | 显示全部楼层
多谢楼主,刚考到这题了。参考了网上union find的解法,顺利解决了。求过啊
回复 支持 反对

使用道具 举报

adampig 发表于 2016-2-4 14:44:13 | 显示全部楼层
完全不明白为什么筒子们都要用啥union find

  1. def findMinChange(arr):
  2.     if len(arr) <= 1:
    . 1point3acres
  3.         return 0
  4.     i = 1
  5.     goodLookup = {0:True}
  6.     count = 0
  7.     while i < len(arr):
  8.         if i not in goodLookup:
  9.             result = recurCheck(i, arr, goodLookup, {})
  10.             if not result:
  11.                 count += 1. Waral 博客有更多文章,
  12.         i += 1
  13.     return count
    . 留学申请论坛-一亩三分地
  14. .留学论坛-一亩-三分地
  15. def recurCheck(i, arr, goodLookup, loopLookup):
  16.     if i in loopLookup:
  17.         return False
  18.     if i in goodLookup:
  19.         return True-google 1point3acres
  20.     loopLookup[i] = True.本文原创自1point3acres论坛
  21.     ret = recurCheck(arr[i] - 1, arr, goodLookup, loopLookup)
  22.     goodLookup[i] = True
  23.     return ret
复制代码
回复 支持 反对

使用道具 举报

zsz1990ustc 发表于 2016-2-16 13:03:22 | 显示全部楼层
还是觉得 union find 更直观更容易想些。转载一个解法,感觉很有启发:http://yuanhsh.iteye.com/blog/2200515
回复 支持 反对

使用道具 举报

haoxuango 发表于 2016-2-20 08:37:52 | 显示全部楼层
zsz1990ustc 发表于 2016-2-16 13:03
还是觉得 union find 更直观更容易想些。转载一个解法,感觉很有启发:http://yuanhsh.iteye.com/blog/2200 ...

下标为0 的那个node使用了吗
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-21 19:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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