一亩三分地论坛

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

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

热腾腾的LiveRamp电面面经,被问了一道新题

[复制链接] |试试Instant~ |关注本帖
ZionHill 发表于 2015-10-8 06:30:05 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 实习@LiveRamp - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x

LZ第一次面试,是跟Tenzing小哥,上来先问几个Behaviour Question,介绍下自己和like which project most blabla。LZ有点紧张,说的也是磕磕巴巴的,大约5分钟后开始问技术题. From 1point 3acres bbs
两道技术题:第一道题介于word laddar 1和2之间,给你两个正整数X和T,X可以有两种操作:X ^ 2和X-1,问你从X出发怎么经过最少的变换到T,返回任一种path(word laddar 2要求返回所有的path,1则是要求返回最短路径的长度)。我答得是用BFS的同时记录每个得到的数的前一个点,当找到T的时候可以反向reconstruct整条路径。小哥估计看出来我做过这道题,什么follow up都没问就直接move on下一题了. 1point3acres.com/bbs

. visit 1point3acres.com for more.
第二道题没在面经里见到过:给一堆coins,每个coin有一个distinct positive value,让你从中找不重复的两组数,这两组数的和相等(两组数的长度可能不相等),如果找不到这样的两组数的话也要返回适当的值。follow up是如果你有1T个数怎么办。LZ卡在这道题很久,只说出来一个Brute Force的解法,后面死活也想不出更好的解法了,小哥也没给什么提示。(大家有什么更好的方法也可以分享一下,我个人始终没解决的一个难点是两组数都不是定长的,可能一组数特别多另一组数特别少) 最后时间快到了,小哥让随便问了几个问题就结束了。整个面试只有20多分钟
.鐣欏璁哄潧-涓浜-涓夊垎鍦
暂时还没出结果,不过100%是跪了,刷题还是刷的不牢固啊。希望后面的面试好运吧



补充内容 (2015-10-8 06:32):
对了,Tenzing说现在公司一共有100多人,其中技术员工有45人。我之前看过LiveRamp中国员工的Linkedin,各种清北浙交本科CMU硕士,感觉这家的bar还是挺高的
hanchen999 发表于 2015-10-8 06:51:44 | 显示全部楼层
求问总共面了多长时间,我下周也要面他家一个叫Roshan George的

补充内容 (2015-10-8 06:53):
20多分钟能把第一题做出来已经很强了
回复 支持 反对

使用道具 举报

 楼主| ZionHill 发表于 2015-10-8 06:53:37 | 显示全部楼层
hanchen999 发表于 2015-10-8 06:51. Waral 鍗氬鏈夋洿澶氭枃绔,
求问总共面了多长时间,我下周也要面他家一个叫Roshan George的

20多分钟,主要是我第二题答得特别不好,感觉面试官也想早点结束
回复 支持 反对

使用道具 举报

nemoleoliu 发表于 2015-10-8 07:41:03 | 显示全部楼层
第二题就是01背包吧 先计算总和的一半 然后就是01背包 使得最接近总和的一半
回复 支持 反对

使用道具 举报

 楼主| ZionHill 发表于 2015-10-8 08:41:09 | 显示全部楼层
nemoleoliu 发表于 2015-10-8 07:41
第二题就是01背包吧 先计算总和的一半 然后就是01背包 使得最接近总和的一半

可是数组里面的数也有可能不会被用到,比如如果一共N个数,其中有两个数特别大,而剩下的N-2个数的和正好等于其中一个大数,这种情况该怎么办呢?
回复 支持 反对

使用道具 举报

 楼主| ZionHill 发表于 2015-10-8 08:43:13 | 显示全部楼层
hanchen999 发表于 2015-10-8 06:51
求问总共面了多长时间,我下周也要面他家一个叫Roshan George的
. from: 1point3acres.com/bbs
补充内容 (2015-10-8 06:53):

不需要写代码,口述思路即可。我第一题只说了2、3分钟,说完就move on了...
回复 支持 反对

使用道具 举报

nemoleoliu 发表于 2015-10-8 09:08:56 | 显示全部楼层
ZionHill 发表于 2015-10-8 08:41
可是数组里面的数也有可能不会被用到,比如如果一共N个数,其中有两个数特别大,而剩下的N-2个数的和正 ...

哦 就是说有可能1k个数 最后只用到2个数对吧
回复 支持 反对

使用道具 举报

 楼主| ZionHill 发表于 2015-10-8 09:24:06 | 显示全部楼层
nemoleoliu 发表于 2015-10-8 09:08
哦 就是说有可能1k个数 最后只用到2个数对吧

嗯,不过两个数是不可能的,至少三个数,因为每个数都是unique的
回复 支持 反对

使用道具 举报

maplain 发表于 2015-10-22 07:49:16 | 显示全部楼层
这题真的不是NP-Complete么== 为什么还要1T数据。。1T个不同的数。。

http://stackoverflow.com/questions/19499544/subsets-with-equal-sum
回复 支持 反对

使用道具 举报

 楼主| ZionHill 发表于 2015-10-22 08:53:06 | 显示全部楼层
maplain 发表于 2015-10-22 07:49
这题真的不是NP-Complete么== 为什么还要1T数据。。1T个不同的数。。

http://stackoverflow.com/quest ...

我面试完想这道题想了很久,我也觉得是NP-Complete的,至少到现在为止我都想不出来有什么方法可以在多项式时间解决这题。。
回复 支持 反对

使用道具 举报

chm34 发表于 2015-10-23 05:08:05 | 显示全部楼层
参考了stackoverflow才发现用subset的思想还是比较好做的,但是真的好难想到。。可以在O(3^N)时间解出来:
public static boolean solve(ArrayList<Integer> set,int level,int sum1,int sum2)
        {
                if(sum1!=0 && sum1==sum2) return true;
                if(level==set.size()) return false;
                return solve(set,level+1,sum1+set.get(level),sum2) || solve(set,level+1,sum1,sum2+set.get(level))
                                || solve(set,level+1,sum1,sum2);
        }

补充内容 (2015-10-23 05:10):
没仔细看楼主的问题。。我写的这个只是返回是否有解,要返回具体的结果还要用两个list来存结果才行。。
回复 支持 反对

使用道具 举报

 楼主| ZionHill 发表于 2015-10-23 05:26:12 | 显示全部楼层
chm34 发表于 2015-10-23 05:08
参考了stackoverflow才发现用subset的思想还是比较好做的,但是真的好难想到。。可以在O(3^N)时间解出来:. Waral 鍗氬鏈夋洿澶氭枃绔,
...

恩,应该是subset的变种,时间是指数级的,但是我就不懂面试官问我“如果有1T个数怎么办”是闹哪样。。
回复 支持 反对

使用道具 举报

xuchen1m3fd 发表于 2015-10-27 03:04:36 | 显示全部楼层
楼主,我第二题有个思路是这样的:
假设我们完成了 List<Integer> findSum(List<Integer> nums, int target)这样的方法,先调用list = findSum(nums, 2K) 假设K是目标,然后再调用firstPart = findSum(list, K).鏈枃鍘熷垱鑷1point3acres璁哄潧
这样怎么样?
回复 支持 反对

使用道具 举报

 楼主| ZionHill 发表于 2015-10-27 04:30:51 | 显示全部楼层
xuchen1m3fd 发表于 2015-10-27 03:04. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
楼主,我第二题有个思路是这样的:
假设我们完成了 List findSum(List nums, int target)这样的方法,先调 ...

可行,不过你要怎么确定K的值呢?
回复 支持 反对

使用道具 举报

returning 发表于 2015-10-27 10:01:38 | 显示全部楼层
第二题似曾相似,google partition problem即可。. Waral 鍗氬鏈夋洿澶氭枃绔,
按照这个思路,一旦找到某个DP[N][k]为true,表示可以从1到k,其中某个subset的和为N,这样我们就得到了所有可能的N,然后就是找是否存在一个N/2和N,都是可以从某个subset构成。只要N/2和N都存在,那么问题就解决了。

先mark一下,看看有无更好的办法。. From 1point 3acres bbs

补充内容 (2015-10-27 10:04):
当然本题不用走完所有的N,一旦找到某个N和N/2可以由两个不同的集合的子集构成,那么问题就结束了。
回复 支持 反对

使用道具 举报

 楼主| ZionHill 发表于 2015-10-27 13:32:02 | 显示全部楼层
returning 发表于 2015-10-27 10:01
第二题似曾相似,google partition problem即可。
按照这个思路,一旦找到某个DP[N][k]为true,表示可以从 ...

没太明白你的解法。。原来的数组里的数不一定都会被用到. 鍥磋鎴戜滑@1point 3 acres
比如[1,19,33,12,999,4,31,200],返回[19,12]和[31],这种情况该怎么办呢?
回复 支持 反对

使用道具 举报

returning 发表于 2015-10-27 13:48:28 | 显示全部楼层
ZionHill 发表于 2015-10-27 13:32
没太明白你的解法。。原来的数组里的数不一定都会被用到
比如[1,19,33,12,999,4,31,200],返回 ...

那个解法有误,问题不一样,找到了和为N的subset,找到了和为2*N的subset,他们不一定是彼此覆盖关系。
这个题依然不明白。sorry
回复 支持 反对

使用道具 举报

 楼主| ZionHill 发表于 2015-10-27 13:52:06 | 显示全部楼层
returning 发表于 2015-10-27 13:48
那个解法有误,问题不一样,找到了和为N的subset,找到了和为2*N的subset,他们不一定是彼此覆盖关系。.鏈枃鍘熷垱鑷1point3acres璁哄潧
...
.1point3acres缃
好的,9楼的同学分享的stackoverflow上的解法应该是正确的,复杂度O(3^n)
回复 支持 反对

使用道具 举报

jigsaw_Becky 发表于 2016-11-27 12:37:48 | 显示全部楼层
请问第二题“follow up是如果你有1T个数怎么办”。这个怎么回答最后lz知道了吗?求告知!谢谢!
回复 支持 反对

使用道具 举报

lausteven 发表于 前天 12:27 | 显示全部楼层
int tot = 0, a[55], can[500005];

can[0] = 1;
for (int i = 0; i < n; i++) {
    for (int j = tot; j >= 0; j--) {
        if (can[j]) {
           if(can[j + a])
               return true;
           else. From 1point 3acres bbs
              can[j+a] = 1;
        }
    }.1point3acres缃
    tot += a;
}

这个应该是polynomial!

补充内容 (2016-12-8 12:28):
修改下:a[n], can[k]. n是input size,k是maximum sum of n unique positive integer
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 04:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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