[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

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

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

[复制链接] |试试Instant~ |关注本帖
jasusy 发表于 2015-8-1 04:53:19 | 显示全部楼层 |阅读模式

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

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

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

x
中午刚做的题,以为还是传统的六度空间呢,正准备表现一下我的文采,一看不是!!看来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:
大款们给赏点米

. more info on 1point3acres

评分

4

查看全部评分

夏末微凉 发表于 2015-8-14 09:06:05 | 显示全部楼层
能麻烦楼主再说说第一题嘛。。就是排序后,用的什么方法接着算sequence ,我收到了OA也要做了。。

补充内容 (2015-8-14 09:11):. more info on 1point3acres
我的打算是先quicksort, 然后dp
回复 支持 反对

使用道具 举报

 楼主| jasusy 发表于 2015-8-15 01:13:12 | 显示全部楼层
夏末微凉 发表于 2015-8-13 17:06
能麻烦楼主再说说第一题嘛。。就是排序后,用的什么方法接着算sequence ,我收到了OA也要做了。。 ...
.留学论坛-一亩-三分地
就看a<=pre + 1 是否满足,pre是前一个不和a相等的数。变的时候要更新res,count,和pre什么的
回复 支持 反对

使用道具 举报

zyz0104 发表于 2015-8-16 01:23:15 | 显示全部楼层
想问问楼主第二题的具体实现?
回复 支持 反对

使用道具 举报

 楼主| jasusy 发表于 2015-8-16 04:39:39 | 显示全部楼层
zyz0104 发表于 2015-8-15 09:23
想问问楼主第二题的具体实现?

思路还是BFS, 就是定义一个class 叫Node吧,Node里面有个list存着他分别和那几个城市相连。然后新建array和给的城市array一样长,把里面放的换成Node.先遍历一遍给的array,把新的array里面Node的list都写好。然后根据新的array BFS就好了。就是用array替代了hashmap。思路一样
回复 支持 反对

使用道具 举报

miracle2138 发表于 2017-2-19 05:29:47 | 显示全部楼层
public int[] position(int[] array){
                if(array == null) return null;
                Map<Integer, List<Integer>> map = new HashMap<>();. 牛人云集,一亩三分地
                Queue<Integer> queue = new LinkedList<>();
                for(int i = 0; i < array.length; i++){
                        int des = array[i];
                        if(des == i){
                                queue.add(i);
.1point3acres网                                continue;
                        }
                        if(!map.containsKey(des))
                                map.put(des, new ArrayList<>());
                        map.get(des).add(i);
                }. 留学申请论坛-一亩三分地
                int[] res = new int[array.length - 1];
                int layer = -1;
                while(!queue.isEmpty()){
                        int size = queue.size();.本文原创自1point3acres论坛
                        if(layer != -1)
                                res[layer] = size;. 1point 3acres 论坛
                        for(int i = 0; i < size; i++){
                                int des = queue.poll();
                                List<Integer> list = map.get(des);
                                if(list != null). 一亩-三分-地,独家发布
                                        queue.addAll(list);
                        }
                        layer++;. 一亩-三分-地,独家发布
                }
                return res;
        }
我的城市那道题的实现,map存指向某一个节点的全部节点。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-25 23:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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