一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4819|回复: 18
收起左侧

LiveRamp OA面经

[复制链接] |试试Instant~ |关注本帖
yawnzh 发表于 2015-7-10 08:19:16 | 显示全部楼层 |阅读模式

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

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

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

x
昨天晚上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来求每个距离上的节点数。. 鍥磋鎴戜滑@1point 3 acres
. visit 1point3acres.com for more.
. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2015-7-9 16:37):
说错了,是90分钟

评分

2

查看全部评分

 楼主| yawnzh 发表于 2015-8-28 09:32:10 | 显示全部楼层
老冯123 发表于 2015-8-27 17:05
.鏈枃鍘熷垱鑷1point3acres璁哄潧楼主说的题意我get到了。
跟进几个小问题。
1. 排序是否可以直接用Arrays.sort()?我看到另一个帖子里面 ...
. From 1point 3acres bbs
这个是hashtable实现的
  1. def max_subsequence(a):
  2.     count={}
  3.     for num in a:.1point3acres缃
  4.         count[num]=count.get(num,0)+1
  5.     max_len=0
  6.     for num in count:. visit 1point3acres.com for more.
  7.         max_len=max(max_len,count[num]+count.get(num+1,0))
  8.     return max_len
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| yawnzh 发表于 2015-8-28 09:51:43 | 显示全部楼层
老冯123 发表于 2015-8-27 17:31
这是我的代码,貌似是解决了。
我的test case : {1,1,1}, {1,1,1,2,3,3,3,3}, {1}, {}

你这样显然不够优化啊,而且不够精简,虽然时间复杂度也是O(N),我用java重新写了一遍:
  1.    public int maxSubsequence(int[] a){
  2.        Arrays.sort(a);.1point3acres缃
  3.        int last=-1;
  4.        int current=0;
  5.        int max_len=0;
  6.        int i=0;
  7.        for(;i<a.length;i++){
  8.            if(i>0&&a[i]!=a[i-1]){
  9.                max_len=Math.max(max_len,last>=0?i-last:i-current);
  10.                last=a[i]-a[i-1]==1?current:-1;
  11.                current=i;
  12.            }
  13.        }
  14.        max_len=Math.max(max_len,last>=0?i-last:i-current);
  15.        return max_len;
  16.    }
复制代码

补充内容 (2015-8-27 17:56):
复杂度是O(NlgN),说错了
回复 支持 1 反对 0

使用道具 举报

 楼主| yawnzh 发表于 2015-8-9 02:53:13 | 显示全部楼层
wangtieguo 发表于 2015-8-8 08:15
请问楼主,能看下你第二题的具体code吗, 谢谢

我重写了下代码,这个图是棵树,没有环路,从下往上做dfs就可以了, 之前那个做法搞复杂了。
  1. class Solution:

  2.     def count_dist(self,T):
  3.         distance=[-1]*len(T)
  4.         count=[0]*(len(T)-1).1point3acres缃
  5.         for i in range(len(T)):
    -google 1point3acres
  6.             if distance[i]<0:
  7.                 self.get_dist(T,distance,i)
  8.         for i in range(len(T)):
  9.             if distance[i]>0:
  10.                 count[distance[i]-1]+=1
  11.         return count


  12.     def get_dist(self,T,distance,i):
  13.         next=T[i]. more info on 1point3acres.com
  14.         if next==i:
  15.             distance[i]=0
  16.             return 0
  17.         elif distance[next]>0:
  18.             distance[i]=distance[next]+1
  19.             return distance[i]
  20.         else:. visit 1point3acres.com for more.
  21.             distance[i]=self.get_dist(T,distance,next)+1
  22.             return distance[i]
复制代码
回复 支持 1 反对 0

使用道具 举报

jasusy 发表于 2015-8-1 04:54:19 | 显示全部楼层
今天也做到了这两题,幸好有这个帖子。再次感谢。另外我发了一个帖子引用了你这里的内容。
回复 支持 反对

使用道具 举报

pengbomuzzy 发表于 2015-8-1 12:32:22 | 显示全部楼层
jasusy 发表于 2015-8-1 04:54
今天也做到了这两题,幸好有这个帖子。再次感谢。另外我发了一个帖子引用了你这里的内容。
. Waral 鍗氬鏈夋洿澶氭枃绔,
我也是,再次来感谢楼主!
回复 支持 反对

使用道具 举报

wangtieguo 发表于 2015-8-9 00:15:24 | 显示全部楼层
请问楼主,能看下你第二题的具体code吗, 谢谢
回复 支持 反对

使用道具 举报

wangtieguo 发表于 2015-8-9 05:11:07 | 显示全部楼层
yawnzh 发表于 2015-8-9 02:53.鐣欏璁哄潧-涓浜-涓夊垎鍦
我重写了下代码,这个图是棵树,没有环路,从下往上做dfs就可以了, 之前那个做法搞复杂了。

非常感谢楼主
回复 支持 反对

使用道具 举报

老冯123 发表于 2015-8-28 07:15:57 | 显示全部楼层
楼主有几个小问题关于第一题的。.1point3acres缃
1. 如果用排序法,排序完之后如何用dp呢?能不能简单说下?
2. 如果用楼主的hashtable方法,我注意到,count[k] + count[k+1] 这里面的k我理解为应该指代的是a数组中出现的哪几个数(不算重复),所以应是,1,2,3,5,7,而不是k从0开始然后取a[k]这种,因为有重复,那就有可能是count[3] + count[3]的效果,那我想问楼主,这5个distinct数怎么去找?简单做法就是再建一个array,然后循环hashtable,把key放进新的array,再count[k] + count[K+1],但觉得这种方法非常傻而且有增加了空间,想问楼主是怎么解决这个问题的?
我马上也要OA,估计就是这两道题,在线等楼主。谢谢
回复 支持 反对

使用道具 举报

 楼主| yawnzh 发表于 2015-8-28 07:46:23 | 显示全部楼层
老冯123 发表于 2015-8-27 15:15
楼主有几个小问题关于第一题的。
1. 如果用排序法,排序完之后如何用dp呢?能不能简单说下?
2. 如果用楼 ...

1.如果排序做,假如排好之后是【1,1,1,2,3,5,5,5,5,6,7】,那么差值不超过1的是【1,1,1,2】,【2,3】,【5,5,5,5,6】和【6,7】,所以最长的是5 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
2.如果用hittable,count【1】=3,count【2】=1,count【3】=1,count【5】=4,count【6】=1,count【7】=1,最长就是count【5】+count【6】=5了
回复 支持 反对

使用道具 举报

 楼主| yawnzh 发表于 2015-8-28 07:50:06 | 显示全部楼层
老冯123 发表于 2015-8-27 15:15
楼主有几个小问题关于第一题的。
1. 如果用排序法,排序完之后如何用dp呢?能不能简单说下?
2. 如果用楼 ...

是不是我没表达清楚这里只需要找最长的subsequence的长度,而不是求所有符合条件的subsequence。
回复 支持 反对

使用道具 举报

老冯123 发表于 2015-8-28 09:05:23 | 显示全部楼层
yawnzh 发表于 2015-8-28 07:46
1.如果排序做,假如排好之后是【1,1,1,2,3,5,5,5,5,6,7】,那么差值不超过1的是【1,1,1,2】 ...

楼主说的题意我get到了。
跟进几个小问题。
1. 排序是否可以直接用Arrays.sort()?我看到另一个帖子里面说用merge sort排序,我在想是否需要这样??另外就是排序完之后,找这个subset是怎么做到的?我下午想的时候,是loop整个array, 然后设置一个start point,开始时为0,然后找到大于start point数2的时候,计算一下从当前到start point多长,然后这里会遇到一个问题就是之后又重复怎么办?我的考虑就是,如果之后是重复的,start point就跳过,直到不重复为止。. From 1point 3acres bbs
所以,【1,1,1,2,3,5】小点的数组,start point 是0, 找到3的时候发现3>1+1,然后计算一下长度是4,先把这个设为最大长度,然后因为有3个1,所以第二个1和第三个1到3也是停止的,也就是说第二个1和第三个1到3的距离肯定没有第一个1到3的距离大,所以start point更新的时候就是找到不跟当前start point一样的,也就是2了,然后从2再loop,我觉得这方法不是很好,但是我又没想到其他的找到这种subset的方法,楼主能不能给点提示?. From 1point 3acres bbs
2. hittable? 是笔误吧?楼主想打的是hashtable吧?我想问的就是在计算count[k] + count[k+1]的时候如何知道这个k呢?hastable存的是{1,3},{2,1},{3,1},{5,4},{6,1},{7,1},如何提取这个hashtable的key来计算count[k]+count[k+1]呢?

补充内容 (2015-8-28 09:08):
说错了,另一个帖子说的是quick sort.
回复 支持 反对

使用道具 举报

 楼主| yawnzh 发表于 2015-8-28 09:26:15 | 显示全部楼层
老冯123 发表于 2015-8-27 17:05
楼主说的题意我get到了。. more info on 1point3acres.com
跟进几个小问题。
1. 排序是否可以直接用Arrays.sort()?我看到另一个帖子里面 ...

我刚刚用python写了一遍,如果你会python的话应该很好理解,last记录比当前值大1的数的起始index,如果没有就设为None(null), current记录当前数字的起始index, 然后碰到跟当前数字不一样的数的时候就计算一下最大长度。
  1. def max_subsequence(a):
  2.     a.sort()
  3.     last=None.1point3acres缃
  4.     current=0
  5.     max_len=0. visit 1point3acres.com for more.
  6.     for i in range(len(a)): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.         if i>0 and a[i]!=a[i-1]:
  8.             max_len=max(max_len,i-(last or current))
  9.             last=current if a[i]-a[i-1]==1 else None
  10.             current=i. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11.     max_len=max(max_len,len(a)-(last or current))
  12.     return max_len
复制代码

补充内容 (2015-8-27 17:26): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
last记录比当前值小1的数的起始index,说错了
回复 支持 反对

使用道具 举报

老冯123 发表于 2015-8-28 09:31:04 | 显示全部楼层
yawnzh 发表于 2015-8-28 07:50. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
是不是我没表达清楚这里只需要找最长的subsequence的长度,而不是求所有符合条件的subsequence ...

这是我的代码,貌似是解决了。
我的test case : {1,1,1}, {1,1,1,2,3,3,3,3}, {1}, {}
  1. Arrays.sort(a);
  2.                 int start = 0;
  3.                 int max = 0;.1point3acres缃
  4.                 int count = 1;
  5.                 //从1开始向前一个查,所以初始长度为1.
  6.                 int i = 1;
  7.                 while(i<a.length){
  8.                         if(a[i] == a[start]){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.                                 count++;
  10.                                 i++;
  11.                         }
  12.                         else{
  13.                                 if(a[i]<= a[start]+1) {-google 1point3acres
  14.                                         count++;
  15.                                         i++;
  16.                                 }
  17.                                 else{
  18.                                         max = Math.max(max,count);
  19.                                         count = 1;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  20.                                         //跳过start与i之间和a[start]相同数值的数
  21.                                         while(a[start] == a[start+1]){
  22.                                                 start++;
  23.                                         }. From 1point 3acres bbs
  24.                                         start ++;
  25.                                         //新的对比点. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  26.                                         i = start +1;. 1point 3acres 璁哄潧
  27.                                 }
  28.                         }-google 1point3acres
  29.                 }. 1point 3acres 璁哄潧
  30.                 //这里为什么不是max?
  31.                 //考虑到如果数组为{1,1,1}的话,else不进行,所以max为0,而count则记录了长度
  32.                 //所以要再次check一下。
  33.                 //而如果{1,1,1,2},count一定是没有max大的,所以不会影响max
  34.                 return Math.max(max,count);
复制代码
回复 支持 反对

使用道具 举报

Laurinda93 发表于 2015-9-18 14:01:13 | 显示全部楼层
yawnzh 发表于 2015-8-28 09:26
我刚刚用python写了一遍,如果你会python的话应该很好理解,last记录比当前值大1的数的起始index,如果没 ...

其实觉得这样可能会更容易理解一些,和lz的思路差不多这里用lastLen记录上一段的长度,因为最大长度只可能由一段或两段长度组成:即,一种是数列中所有数字都相同,所以这里初始状态设为0没有问题;另一种就是复杂的case了
每次当找到变化值之后,计算得到新的最大长度,可能是原有最大长度,或者现有最大长度(上一段lastLen+这一段right-left);之后在分别更新变量
  1.         public static int maxSubsequence(int[] arr) {
  2.                 if (arr == null || arr.length == 0)
  3.                         return 0;
  4.                 Arrays.sort(arr);
  5.                 int left = 0;
  6.                 int lastLen = 0;
  7.                 int maxLen = 0;
  8.                 .鐣欏璁哄潧-涓浜-涓夊垎鍦
  9.                 for (int right = 1; right < arr.length; right++) {
  10.                         if (arr[right] != arr[right - 1]) {
  11.                                 maxLen = Math.max(maxLen, lastLen + right - left);
  12.                                 lastLen = arr[right] - arr[right - 1] == 1 ? right - left : 0;
  13.                                 left = right;
  14.                         }
  15.                 }
  16.                 return maxLen;
  17.         }
复制代码
回复 支持 反对

使用道具 举报

 楼主| yawnzh 发表于 2015-9-19 10:01:34 | 显示全部楼层
Laurinda93 发表于 2015-9-17 22:01
其实觉得这样可能会更容易理解一些,和lz的思路差不多这里用lastLen记录上一段的长度,因为最大长度只可 ...

你这代码有bug, 如果最大长度包含最后一个数,你的结果是问题的。
回复 支持 反对

使用道具 举报

Laurinda93 发表于 2015-9-19 11:03:23 | 显示全部楼层
yawnzh 发表于 2015-9-19 10:01
你这代码有bug, 如果最大长度包含最后一个数,你的结果是问题的。

谢谢是的呢~已经改掉了~~~
回复 支持 反对

使用道具 举报

458870432 发表于 2015-9-24 06:35:31 | 显示全部楼层
如果只有一个元素算是subsequence吗?
回复 支持 反对

使用道具 举报

458870432 发表于 2015-9-24 08:23:26 | 显示全部楼层
public int findMaxSubsequence2(int[] a){
    Arrays.sort(a);. more info on 1point3acres.com
    int cur_index = 0;. more info on 1point3acres.com
    int last_index = -1;
    int max_length = 0;
    for(int i = 1; i < a.length; i++){
      if(a[i] != a[cur_index]){
        last_index = cur_index;
        cur_index = i;
      }
      if(last_index >= 0 && a[cur_index] - a[last_index] == 1){
        max_length = Math.max(max_length, i - last_index + 1);
      }
    }
    return max_length; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  }
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 04:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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