一亩三分地论坛

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

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

Google on-site

[复制链接] |试试Instant~ |关注本帖
pro 发表于 2014-12-5 04:19:46 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Other

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

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

x
虽然有签NDA但是好像保密的内容并不是指面试题……以防万一还是全部用中文描述了。
1、返回只包含两个不同字符的最长的连续字串。"hello" => "ell" 或者 "llo"。2、检查一个字符串是否包含k位a进制数的所有表示形式。保证原字符串的所有字串都是合法的k位a进制数。"00110, a=2, k=2" => true (包括了00,01,10,11)。3、给一个数组a[n],令s[i]为a[i+1..n-1]中比a[i]大的数的数量。求最大的s[i]。要求O(nlogn)。<=这道题我一直在和面试官讨论解法最后没时间了一行代码都没写TAT 不过面试官说很喜欢我的思路。4、给一段输入文字,统计所有2-gram及出现次数。dataset有100G怎么办?你有100台32-bit机器(4G内存),怎么分发给100台机器处理?瓶颈在哪里?

评分

6

查看全部评分

辉哥哥 发表于 2014-12-5 13:40:24 | 显示全部楼层
jacgraphy 发表于 2014-12-5 08:29
请问第三题用mergesort的意思是不是这样:

function mergesort(array from s to e)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
public int getMax(int[] a, int start, int end){
                int[] count = new int[a.length];
                mergeSort(count, a, start, end);
               
                int max = 0;
                for(int i : count)
                        max = Math.max(max, i);
               
                return max;
        }
       
        public void mergeSort(int[] count, int[] a, int start, int end){
                if(start >= end){
                        count[start] = 0;
                       
                        return;
                }
                . more info on 1point3acres.com
                int mid = start + (end-start)/2;. Waral 鍗氬鏈夋洿澶氭枃绔,
               
                mergeSort(count, a, start, mid);
                mergeSort(count, a, mid+1, end);
               
                merge(count, a, start, mid, mid+1, end);
        }
       
        public void merge(int[] count, int[] a, int s1, int e1, int s2, int e2){
                int[] temp = new int[a.length];
                for(int i=0; i<a.length; i++)
                        temp = a;
               
                int p1 = s1, p2 = s2;
                int runner = s1;
                . From 1point 3acres bbs
                while(p1 <= e1 && p2 <= e2){
                       
                        //归并的时候计数
                        if(temp[p1] < temp[p2]){
                                a[runner] = temp[p1];-google 1point3acres
                               
                                count[runner] += e2-p2+1;
                                                . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                runner++;
                                p1++;
                        }
                        else{
                                a[runner] = temp[p2];
                               
                                count[runner] = count[p2];
                               
                                runner++;
                                p2++;
. 鍥磋鎴戜滑@1point 3 acres                        }
                }
               
                while(p1 <= e1){
                        a[runner] = temp[p1];
                       
                        count[runner] = count[p1];
                        -google 1point3acres
                        runner++;
                        p1++;
                }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
               
        }
回复 支持 0 反对 1

使用道具 举报

忽而今夏 发表于 2014-12-5 05:07:11 | 显示全部楼层
第一题leetcode新题啊
回复 支持 反对

使用道具 举报

辉哥哥 发表于 2014-12-5 06:42:52 | 显示全部楼层
第一题是lc上的。. Waral 鍗氬鏈夋洿澶氭枃绔,
第二题有什么好的想法吗?
第三题mergesort做符合NlogN的要求。
第四题看上去挺简单的, 是要写code吗?不知道楼主怎么答的
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-12-5 07:31:06 | 显示全部楼层
辉哥哥 发表于 2014-12-5 06:42
第一题是lc上的。
第二题有什么好的想法吗?
第三题mergesort做符合NlogN的要求。

2、弄给hashset类似的东西,一个个全部丢进去,数一数set里的元素数量有没有到a^k。这道题后面有个followup我没有想出来:满足这样的条件的字符串至少要有多长(用a和k表示),算是个组合数学的题目吧= =
3、不明白你的想法。能说详细点吗?-google 1point3acres
4、是的。主要是follow up了一些分布式系统的内容。
回复 支持 反对

使用道具 举报

jacgraphy 发表于 2014-12-5 08:29:54 | 显示全部楼层
辉哥哥 发表于 2014-12-4 17:42.1point3acres缃
第一题是lc上的。
第二题有什么好的想法吗?
第三题mergesort做符合NlogN的要求。

请问第三题用mergesort的意思是不是这样:

function mergesort(array from s to e)
    if  array is empty (s > e)
        return;
    find middle postion m;
    mergesort(subarray from m+1 to e);
    calculate s[m] and insert a[m] into subarray from m+1 to e by binary search in ;
    mergesort(subarray from s to m-1);. more info on 1point3acres.com
    merge two subarrays;
   

补充内容 (2014-12-4 19:39):
突然感觉递归到最底层的时候有些地方会有问题……

补充内容 (2014-12-4 20:03):
请无视我 = , =   这样做有问题,虽然好像可以通过改merge那一步改对,但是时间复杂度就高了。求问正确的做法
回复 支持 反对

使用道具 举报

rialmat 发表于 2014-12-5 09:43:49 | 显示全部楼层
jacgraphy 发表于 2014-12-5 08:29
请问第三题用mergesort的意思是不是这样:

function mergesort(array from s to e)

merge的时候,只要是左边的子数列中当前指向的数小,那么右边子数列中,从当前指向的数到最后都比那个数大。如果左边子数列中当前的数在原数组中的位置是i, 那么S += (右边从当前数到末尾的数的个数)。右数列中的数在原数组中肯定也是在该数的后面,左数列中比该数大的数原先也可能在其后面,但是已经在上一次的merge中考虑进去,所以每次merge只要看右边就行了。

这样看来,跟一般的merge没多大变化,复杂度仍然是nlogn
回复 支持 反对

使用道具 举报

jacgraphy 发表于 2014-12-5 09:55:49 | 显示全部楼层
rialmat 发表于 2014-12-4 20:43
merge的时候,只要是左边的子数列中当前指向的数小,那么右边子数列中,从当前指向的数到最后都比那个数 ...

原来如此,有道理! 谢谢~
回复 支持 反对

使用道具 举报

rettyye3 发表于 2014-12-5 10:05:25 | 显示全部楼层
第二题你说的那个followup应该就是当所有连续的k位都是满足要求的, 而且没有重复 a^k+k-1, 之前网上看到过这个问题... 是个数学问题 什么汉密尔顿环啥的
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-12-5 10:18:31 | 显示全部楼层
rettyye3 发表于 2014-12-5 10:05
第二题你说的那个followup应该就是当所有连续的k位都是满足要求的, 而且没有重复 a^k+k-1, 之前网上看到过 ...
. From 1point 3acres bbs
我按照直觉给了这个答案,但是当时没有办法给出数学上的证明。
回复 支持 反对

使用道具 举报

辉哥哥 发表于 2014-12-5 13:40:13 | 显示全部楼层
jacgraphy 发表于 2014-12-5 08:29
请问第三题用mergesort的意思是不是这样:
. 鍥磋鎴戜滑@1point 3 acres.鏈枃鍘熷垱鑷1point3acres璁哄潧
function mergesort(array from s to e)
. from: 1point3acres.com/bbs
public int getMax(int[] a, int start, int end){. 1point 3acres 璁哄潧
                int[] count = new int[a.length];
                mergeSort(count, a, start, end);
                . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                int max = 0;
                for(int i : count)
                        max = Math.max(max, i);
               
                return max;
        }
       
        public void mergeSort(int[] count, int[] a, int start, int end){
                if(start >= end){
                        count[start] = 0;
                       
                        return;
                }. 1point3acres.com/bbs
                . 1point 3acres 璁哄潧
                int mid = start + (end-start)/2;
                .1point3acres缃
                mergeSort(count, a, start, mid);
                mergeSort(count, a, mid+1, end);
               
                merge(count, a, start, mid, mid+1, end);
        }
        .1point3acres缃
        public void merge(int[] count, int[] a, int s1, int e1, int s2, int e2){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                int[] temp = new int[a.length];
                for(int i=0; i<a.length; i++)
                        temp = a;
               
                int p1 = s1, p2 = s2;. 1point 3acres 璁哄潧
                int runner = s1;
               
                while(p1 <= e1 && p2 <= e2){
                       
                        //归并的时候计数
                        if(temp[p1] < temp[p2]){
                                a[runner] = temp[p1];
                               
                                count[runner] += e2-p2+1;
                                               
                                runner++;
                                p1++;
.鐣欏璁哄潧-涓浜-涓夊垎鍦                        }
                        else{
                                a[runner] = temp[p2];. 1point 3acres 璁哄潧
                               
                                count[runner] = count[p2];
                               
                                runner++;. Waral 鍗氬鏈夋洿澶氭枃绔,
                                p2++;
                        }.1point3acres缃
                }
               
                while(p1 <= e1){
                        a[runner] = temp[p1];
                        . from: 1point3acres.com/bbs
                        count[runner] = count[p1];
                       
                        runner++;
                        p1++;
                }
               
        }
回复 支持 反对

使用道具 举报

辉哥哥 发表于 2014-12-5 13:49:20 | 显示全部楼层
rettyye3 发表于 2014-12-5 10:05
第二题你说的那个followup应该就是当所有连续的k位都是满足要求的, 而且没有重复 a^k+k-1, 之前网上看到过 ...

有链接吗, 给一个呗, 这道题还是没有理解怎么做。。。
回复 支持 反对

使用道具 举报

jacgraphy 发表于 2014-12-5 14:03:04 | 显示全部楼层
辉哥哥 发表于 2014-12-5 00:40
public int getMax(int[] a, int start, int end){
                int[] count = new int[a.length];
                mergeSort(c ...

非常感谢~ 字数字数
回复 支持 反对

使用道具 举报

rettyye3 发表于 2014-12-5 15:00:36 | 显示全部楼层
辉哥哥 发表于 2014-12-5 13:49-google 1point3acres
有链接吗, 给一个呗, 这道题还是没有理解怎么做。。。

http://en.wikipedia.org/wiki/De_Bruijn_sequence
. From 1point 3acres bbs
把所有a^k种可能性放在一个图里面, 然后可以连续的建一条边, 比如 011和111之间, 111和110之间有边...鐣欏璁哄潧-涓浜-涓夊垎鍦

然后证明这个图有hamiltonian path, 其实可以有cycle.. 这样就证明了那个最小值是可以实现的了

然后这个证明我又查了下还得用到什么欧拉路径的性质啥的 -_-||| 当时想这题想好久 然后搜了更久.... visit 1point3acres.com for more.

hope it helps
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-12-5 16:01:20 | 显示全部楼层
rettyye3 发表于 2014-12-5 15:00
http://en.wikipedia.org/wiki/De_Bruijn_sequence

把所有a^k种可能性放在一个图里面, 然后可以连续的 ...

谢谢!原来是这样证的……这个如果事先不知道面试的时候根本不可能从无到有的想出来啊_(:з」∠)_
回复 支持 反对

使用道具 举报

wondermu 发表于 2014-12-5 22:50:55 | 显示全部楼层
回复 支持 反对

使用道具 举报

yolkfive 发表于 2014-12-6 05:09:43 | 显示全部楼层
第二题还不是很明白。。。。
回复 支持 反对

使用道具 举报

latioswang 发表于 2014-12-6 15:55:39 | 显示全部楼层
马上就要面Google了,多谢楼主的面经,祝楼主好运,每一面只有一道题嘛?
回复 支持 反对

使用道具 举报

allonq 发表于 2014-12-31 07:11:04 | 显示全部楼层
什么是2gram 呢楼主? blessing
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-12-31 23:11:06 | 显示全部楼层
allonq 发表于 2014-12-31 07:11
什么是2gram 呢楼主? blessing

"i have a dream"

2-gram: "i have", "have a", "a dream". 1point3acres.com/bbs
3-gram: "i have a", "have a dream"
以此类推
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 09:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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