新鲜LiveRamp OA, 不是传统六度空间 six degree

原帖地址:一亩三分地

中午刚做的题,以为还是传统的六度空间呢,正准备表现一下我的文采,一看不是!!看来LiveRamp出新题了.真是难得。
不过幸好 yawnzh 之前发过一个帖子, 题目他/她说的一样。http://www.1point3acres.com/bbs/ … light=liveramp%2BOA
但是有几点需要修正补充!!, yawnzh 的原内容是这样的:
——————————————————————————————————-Start
昨天晚上12点才想起来有个LiveRamp的OA没做,然后做完今天中午HR就约了电面,效率确实快,只可惜这家不怎么招人好像,发个OA攒攒人品吧。
一共两道编程题,150分钟,可以使用的语言很多。
1.一个sequence,里面都是整数,求最长的subsequence的长度,使得这个subsquence的最大值和最小值相差不超过1. 比如[1,3,2,2,5,2,3,7]最长的subsequence是[3,2,2,2,3],所以应该返回5. 其实挺简单的一道题,开始我以为subsequence要求连续,就用dp做,run了一下结果不对,发现subsequence可以是不连续的,这样的话只需要用一个hashtable统计一下各个整数的个数,所以最长的长度应该就是count[k]+count[k+1]的最大值,k是这个sequence里的某一个数,count[k]是它出现的次数。另外一个思路就是排序,这样空间复杂度小点,但是时间复杂度要高一些。
2.一个图,节点表示城市,有M个节点和M-1条边,所以是没有环的,用一个array表示这个图,比如T[x]=y的话那么节点x就和y相连,如果T[x]=x就说明x是首都。现在要分别求出到首都距离为1,2,3…M-1的节点数。
这题我用一个hashmap重新建了一个图,这样方便查找所有相邻的节点,而不用每次查找整个array。然后用bfs来求每个距离上的节点数。
————————————————————————————————————End
补充:
1. 第一题对空间复杂度有要求是O(n), 所以我没敢用hash, 用了排序法还是比较简的。
2. 第二题对时间和空间要求都是O(M), 所以觉得也不能用hash吧, 不过现在想想hash的空间复杂度怎么算,怎么觉得没印象呢~~~
本来不准备发这个帖子的, 因为题目和yawnzh的帖子一样。后来发现提到新题的只有这一个帖子,就连稍微早几天的帖子也是老题,所以发个帖,我也是新题~~~~~

谢谢

ps:
大款们给赏点米