10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 2485|回复: 5
收起左侧

Indeed OA Coding Test #6

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

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

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

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

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

good node的定义是至少满足以下任意一点:
1.它是头节点(node 1)
2.它指向头节点
3.它指向一个good node
.1point3acres缃
题目输入为: N, array
输出为:需要改变的node的数目
. 1point3acres.com/bbs
例如: . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Input: N = 5, array = {1, 2, 3, 4, 5}
Output: 4

因为要改变2, 3, 4, 5。比如都去指向1,或者1<-2<-3<-4<-5, etc.
. 1point3acres.com/bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

评分

4

查看全部评分

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

使用道具 举报

adampig 发表于 2016-2-4 14:44:13 | 显示全部楼层
完全不明白为什么筒子们都要用啥union find
. more info on 1point3acres.com
  1. def findMinChange(arr):
  2.     if len(arr) <= 1:
  3.         return 0. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  4.     i = 1
  5.     goodLookup = {0:True}
  6.     count = 0
  7.     while i < len(arr):. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.         if i not in goodLookup:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  9.             result = recurCheck(i, arr, goodLookup, {}). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  10.             if not result:
  11.                 count += 1
  12.         i += 1
  13.     return count

  14. def recurCheck(i, arr, goodLookup, loopLookup):
  15.     if i in loopLookup:
  16.         return False
  17.     if i in goodLookup:
  18.         return True
  19.     loopLookup[i] = True
  20.     ret = recurCheck(arr[i] - 1, arr, goodLookup, loopLookup)
  21.     goodLookup[i] = True
  22.     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 ...
. visit 1point3acres.com for more.
下标为0 的那个node使用了吗
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-21 00:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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