一亩三分地论坛

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

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

Google新鲜面经

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

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

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

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

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问题,然后立马改了下就结束了
.鐣欏璁哄潧-涓浜-涓夊垎鍦
求大米求大米求大米~~┏ (゜ω゜)=☞ 重要的事情说三遍~~

评分

7

查看全部评分

本帖被以下淘专辑推荐:

discoveryi 发表于 2015-8-12 07:09:46 | 显示全部楼层
    // O(n^2) solution
    public static int findNumberOfTriangles(int[] a) {
        int n = a.length;. 1point3acres.com/bbs
        Arrays.sort(a);. 鍥磋鎴戜滑@1point 3 acres
        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++;
                }. 鍥磋鎴戜滑@1point 3 acres
                count += k - j - 1;. Waral 鍗氬鏈夋洿澶氭枃绔,
            }
        }
        return count;
    }
. Waral 鍗氬鏈夋洿澶氭枃绔,
    // O(n^3) solution
    public static int findNumberOfTriangles2(int[] a) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        int n = a.length;
        Arrays.sort(a);. Waral 鍗氬鏈夋洿澶氭枃绔,
        int count = 0;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n; j++) {-google 1point3acres
                for (int k = j + 1; k < n; k++) {
                    if (a + a[j] > a[k]) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        count++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                    }
                }.鏈枃鍘熷垱鑷1point3acres璁哄潧
            }.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
        return count;
    }
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-8-12 07:10):
原题是:

/**
* 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 | 显示全部楼层
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
. Waral 鍗氬鏈夋洿澶氭枃绔,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么?所以都是满足条件的。注意原题是

I see. 没有注意到题目是<=。 多谢指出!
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

Williamslg 发表于 2015-8-15 09:20:38 | 显示全部楼层
请问这里需要考虑重复嘛?能否给个例子
. 1point3acres.com/bbs
补充内容 (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. Waral 鍗氬鏈夋洿澶氭枃绔,
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) {. visit 1point3acres.com for more.
  3.             return 0;-google 1point3acres
  4.         }. visit 1point3acres.com for more.
  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];. from: 1point3acres.com/bbs
  12.             int lo = i + 1, hi = nums.length - 1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.             while (lo < hi) {
  14.                 while (lo < hi && curr + nums[lo] + nums[hi] >= target) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.                     --hi;
  16.                 }
  17.                 res += hi - lo;
  18.                 ++lo;
  19.             }
  20.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  21.         return res;. from: 1point3acres.com/bbs
  22.     }
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

wqsa007 发表于 2015-9-1 04:00:58 | 显示全部楼层

08, 14行的>=是不是应该改成>
不然好像除去了相等的情况,问题包含了相等的情况。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 18:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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