一亩三分地论坛

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

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

Walmart 奇葩面试题

[复制链接] |试试Instant~ |关注本帖
micro_long 发表于 2015-12-2 08:40:56 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Walmart Lab - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
楼主上周去 walmart Lab onsite.
6轮面试都是印度哥哥,  结果最后一面出了个 这样的题, 一口老血吐在墙上.

题目是  3-sum 变形.

给一个数组 a, 求出 里面的三个数的组合 满足以下三个条件:

1. a[i] + a[j] + a[k] < target
2. a[i] < a[j] < a[k]
3. i < j < k    (i, j ,k 是数的index). 鍥磋鎴戜滑@1point 3 acres

要求返回所有满足条件的组合.-google 1point3acres
例如 a [-2, 3, 0, 4]    targt:  6   应该返回:    [ [-2, 3, 4] ]
如果是 [-3, 2, 0, -2, 1, 5] target: 6 应该返回 [[-3, 0, 1], [-3, 0, 5], [-3, 2, 5], [-3, 1, 5], [-2, 1, 5]]
.鐣欏璁哄潧-涓浜-涓夊垎鍦
要求时间复杂度是 O(n^2) 的.

楼主试了很多方法都没法用O(n^2)完成, 只给出了 O(n^3)的解法.

最后 面试官给了一个方法, 先排序, 保存二元元祖(a[i], i)
然后先取 中间元素k, 从中间往俩边遍历. 我觉得没法在O(n^2)时间内做出来, 但是因为时间不够了,所以也没法深入的聊.

楼主的其他面都很好, 但是这一轮没做出来, 最后面试官把 a[i] + a[j] + a[k] < target 改成了 a[i] + a[j] + a[k] = target.
楼主写了个 O(n^2)的解法.
. 鍥磋鎴戜滑@1point 3 acres
总之, 楼主觉得这个题目各种扯, 想了好几天都没想出来合理的解法, 有大神给一个详细的解法吗?

评分

1

查看全部评分

本帖被以下淘专辑推荐:

gzwenyue 发表于 2015-12-2 09:32:00 | 显示全部楼层
这道题最多有O(n^3)种返回的值,感觉O(n^2)算不完。。。
回复 支持 反对

使用道具 举报

awakeningcedar 发表于 2015-12-2 09:45:49 | 显示全部楼层
坑你呢吧 返回所有组合的话 组合数都有可能n^3  问组合个数才可能O(n^2)
回复 支持 反对

使用道具 举报

ryb 发表于 2015-12-2 10:23:14 | 显示全部楼层
这不是3sum smaller吗。。leetcode原题。。O(n^2)的解法大概是:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1. 先sort, O(nlgn)
2. int count = 0;
    for i in array{  // 大概的伪代码 没考虑corner case
       int left  = i + 1;
       int right = array.length - 1;
       while (left < right){
            if(array[i] + array[left] + array[right] < target) {
                  count += (right - left);
                  left++;
            }else{
                  right--;
            }
        }
     }
     return sum;
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这样的话等于两个loop 每个最多是n,所以是O(n^2)的解法 :)
回复 支持 反对

使用道具 举报

awakeningcedar 发表于 2015-12-3 08:27:05 | 显示全部楼层
ryb 发表于 2015-12-1 19:23
这不是3sum smaller吗。。leetcode原题。。O(n^2)的解法大概是:
1. 先sort, O(nlgn)
2. int count = 0; ...

. visit 1point3acres.com for more.这是求的count (应该是题目本意)不过楼主说要把所有组合求出来 那O(n^2)就不可能了。。
回复 支持 反对

使用道具 举报

 楼主| micro_long 发表于 2015-12-3 08:30:16 | 显示全部楼层
即使是求个数, 也不一样. 题目多了一个条件:
a[i] < a[j] < a[k]
Leetcode 上只有一个要求  i<j<k
现在问题来了, 如果只求个数,应该O(n^2)也做不到吧.

回复 支持 反对

使用道具 举报

rosalind324 发表于 2015-12-3 08:55:14 | 显示全部楼层
如果是给出组合,直接 if(array + array[left] + array[right] < target) {  count += (right - left); 加个ArrayList.add(array , array[left], array[right] )//伪码 或者直接System.out.print(array + array[left]+ array[right]) 然后外圈System.out.println();分行 还是n^2啊。


补充内容 (2015-12-3 08:56):
能求个数了,肯定能同时拿到结果存起来的哈,新手,bug 请指正哈,谢谢
回复 支持 反对

使用道具 举报

ryb 发表于 2015-12-3 09:14:15 | 显示全部楼层
micro_long 发表于 2015-12-3 08:30
即使是求个数, 也不一样. 题目多了一个条件:
a < a[j] < a[k]. 1point3acres.com/bbs
Leetcode 上只有一个要求  i

这个其实不要紧。。因为第一步花了O(nlogn)的时间sort 所以只要i < j < k, 就可以保证 a < a[j] < a[k] (如果没有duplicate的情况). more info on 1point3acres.com
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2015-12-3 09:14):
a[ i ] ...被自动转义了。。
回复 支持 反对

使用道具 举报

 楼主| micro_long 发表于 2015-12-3 09:16:25 | 显示全部楼层
当然不是啊, 给你的原来的数组不一定是有序的.. 鍥磋鎴戜滑@1point 3 acres
比如说 我给你 [5,3,2,4,6]
你排序以后得到 [2,3,4,5,6] 这个时候使用的是原来的index 比如说, [2,3,4] 就不满足 i<j<k 和 a[i] < a[j] < a[k] 这个条件.
回复 支持 反对

使用道具 举报

ryb 发表于 2015-12-3 09:17:07 | 显示全部楼层
rosalind324 发表于 2015-12-3 08:55.1point3acres缃
如果是给出组合,直接 if(array + array[left] + array[right] < target) {  count += (right - left); 加 ...

我感觉是对的。。
回复 支持 反对

使用道具 举报

ryb 发表于 2015-12-3 09:22:49 | 显示全部楼层
micro_long 发表于 2015-12-3 09:16. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
当然不是啊, 给你的原来的数组不一定是有序的.
比如说 我给你 [5,3,2,4,6]
你排序以后得到 [2,3,4,5,6]  ...
.1point3acres缃
哦哦 不好意思。。刷题刷的固定思维了。。. more info on 1point3acres.com

不过按照面试官的提示感觉 用一个hashmap记录原始数字和index的对应位置,然后在输出(或者加到list)之前比较一下i < k < j这个条件就ok了。。前提是没有dup的情况
回复 支持 反对

使用道具 举报

gzwenyue 发表于 2015-12-3 10:07:54 | 显示全部楼层
只计算个数的话,面试官给的算法应该可以做到O(n^2)。对于排序好的[a[i],i], 遍历每个[a[i],i]作为中间的数值,然后分别找出[a[i],i] 左边的a[[j],j]对,及[a[i],i]右边的[a[k],k]对,使得a[j]<a[i]且j<i,a[k]>a[i]且k>i。这样一共进行了n次遍历,每次遍历都是O(n)时间。假设对于a[i]找到了 a[j1],a[j2]...a[jn1], a[k1],a[k2],...a[kn2],这住数组左边的都满足a[j]<a[i], j<i,右边的满足 a[k]>a[i],k>i, 只需要左右各取一个数再加上a[i]的和小于target,就是一个满足条件的组合。注意这里a[j1],a[j2]...a[jn1], a[k1],a[k2],...a[kn2]的值是排序好的,所以可以利用二指针法进行扫描,扫描一轮的时间也是O(n),所以总共的时间最后是O(n^2)。二指针大概的算法就是对于每一个a[pl],找出a[pr],使得a[i]+a[pl]+a[pr]刚好小于target,pr 多对应的kx中的x就是count要加的值。
回复 支持 反对

使用道具 举报

zq13667243992 发表于 2015-12-3 12:29:55 | 显示全部楼层
举个例子,如果target 很大很大, 然后这个数组是升序的, 那么任取三个数,都会符合条件。 用排列组合公式就知道,满足条件的结果是O(n^3).
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 10:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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