May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3286|回复: 24
收起左侧

Google新鲜面经

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

2015(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚面完,来发个面经求rp求大米~

Given an array of N=10^6 int32 and an int32 X, compute the exact number of triples (a, b, c) of distinct elements of the array so that a + b + c <= X
其实就是和3Sum差不多,不过写完被他问了可能的overflow问题,然后立马改了下就结束了

求大米求大米求大米~~┏ (゜ω゜)=☞ 重要的事情说三遍~~
. visit 1point3acres.com for more.

评分

7

查看全部评分

本帖被以下淘专辑推荐:

discoveryi 发表于 2015-8-12 07:09:46 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
    // O(n^2) solution
    public static int findNumberOfTriangles(int[] a) {. visit 1point3acres.com for more.
        int n = a.length;
        Arrays.sort(a);
        int count = 0;
        for (int i = 0; i < n - 2; i++) {
            int k = i + 2;
            for (int j = i + 1; j < n; j++) {
                while (k < n && a + a[j] > a[k]) {
                    System.out.println("a:" + a + "  ,b:" + a[j] + "  ,c:" + a[k]);
                    k++;
                }
                count += k - j - 1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
            }
        }
        return count;
    }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

    // O(n^3) solution
    public static int findNumberOfTriangles2(int[] a) {
        int n = a.length;
        Arrays.sort(a);.鏈枃鍘熷垱鑷1point3acres璁哄潧
        int count = 0;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (a + a[j] > a[k]) {
                        count++;
                    }
                }
            }. From 1point 3acres bbs
        }
        return count;
    }

补充内容 (2015-8-12 07:10):
原题是:. 1point3acres.com/bbs

/**
. 1point 3acres 璁哄潧 * Given an unsorted array of positive integers. Find the number of triangles that can be formed with three different array elements as three sides of triangles. For a triangle to be ...
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-8-12 12:30:45 | 显示全部楼层
关注一亩三分地微博:
Warald
LZ这不是就是3sum的变种嘛,我感觉这个10^6大小的数组的限制无意义啊,这时可以fit进memory的啊,这就是一个简单的3sum吧。请问lz,那个overflow是什么情况?是return的val int可能存不下吧。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-8-12 13:04:21 | 显示全部楼层
f1371342385 发表于 2015-8-12 12:30
LZ这不是就是3sum的变种嘛,我感觉这个10^6大小的数组的限制无意义啊,这时可以fit进memory的啊,这就是一 ...

假设X很大,比如是2^31,而数组中的数字是1,2,3...10^6,那么数组中的每一个triplet都满足条件,最后数出来的个数会是C(3, 10^6) ~= 2^58。这在C++中就必须上long long了。但是如果数组再稍微大一点,比如到10^7的话,long long就可能hold不住了;所谓的overflow应该就是指这个。所以这个限制非常关键,如果是面试官一开始主动提出来这个限制的话,我觉得算是比较良心的。
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-8-12 13:09:22 | 显示全部楼层
stellari 发表于 2015-8-12 13:04
假设X很大,比如是2^31,而数组中的数字是1,2,3...10^6,那么数组中的每一个triplet都满足条件,最后数出 ...

对,这就是我考虑为什么面试官提醒这个的问题啦
回复 支持 反对

使用道具 举报

monkerek 发表于 2015-8-12 13:10:10 | 显示全部楼层
stellari 发表于 2015-8-12 13:04
假设X很大,比如是2^31,而数组中的数字是1,2,3...10^6,那么数组中的每一个triplet都满足条件,最后数出 ...

这种情况下应该不是C(3, 10^6)吧。。。i.e. (1,2,3) (2,3,4)的sum就不一样

我想面试官指的是三个int32的sum有可能会超过int32吧
回复 支持 反对

使用道具 举报

stellari 发表于 2015-8-12 13:24:15 | 显示全部楼层
monkerek 发表于 2015-8-12 13:10
这种情况下应该不是C(3, 10^6)吧。。。i.e. (1,2,3) (2,3,4)的sum就不一样

我想面试官指的是三个int32 ...

为什么不是呢?你举的这两者的sum是不一样,但是不都小于X == 2^31么?所以都是满足条件的。注意原题是<=,而不是==。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
当然,三个int32的和会超过int32这也是一个重要的overflow的点。多谢指出。这两个overflow的点都可以通过使用long long进行规避。
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-12 15:19:32 | 显示全部楼层
stellari 发表于 2015-8-12 13:04
假设X很大,比如是2^31,而数组中的数字是1,2,3...10^6,那么数组中的每一个triplet都满足条件,最后数出 ...

一句话,这个坑太隐蔽。。。。。
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-8-13 08:51:44 | 显示全部楼层
stellari 发表于 2015-8-12 13:24
为什么不是呢?你举的这两者的sum是不一样,但是不都小于X == 2^31么?所以都是满足条件的。注意原题是
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果说存在了overflow我们应该如何处理呢?用string来存储最后的结果?
回复 支持 反对

使用道具 举报

monkerek 发表于 2015-8-13 09:53:41 | 显示全部楼层
stellari 发表于 2015-8-12 13:24
为什么不是呢?你举的这两者的sum是不一样,但是不都小于X == 2^31么?所以都是满足条件的。注意原题是
. 鍥磋鎴戜滑@1point 3 acres
I see. 没有注意到题目是<=。 多谢指出!
回复 支持 反对

使用道具 举报

monkerek 发表于 2015-8-13 09:54:30 | 显示全部楼层
UmassJin 发表于 2015-8-13 08:51
如果说存在了overflow我们应该如何处理呢?用string来存储最后的结果?
. 1point 3acres 璁哄潧
用64位intteger来存就行了
回复 支持 反对

使用道具 举报

stellari 发表于 2015-8-13 11:31:14 | 显示全部楼层
UmassJin 发表于 2015-8-13 08:51
如果说存在了overflow我们应该如何处理呢?用string来存储最后的结果?
. more info on 1point3acres.com
如果限定数组小于等于10^6次,用64位整型就一定可以表示结果;但是如果数组较大,恐怕就要考虑1)用string表示,2)用一个数组表示,3)抛出异常,根据实际情况选择方案。这些方案都可以跟面试官提。
回复 支持 反对

使用道具 举报

Williamslg 发表于 2015-8-15 09:20:38 | 显示全部楼层
请问这里需要考虑重复嘛?能否给个例子-google 1point3acres

补充内容 (2015-8-15 10:31):
比如 1112225556, x=10.  (1, 1, 1) 这种算嘛?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-8-27 15:50:06 | 显示全部楼层
楼主这题复杂度是多少?感觉虽然可以先排个序,但是这种不等于的关系似乎只能是 O(n^3)?
回复 支持 反对

使用道具 举报

 楼主| flamen 发表于 2015-8-27 16:03:18 | 显示全部楼层
hj867955629 发表于 2015-8-26 23:50. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主这题复杂度是多少?感觉虽然可以先排个序,但是这种不等于的关系似乎只能是 O(n^3)?

O(n^2)哦 突然发现leetcode最近补上这道题了 难道是在我发完面经以后 lol
https://leetcode.com/problems/3sum-smaller/
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-8-28 00:53:50 | 显示全部楼层
flamen 发表于 2015-8-27 16:03.鏈枃鍘熷垱鑷1point3acres璁哄潧
O(n^2)哦 突然发现leetcode最近补上这道题了 难道是在我发完面经以后 lol
https://leetcode.com/problem ...

能贴下代码或者伪码嘛?还是没想通。如果一个数组所有组合都行,那不就是n^3了吗?
回复 支持 反对

使用道具 举报

 楼主| flamen 发表于 2015-8-28 09:31:33 | 显示全部楼层
hj867955629 发表于 2015-8-27 08:53
能贴下代码或者伪码嘛?还是没想通。如果一个数组所有组合都行,那不就是n^3了吗?
  1.     public int threeSumSmaller(int[] nums, int target) {
  2.         if (nums.length < 3) {. 1point3acres.com/bbs
  3.             return 0;
  4.         }
  5.         Arrays.sort(nums);
  6.         int res = 0;
  7.         for (int i = 0; i < nums.length - 2; ++i) {
  8.             if (nums[i] + nums[i + 1] + nums[i + 2] >= target) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  9.                 break;
  10.             }
  11.             int curr = nums[i];
  12.             int lo = i + 1, hi = nums.length - 1;
  13.             while (lo < hi) {
  14.                 while (lo < hi && curr + nums[lo] + nums[hi] >= target) {
  15.                     --hi;
  16.                 }. 1point 3acres 璁哄潧
  17.                 res += hi - lo;
  18.                 ++lo;
  19.             }
  20.         }
  21.         return res;
  22.     }
复制代码
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-8-28 12:32:15 | 显示全部楼层

噢这个只要返回数量就行了,明白啦谢谢
回复 支持 反对

使用道具 举报

wqsa007 发表于 2015-9-1 04:00:58 | 显示全部楼层
. From 1point 3acres bbs
08, 14行的>=是不是应该改成>
不然好像除去了相等的情况,问题包含了相等的情况。
回复 支持 反对

使用道具 举报

 楼主| flamen 发表于 2015-9-1 05:44:19 | 显示全部楼层
wqsa007 发表于 2015-8-31 12:00
08, 14行的>=是不是应该改成> .1point3acres缃
不然好像除去了相等的情况,问题包含了相等的情况。

不是哦,>=是对的,你再仔细看一下题目:)
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-24 18:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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