一亩三分地论坛

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

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

Google 电面面经

[复制链接] |试试Instant~ |关注本帖
ron1990 发表于 2016-1-8 06:44:06 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
1月5号的google电面,实在是太囧,12月约的··时间太久给忘了是在5号···一直以为是6号。对面打电话过来之后才发现是今天···跟面试官讨价还价半天约到了3小时之后再打一个电话. 1point3acres.com/bbs
主要问了两个题吧. 1point 3acres 璁哄潧
一个不知道算什么类型的题,一个算法
第一题:问有一个marble,含有名字name和颜色color两个属性。问你用什么数据结构,可以任意的拿和放入其中,使的每次拿的时候取到任意一个marble的概率都是一样。
follow up 如果你有1M种颜色,平均每个颜色有1M个marble,但是你的内存没有1M*1M这么大,这时这个数据结构用什?

第二题 算法 给你一个arr 返回 T 或者 F
arr的每个数代表从这个点开始跳几部,返回T的情况:从这个arr中任意一个数开始跳,可以在每个元素都跳到且只跳到一次的情况下返回到开始跳的元素
比如[1,1,1,1,1,1] => T
[0,1,1,1,1,1]=> F
[7, 5, 2, 3] => F. more info on 1point3acres.com
[2,2,3,1] => T

评分

1

查看全部评分

lancelot981 发表于 2016-1-25 10:23:46 | 显示全部楼层
我觉得第一题一维array顺序存就好了吧?取的时候取random一个,然后将最后的填到取了的空位上。followup就在内存里搞个1M大小数组存不同颜色的,每个数组指向一个文件,文件里面存marble。拿的时候random两次,第一次选颜色,第二次选marble。
第二题的话就用一个同样大小的数组存哪些数字被跳过了。任挑一个位置开始。如果遇到两边可以跳的位置都跳过就return false。如果最后跳到初始位置就在看看是不是所有都跳过了。如果是就return true
回复 支持 2 反对 0

使用道具 举报

lancelot981 发表于 2016-2-20 07:27:19 | 显示全部楼层
哗啦啦 发表于 2016-2-19 21:15
但是不一定每次取出来之后马上就有新的填进去吧?不能用array啊
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
没说要用新的填啊,拿最后的填就好啦,反正不按顺序
回复 支持 1 反对 0

使用道具 举报

头像被屏蔽
q19890217 发表于 2016-1-8 06:56:09 来自手机 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

beefcurtain5 发表于 2016-1-8 06:59:27 | 显示全部楼层
第二题, 好像就是看看从每个element, 能跳到哪里。。。 然后是不是所有的元素都能跳到而且只跳到一次?
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2016-1-8 07:17:11 | 显示全部楼层
lz, 第一题是不是HashMap + Array? follow up怎么整?array 放1 M个index instead of marble object?
回复 支持 反对

使用道具 举报

虾米酱 发表于 2016-1-8 10:13:16 | 显示全部楼层
同问follow up
回复 支持 反对

使用道具 举报

 楼主| ron1990 发表于 2016-1-8 11:41:46 | 显示全部楼层
beefcurtain5 发表于 2016-1-8 06:59
第二题, 好像就是看看从每个element, 能跳到哪里。。。 然后是不是所有的元素都能跳到而且只跳到一次?

不是不是···是每个元素是几就必须跳几次。对。最后的要求是所有元素都要被跳到而且只被跳到一次。
回复 支持 反对

使用道具 举报

 楼主| ron1990 发表于 2016-1-8 11:42:02 | 显示全部楼层
q19890217 发表于 2016-1-8 06:56
楼主是fresh graduate职位吗

对对对~字数字数
回复 支持 反对

使用道具 举报

 楼主| ron1990 发表于 2016-1-8 11:45:03 | 显示全部楼层
nothingtrouble 发表于 2016-1-8 07:17
lz, 第一题是不是HashMap + Array? follow up怎么整?array 放1 M个index instead of marble object?

对··我基本思路也是这样的····但是我觉得我的答案他不是太满意,. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我是想arr那里也弄一个hash让在arr里拿任意一个marble也是随机的···
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-8 12:39:51 | 显示全部楼层
请问楼主第二题的思路是什么?
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-1-8 15:18:36 | 显示全部楼层
第一题完全没思路唉 能讲讲吗
回复 支持 反对

使用道具 举报

269644943 发表于 2016-1-8 16:44:37 | 显示全部楼层
第一题完全不懂,求楼主讲讲. visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

MrA 发表于 2016-1-8 16:45:07 | 显示全部楼层
谢谢楼主的分享~~~~
回复 支持 反对

使用道具 举报

唐老鸭 发表于 2016-1-9 13:03:03 | 显示全部楼层
第一题要求可以随意加入移除,不能用array吧,是不是应该用ArrayList? 为什么要用hash?如果要求返回每个marble概率相同,岂不是把每个marble都放到arraylist里,然后Random取?Follow up求讲
第二题没懂什么意思啊?比如【7,5,2,3】,怎么跳?数组是个环?能再解释下吗?
回复 支持 反对

使用道具 举报

hzyslddm 发表于 2016-1-25 14:44:21 | 显示全部楼层
第二题有好的思路吗?求问LZ第二题是不是在每个点向前跳和向后跳都可以的?
回复 支持 反对

使用道具 举报

哗啦啦 发表于 2016-2-19 21:15:27 | 显示全部楼层
lancelot981 发表于 2016-1-25 10:23
我觉得第一题一维array顺序存就好了吧?取的时候取random一个,然后将最后的填到取了的空位上。followup就 ...

但是不一定每次取出来之后马上就有新的填进去吧?不能用array啊
回复 支持 反对

使用道具 举报

ABCamille 发表于 2016-2-21 15:24:57 | 显示全部楼层
楼主[2,2,3,1]=>T 这个不太懂,第一个是2就去了3那里?然后3的话左右都跳不了 这不应该是F么?
回复 支持 反对

使用道具 举报

wju1556 发表于 2016-2-22 22:59:47 | 显示全部楼层
第二题是backtrack吗?
回复 支持 反对

使用道具 举报

tianlu1 发表于 2016-2-24 02:20:43 | 显示全部楼层
第二题O(n) 解法:
public boolean arrayJump(int[] arr){
                if(arr == null || arr.length == 0 ) return false; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                if(arr.length == 1) return arr[0] == 0;
               
                int n = arr.length;
                HashSet<Integer> jump = new HashSet<Integer>();.1point3acres缃
               
                for(int i = 0; i < arr.length; i++){
                        int next = (i + arr[i]) % n;. visit 1point3acres.com for more.
                        if(jump.contains(next)) return false;
                        else jump.add(next);. 1point 3acres 璁哄潧
                }
               
                return true;
        }
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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