一亩三分地论坛

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

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

Google onsite 3/25

[复制链接] |试试Instant~ |关注本帖
xiaoniqiuqiu 发表于 2016-3-26 15:02:39 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 校园招聘会 - Onsite |Otherfresh grad应届毕业生

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

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

x
Google onsite 面经
今天刚面的,热乎乎的面经回馈地里的兄弟姐妹~
第一轮 一个说话不太听得懂的外国小哥(非美国人)
贪食蛇 就是手机里面的那个贪食蛇,不能出手机屏幕,头部不能吃到身体的任何部分,出了尾巴, 因为头部移过去的时候尾巴会移走,所以不会吃到
输入:
List of moves: [U, U, D, L, D, R….] U: up, D: down, L: left, R : right 移动的方向,有限长度的list
List of food: [(x1, y1), (x2, y2), (x3, y3)….] 食物的位置,有限长度的list
int: width 宽度 (屏幕宽度)
int: height 高度 (屏幕高度)
开始的时候,蛇在(0,0)的位置,长度是一
蛇每次吃到一个食物,长度就会增加一,然后得分也会加一,求最后的得分
食物是一个一个出现的,第一个食物没被吃到的话,第二个食物是不会出现的。

第二轮 印度人,一直不太高兴的样子
1) find 1 closest value to target in a BST, either larger or smaller is fine
2) find k closest values to target in a BST

中午饭是个特别nice的中国小哥,真的特别nice,特别感谢他

第三轮 美国小哥 这个小哥人也很好,一直笑眯眯的,没啥压力
先讨论hashing
然后是Iterator of Iterator
[
[1, 2, 3]
[4, 5]
[6, 7, 8]
输出1, 4, 6, 2, 5, 7, 3, 8

第四轮 亚裔小哥+shadow 这两个小哥人超好
1) max length of substring with k different characters in a string
2) leetcode 298. Binary Tree Longest Consecutive Sequence

很多应该都是地里面经的高频题,特别感谢之前提供面经的兄弟姐妹~
我弱弱的,但是真的是努力找工作很久了,可怜可怜我,给我一个offer吧
-google 1point3acres
. 1point3acres.com/bbs

补充内容 (2016-3-26 16:08):
贪食蛇那题,我当时的做法是用一个linkedlist+hashset来保存蛇的身体,后来跟朋友讨论,还是用queue+hashset比较好。每一步,如果出了边界,或者蛇下一步的头碰到了身体里除了尾巴的别的部分,游戏就结束了。

补充内容 (2016-3-26 16:12):
如果下一步是valid的,有两种情况:1)蛇头到了食物的位置,则linkedlist和set里加上新的蛇投头的位置,蛇尾巴的位置不变。2)蛇没吃到食物,则除了加上新的舌头,尾巴也会往前移一步,即之前的尾巴的位置就不是蛇

补充内容 (2016-3-26 16:13):.1point3acres缃
的身体的一部分了,要从linkedlist里面和set里面删除掉。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (2016-3-26 16:18):
为什么要用linkedlist+set的原因是,检查下一步的蛇头的位置是不是已经身体的一部分的时候,set可以O(1)做到,但是set不知道尾巴是哪一个;然后要删除尾巴的时候,可以从linklist拿到尾巴,从list和set删掉尾巴

评分

5

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
newbiee 发表于 2016-3-26 15:30:38 | 显示全部楼层
楼主,我来点赞了, 能说一下第一题你判断游戏结束的思路么?
我的想法是用一个queue<int[]>,用蛇的长度来限制capacity,超出则移出来queue最前面的部分,any better idea?
回复 支持 反对

使用道具 举报

 楼主| xiaoniqiuqiu 发表于 2016-3-26 15:40:46 | 显示全部楼层
newbiee 发表于 2016-3-26 15:30
楼主,我来点赞了, 能说一下第一题你判断游戏结束的思路么?
我的想法是用一个queue,用蛇的长度来限制cap ...

我是当所有的步数走完,或者所有的食物吃完就结束游戏的。
. visit 1point3acres.com for more.不好意思我没太明白你用queue的意思哈。
每一步都需要检查会不会导致游戏结束的,如果用queue来模拟蛇的话,就不能检查到蛇的头部会不会碰到身体的某一个部分。.鏈枃鍘熷垱鑷1point3acres璁哄潧
我把我的思路一会加在帖子后面,你可以看下哈。
回复 支持 反对

使用道具 举报

newbiee 发表于 2016-3-26 15:57:16 | 显示全部楼层
可以判断啊,而且是实时判断,有可能是食物没吃完就挂了;. 1point 3acres 璁哄潧
e.g 蛇的移动从(0, 0)->(0, 1)->(1,1) 如果蛇的长度 > 3,那么现在这3个点必然都是蛇的身体的一部分, 如果接下来碰到一个在queue里面的(这里可以加个hashset)来提高效率,那么就挂了;. 1point3acres.com/bbs
如果蛇的长度是2,还是上面的例子,这样的话第一个(0, 0)的点就不再有蛇身了, queue.poll() 出来;
. From 1point 3acres bbs
这是我的思路,你全部吃完在判断感觉有问题啊,会有中间是碰到身体了,但是移动一段后,又不碰的问题啊,感觉。。
回复 支持 反对

使用道具 举报

 楼主| xiaoniqiuqiu 发表于 2016-3-26 16:05:19 | 显示全部楼层
newbiee 发表于 2016-3-26 15:57
可以判断啊,而且是实时判断,有可能是食物没吃完就挂了;
e.g 蛇的移动从(0, 0)->(0, 1)->(1,1) 如果 ...

嗯嗯~感觉你的queue的方法确实蛮好的~
面试官的意思好像是,蛇头碰到身体了,游戏就结束了,直接返回分数就可以了的
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-26 21:16:06 | 显示全部楼层
除了第一题,基本都是高频题啊,祝楼主好运
回复 支持 反对

使用道具 举报

 楼主| xiaoniqiuqiu 发表于 2016-3-27 01:28:47 | 显示全部楼层
bobzhang2004 发表于 2016-3-26 21:16
除了第一题,基本都是高频题啊,祝楼主好运

嗯嗯,多谢多谢呀~
回复 支持 反对

使用道具 举报

GUIXIANG 发表于 2016-3-27 02:15:23 | 显示全部楼层
祝楼主好运,第三轮的iterator的问题能展开说一下吗?
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-3-27 09:45:45 | 显示全部楼层
赞啊 谢谢楼主分享!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-27 14:03:04 | 显示全部楼层
第一题应该是可以用queue来存蛇的每个点
回复 支持 反对

使用道具 举报

 楼主| xiaoniqiuqiu 发表于 2016-3-28 03:00:22 | 显示全部楼层
GUIXIANG 发表于 2016-3-27 02:15
祝楼主好运,第三轮的iterator的问题能展开说一下吗?

多谢多谢~
输入是Iterator<Iterator<Integer>>, 我用了一个List<Iterator<Integer>>,然后外层遍历一下Iterator<Iterator<Integer>>,把每个iterator都加到list里面,就可以顺序遍历里面的每个iterator啦
回复 支持 反对

使用道具 举报

 楼主| xiaoniqiuqiu 发表于 2016-3-28 03:01:11 | 显示全部楼层
Alice0701 发表于 2016-3-27 09:45
赞啊 谢谢楼主分享!
-google 1point3acres
哈哈,我也看了很多别人的面经嘛,好传统要保持~
回复 支持 反对

使用道具 举报

 楼主| xiaoniqiuqiu 发表于 2016-3-28 03:01:50 | 显示全部楼层
bobzhang2004 发表于 2016-3-27 14:03
第一题应该是可以用queue来存蛇的每个点
. visit 1point3acres.com for more.
是的,queue比直接用linkedlist要方便
回复 支持 反对

使用道具 举报

kemeng1314 发表于 2016-3-28 03:51:04 | 显示全部楼层
楼主您好:感谢面经. more info on 1point3acres.com

想问一下两行输入是不是表示蛇整个游戏的move路径已经定死,而不是我们自己去选择(这个游戏最后得分就是唯一的,而不是寻找最优)。比如第一个list里面每个对象元素是包括两个属性这样吗(方向,步数)。第二个问题是蛇在移动过程中整个身子可能出现任意形状吧,比如直线,L或U形状等。

谢谢!
回复 支持 反对

使用道具 举报

tianlu1 发表于 2016-3-28 08:53:47 | 显示全部楼层
第一天可以用Deque + HashSet来,Deque是一个double linkedlist,加头去尾很方便
回复 支持 反对

使用道具 举报

tianlu1 发表于 2016-3-28 09:35:51 | 显示全部楼层
贪食蛇我的Java code
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
public int findMaxLength(List<Character> moves, List<int[]> food, int width, int height){
                if(width < 1 || height < 1) return 0;
                if(moves == null || food == null || moves.size() == 0 || food.size() == 0) return 1;
               
                Deque<int[]> dequeSnake = new LinkedList<int[]>(); // store the locations of snake
                HashSet<int[]> mapSnake = new HashSet<int[]>(); // store the locations of snake
                HashMap<Character, int[]> moveMap = new HashMap<Character, int[]>(); // dictionary for move directions;
               
                moveMap.put('U', new int[]{1, 0});
                moveMap.put('D', new int[]{-1, 0});
                moveMap.put('L', new int[]{0, 1});
                moveMap.put('R', new int[]{0, -1});
               
                Iterator<Character> itr_moves = moves.iterator();
                Iterator<int[]> itr_food = food.iterator();
                . From 1point 3acres bbs
                int[] nextFood = itr_food.next();
                dequeSnake.offer(new int[]{0,0});.鏈枃鍘熷垱鑷1point3acres璁哄潧
                mapSnake.add(new int[]{0,0});. Waral 鍗氬鏈夋洿澶氭枃绔,
               
                while(itr_moves.hasNext()){
                        char move = itr_moves.next();
                        int[] loc = dequeSnake.peek();
                        int[] next = new int[]{loc[0] + moveMap.get(move)[0], loc[1] + moveMap.get(move)[1]};
                       
                        // case1: next out of screen. From 1point 3acres bbs
                        if(next[0] < 0 || next[0] >= height || next[1] < 0 || next[1] >= width) return dequeSnake.size();
                       
                        // case2: next is food
                        else if(next[0] == nextFood[0] && next[0] == nextFood[0]){
                                if(mapSnake.contains(next)) return dequeSnake.size();
                                mapSnake.add(next);
                                dequeSnake.add(next);.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                if(!itr_food.hasNext()) return dequeSnake.size(); // all food are ate by snake, max length reached;
                                else nextFood = itr_food.next();
                        }
                       
                        // case3: next is not food
                        else{
                                int[] tail = dequeSnake.pollLast();
                                mapSnake.remove(tail);
                                if(mapSnake.contains(next)) return dequeSnake.size() + 1;
                                mapSnake.add(next);
                                dequeSnake.add(next);
                        }
                }
       
                return dequeSnake.size();
        }
回复 支持 反对

使用道具 举报

 楼主| xiaoniqiuqiu 发表于 2016-3-28 10:31:34 | 显示全部楼层
kemeng1314 发表于 2016-3-28 03:51
楼主您好:感谢面经

想问一下两行输入是不是表示蛇整个游戏的move路径已经定死,而不是我们自己去选择( ...

对的对的,结果是确定的,要求就是把结果算出来而已。
移动那里,我当时的理解是每次都是移动一步,没有想到多步的情况唉。。我太naive了。。
身体是会出现各种形状的。
回复 支持 反对

使用道具 举报

Wrath 发表于 2016-3-28 14:08:18 | 显示全部楼层
LZ是在MTV onsite的吗
回复 支持 反对

使用道具 举报

 楼主| xiaoniqiuqiu 发表于 2016-3-28 14:15:41 | 显示全部楼层
Wrath 发表于 2016-3-28 14:08
LZ是在MTV onsite的吗
.鏈枃鍘熷垱鑷1point3acres璁哄潧
对的对的
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-28 23:40:43 | 显示全部楼层
请问楼主电面以后多久收到消息呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 17:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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