一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 2651|回复: 5
收起左侧

Indeed OA Coding Test #6

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

2015(10-12月) 码农类 硕士 全职@Indeed - 网上海投 - 在线笔试 |Otherfresh 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之间,所以数组每个元素的值也在这个范围。
. visit 1point3acres.com for more.

good node的定义是至少满足以下任意一点:
1.它是头节点(node 1)
2.它指向头节点
3.它指向一个good node

题目输入为: N, array
输出为:需要改变的node的数目

例如:
Input: N = 5, array = {1, 2, 3, 4, 5}
Output: 4

因为要改变2, 3, 4, 5。比如都去指向1,或者1<-2<-3<-4<-5, etc.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴



评分

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:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.         return 0
  4.     i = 1
  5.     goodLookup = {0:True}. more info on 1point3acres.com
  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
  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 ...

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-1-19 02:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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