一亩三分地论坛

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

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

Google 面经

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

2015(4-6月) 码农类 硕士 全职@Google - 内推 - Onsite |Other在职跳槽

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

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

x
1.  给你 N 个人 , 有个 function  follow(i, j) 可以check 是否 i follow j,  求 master ( 所有人都follow 他, 他不follow 任何人)-google 1point3acres
   要求 o(n)

2.  3 三个数的sum 小于等于 target, 问有多少种, 要求 n^2.-google 1point3acres
. 1point 3acres 璁哄潧
.鐣欏璁哄潧-涓浜-涓夊垎鍦


补充内容 (2015-6-7 09:47):
3. design: distributed game ,   付费转账 如何 减少 transcation fee .鏈枃鍘熷垱鑷1point3acres璁哄潧
4. group Card  ,  follow up: 如何定义接口 让客户可以自己定义 hashfunction.

评分

4

查看全部评分

本帖被以下淘专辑推荐:

guokecccc 发表于 2015-6-7 10:46:09 | 显示全部楼层
请问lz第一题怎么o(n)做?
回复 支持 反对

使用道具 举报

wugoat 发表于 2015-6-7 10:47:55 | 显示全部楼层
多谢分享面经! 第三四问能否具体描述一下 比如第三问考点是 还有第四问的card是poker吗
回复 支持 反对

使用道具 举报

1370786136.1.3 发表于 2015-6-7 12:12:52 | 显示全部楼层
guokecccc 发表于 2015-6-7 10:46
请问lz第一题怎么o(n)做?

这个类似celebrity problem, 可以做到O(n)
回复 支持 反对

使用道具 举报

 楼主| xiaoxi99cs 发表于 2015-6-7 14:37:58 | 显示全部楼层
http://blog.csdn.net/kalium/article/details/7596570 这里的第一题 是一样的
回复 支持 反对

使用道具 举报

 楼主| xiaoxi99cs 发表于 2015-6-7 14:40:17 | 显示全部楼层
wugoat 发表于 2015-6-7 10:47
多谢分享面经! 第三四问能否具体描述一下 比如第三问考点是 还有第四问的card是poker吗

对  class Card  {
    int rank;
    Character color;
}.鐣欏璁哄潧-涓浜-涓夊垎鍦

这题不难, 就是hashmap , 第二问主要考点是 java design, 可以给一个interface 让 client 自己定义hash function, 然后你的算法是 调用哪个 hash function.
回复 支持 反对

使用道具 举报

 楼主| xiaoxi99cs 发表于 2015-6-7 14:41:08 | 显示全部楼层
guokecccc 发表于 2015-6-7 10:46. from: 1point3acres.com/bbs
请问lz第一题怎么o(n)做?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
就是 celebrity problem:
http://blog.csdn.net/kalium/article/details/7596570 这里的第一题 是一样的
回复 支持 反对

使用道具 举报

 楼主| xiaoxi99cs 发表于 2015-6-7 14:41:31 | 显示全部楼层
1370786136.1.3 发表于 2015-6-7 12:12
这个类似celebrity problem, 可以做到O(n)

牛啊  见多识广啊 :)
回复 支持 反对

使用道具 举报

readman 发表于 2015-6-7 14:43:24 | 显示全部楼层
那第一题当年面经一堆..后来空白了一阵又来了
回复 支持 反对

使用道具 举报

 楼主| xiaoxi99cs 发表于 2015-6-7 14:57:15 | 显示全部楼层
碰上了老人家, 老人家 才问这老题的 ><
回复 支持 反对

使用道具 举报

wugoat 发表于 2015-6-7 23:51:33 | 显示全部楼层
xiaoxi99cs 发表于 2015-6-7 14:40
对  class Card  {
    int rank;
    Character color;

感觉考RPC啊, 第三问的minimize trasaction fee能否详细描述一下
回复 支持 反对

使用道具 举报

嘻嘻呵呵飞出去 发表于 2015-6-8 16:15:48 | 显示全部楼层
多谢分享!
. visit 1point3acres.com for more.
最后那个定义接口 让客户可以自定义hashfunction 如何实现啊?求点拨?
我定义一个interface,interface里override hashCode(),这样客户implement这个interface,那么之后呢?不太明白
回复 支持 反对

使用道具 举报

say543 发表于 2015-6-9 10:08:51 | 显示全部楼层
请问楼主第二题要怎么做到n^2呢?
回复 支持 反对

使用道具 举报

yawnzh 发表于 2015-6-10 06:23:58 | 显示全部楼层
say543 发表于 2015-6-9 10:08
请问楼主第二题要怎么做到n^2呢?

def three_sum(A,target):
    if not A:
        return 0
    A.sort() #sort the array O(NlnN)
    res=0
    for i in xrange(len(A)):.鏈枃鍘熷垱鑷1point3acres璁哄潧
        sum=target-A
        j=i+1
        k=len(A)-1
        while j<k:
            #if A+A[j]+A[k] is equal or less than target,
            #A+A[j]+A[h] for j<h<k would also less than target
            if A[j]+A[k]<=sum:
                res+=k-j
                j+=1
            else:. more info on 1point3acres.com
                k-=1
    return res
这是我的想法,先排序,再用两层循环,如果A+A[j]+A[k]满足要求,j<h<k,那么A+A[j]+A[h]也满足要求
回复 支持 反对

使用道具 举报

yawnzh 发表于 2015-6-10 06:25:07 | 显示全部楼层
yawnzh 发表于 2015-6-10 06:23
def three_sum(A,target):
    if not A:
        return 0

为什么A打不出来
回复 支持 反对

使用道具 举报

say543 发表于 2015-6-10 07:44:07 | 显示全部楼层
感谢回应      楼上这想法我之前想过     考虑有重复的这个case ex: 2 2 3 3 4 4 5 5, target = 12, 如果在第一层循环 skip一样的value 防止duplication 会漏掉3 4 4 这个valid 的case..... 有别的方法防止duplication吗?
回复 支持 反对

使用道具 举报

 楼主| xiaoxi99cs 发表于 2015-6-10 12:49:05 | 显示全部楼层
say543 发表于 2015-6-10 07:44
感谢回应      楼上这想法我之前想过     考虑有重复的这个case ex: 2 2 3 3 4 4 5 5, target = 12, 如果在 ...
  1. int count(int[] num, int target){. visit 1point3acres.com for more.
  2.             int res = 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.             for(int i=0;i<num.length-2;i++){
  4.                 int l = i+1;
  5.                 if( i>0 && num[i] == num[i-1] ){
  6.                     continue; // remove duplicate
  7.                 }
  8.                 int r = num.length -1;
  9.                 while(l<r){
  10.                     if(  num[i] + num[l] + num[r] <= target ) {
  11.                             if( l> i+1 && num[l] == num[l-1] ) {// remove duplicate
  12.                                     l++;
  13.                                     continue;
  14.                             }
  15.                         res += 1;. 1point3acres.com/bbs
  16.                         l++;. more info on 1point3acres.com
  17.                     }
  18.                     else{
  19.                              
  20.                         r--;
  21.                     }
  22.                 }
  23.             }
  24.             return res;
  25.         }
复制代码

补充内容 (2015-6-10 12:55):
sorry, 忘了 sort 了,            Arrays.sort(num );
回复 支持 反对

使用道具 举报

say543 发表于 2015-6-11 03:46:41 | 显示全部楼层
感谢回应 这想法也会漏掉3 4 4 这个valid 的case.....用代碼驗證過...
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-6-12 13:35:14 | 显示全部楼层
say543 发表于 2015-6-10 07:44.1point3acres缃
感谢回应      楼上这想法我之前想过     考虑有重复的这个case ex: 2 2 3 3 4 4 5 5, target = 12, 如果在 ...

如果是14楼的方法 第一层循环去重后,应该不会漏掉344 这个case。 因为题意是求一共有多少个。  比如 现在得到第一个数是3 (即 i=2), 那start = 3, end = 7 ,开始进行while (start < end) 第一个比较的是 3 + 3 + 5, 因为小于target 12, 所以 5之前的 和 3   3 相加都满足小于12; 然后start ++, 这时候 比较 3 + 4 + 5 依然小于等于12, 所以 5之前的 和 3  4 相加都满足条件(包括了3 4 4)。但这种会出现两个334 和两个335 这个不知道怎么在O(n*n)内解决 。。
回复 支持 反对

使用道具 举报

say543 发表于 2015-6-13 04:50:06 | 显示全部楼层
感谢回应 19楼 说的对...
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 20:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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