一亩三分地论坛

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

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

Google Onsite 面经

[复制链接] |试试Instant~ |关注本帖
zhouyoung1124 发表于 2015-9-11 02:49:07 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Fail在职跳槽

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

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

x
第一轮 国人小哥
Recurring decimal leetcode 原题,轻松秒掉,聊了下原题
第二轮 印度大叔
给两个Set A,B, A – Bset,忽略BA没有的元素,只输出A中有B中没有,或者B中也有但出现次数较少的元素, hashmap,轻松摆平。
设计功能,可能认识的人。做对1st connection 的好友列表(忽略自己)做BFS,HashMap统计相同好友人数,并将结果按照相同好友在其好友所占百分比排序
第三轮 白人大叔
两轮面完已经1145,我心情好好的把大脑挑着休眠模式准备背着包准备和进来的人去吃饭,结果他说他不是带我吃饭的,而是上午最后一轮面试官。。。。我当时就蒙B,我有个习惯不太好,一放松,再收起来全速想事情至少要15分钟时间。然后就开始面,问了一个只比memorizingfib略难一些的类似算法,结果能用30行的recursion解决的题,磕磕巴巴折腾半天,面试官明显一副你在逗我吗的表情。。。
午饭是个印度小哥带去吃的,我完全没有兴致聊天不过还是勉力和他嘻嘻哈哈。。。心里一直在想这是什么傻逼安排。。。上午三场下午一场。。。
第四轮 辽宁大叔
友好的不行,聊得非常好,一道常规海量数据和一个OOD,聊完我觉得这下还有戏,三好一不好,碰下狗屎运了。。。
第五轮 白人小哥
就在LZ又一次放松下来的时候敲门声响起,我还和大叔说你去忙吧,我自己走出去就行。结果进来的人不是来找大叔的。。。尼玛还有一场。。。题目是设计一个randommaze generator. 其实就是在一个二维空间画墙但不能允许有封闭空间。我的思路很简单, maintain一个closedSet 里面添加所有处理过的点,maintain一个变量hit,记录生出的枝撞墙的次数,不能有封闭空间的条件实际就是每个点延伸出去的树不能二次撞墙(coveredby hit)或者咬到自己(coveredby closed
定义好这些后开始,遍历矩阵,对于每个不在closedBFS,当前点扔进closed然后随机数决定我们要不要take这个option,处理到没点可以处理后,hit0,往下一个走。
这个思路听起来不是很复杂,但是其实coding的时候还是细节挺多的,,,我当时已经心里各种草泥马家不淡定了,代码只写了一半时间就到了,而且面试官一开始也不怎么理解我判断没有封闭空间的标准,我拖着半挂的大脑和费了不少口舌。。。
大家去面试的时候长个心一定要上午问HR那好schedule sheets,我的HR早上说还没拿到具体安排,我就没留心也没坚持要,以后碰到这种情况的话,至少也要问清面几场,怎么安排。。。
还有各位在东部要飞去面试的同胞,一定记得多请一天假上午就飞去,,,我到旅馆已经是12点了。。。加上时差对我们而言就已经是3点,,,

评分

1

查看全部评分

本帖被以下淘专辑推荐:

rhett.lhy 发表于 2015-9-17 10:02:09 | 显示全部楼层
最后一题判断封闭空间那个不可以直接用disjoint set吗?就跟做最小生成树的时候判断加一条边后会不会有环类似
回复 支持 2 反对 0

使用道具 举报

hbsophia 发表于 2015-9-11 03:26:31 | 显示全部楼层
BLESS LZ,  听上去还行,lz好人,祝lz早日拿到大offer !
回复 支持 反对

使用道具 举报

cbwcs 发表于 2015-9-11 04:00:46 | 显示全部楼层
感谢楼主分享经验,Bless
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-9-11 04:37:30 | 显示全部楼层
祝福楼主!求问像海量数据这种题咋做啊?哪有范例。。
回复 支持 反对

使用道具 举报

 楼主| zhouyoung1124 发表于 2015-9-11 04:40:26 | 显示全部楼层
hj867955629 发表于 2015-9-11 04:37
祝福楼主!求问像海量数据这种题咋做啊?哪有范例。。

http://blog.csdn.net/v_july_v/article/details/7382693
这篇我觉得就不错,忽略它那个传销一样的标题吧。。。内容上我觉得面试来说就差不多能问到这儿
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-9-11 04:50:31 | 显示全部楼层
zhouyoung1124 发表于 2015-9-11 04:40
http://blog.csdn.net/v_july_v/article/details/7382693
这篇我觉得就不错,忽略它那个传销一样的标题 ...

谢谢!那像ood这种题怎么准备呢?
回复 支持 反对

使用道具 举报

 楼主| zhouyoung1124 发表于 2015-9-11 05:36:40 | 显示全部楼层
hj867955629 发表于 2015-9-11 04:50
谢谢!那像ood这种题怎么准备呢?

OOD没什么定式的准备,面试的时候注意交流问清要求,别的都和算法题一样
回复 支持 反对

使用道具 举报

daniel123 发表于 2015-9-11 05:52:58 | 显示全部楼层
请问楼主是什么时候投的简历,什么时候拿到的phone interview 和 onsite
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-11 06:30:38 | 显示全部楼层
memorizing fib,楼主这个啥意思?可以细说嘛?是指可以O(1)取出某个fib值嘛?
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-9-11 08:27:08 | 显示全部楼层
最后一题画墙,能否用并查集来做?就是说,如果发现碰撞到的墙和自己属于一个集合,就意味着闭环了?
回复 支持 反对

使用道具 举报

 楼主| zhouyoung1124 发表于 2015-9-11 08:43:53 | 显示全部楼层
jiebour 发表于 2015-9-11 06:30
memorizing fib,楼主这个啥意思?可以细说嘛?是指可以O(1)取出某个fib值嘛?

它不是fib的规则,是另一种计数规则,奇数作A处理,偶数做B处理,最终都会回到1
回复 支持 反对

使用道具 举报

 楼主| zhouyoung1124 发表于 2015-9-11 08:44:54 | 显示全部楼层
坐看云起 发表于 2015-9-11 08:27
最后一题画墙,能否用并查集来做?就是说,如果发现碰撞到的墙和自己属于一个集合,就意味着闭环了?

感觉可以的,这题应该很多做法的
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-11 08:53:10 | 显示全部楼层
memorizingfib 这个具体说说麻?

补充内容 (2015-9-11 08:54):
能贴下code吗?
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-11 08:56:56 | 显示全部楼层
楼主, 工作几年了。。
回复 支持 反对

使用道具 举报

 楼主| zhouyoung1124 发表于 2015-9-11 09:42:36 | 显示全部楼层
hulahu 发表于 2015-9-11 08:53
memorizingfib 这个具体说说麻?

补充内容 (2015-9-11 08:54):

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷import java.util.List;
import java.util.Queue;
import java.util.Random;
import java.util.Set;

class Point {
        public int x;
        public int y;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        public Point( int x, int y  ) {
                this.x = x;
                this.y = y;
.鏈枃鍘熷垱鑷1point3acres璁哄潧        }
       
        // Override these two methods for the collection method .contains(Object o)
        @Override. from: 1point3acres.com/bbs
        public boolean equals( Object o ) {
                if ( o instanceof Point  ) {. visit 1point3acres.com for more.
                        Point p = (Point) o;. 鍥磋鎴戜滑@1point 3 acres
                        return p.x == this.x && p.y == this.y;
                }
                return false;
                . 1point3acres.com/bbs
        } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        @Override. 1point 3acres 璁哄潧
        public int hashCode(){
                final int prime1 = 31, prime2 = 19;
        return prime1 * x + prime2 * y;
        }       
}.鏈枃鍘熷垱鑷1point3acres璁哄潧

// Only for record output, Name "Wall" sounds much more appropriate than line
class Wall {
        Point p1;
        Point p2;
        public Wall( Point p1, Point p2 ) {-google 1point3acres
                this.p1 = p1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                this.p2 = p2;
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}.鏈枃鍘熷垱鑷1point3acres璁哄潧

public class MazeGenerator {.鏈枃鍘熷垱鑷1point3acres璁哄潧
        Set< Point > closed = new HashSet< Point >(); // Collection of points processed
        List< Wall > res = new ArrayList< Wall >();
        int randomMod = 2; // We can control the average number of walls by setting up this mod
        int MazeX = 7;  
        int MazeY = 7;
        int hit = 0; // Times hit on bound
        public List< Wall > drawMaze () throws IllegalArgumentException{                .1point3acres缃
                for ( int i = 0; i <= MazeX; ++i ) {-google 1point3acres
                        for ( int j = MazeY; j >= 0; --j ) {
                                // For each point not in closed set do a BFS to add lines . visit 1point3acres.com for more.
                                // by this way, walls can be distributed paths instead of single-root path
                                Point p = new Point( i , j );
                                if ( closed.contains(p) || new Random().nextInt(1000) %randomMod == 0) {
                                        continue;
                                }
                                if ( p.x == 0 || p.y == 0 || p.x == MazeX || p.y == MazeY ) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                        if ( hit != 0 ) {
                                                continue;
                                        }
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷                                        ++hit;. from: 1point3acres.com/bbs
                                }
                                int sz = res.size();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                Queue< Point > q = new LinkedList< Point >();-google 1point3acres
                                closed.add(p);
                                q.add(p);
                                while( !q.isEmpty() ) {
                                        Point cur = q.poll();
                                        List< Point > ops = getOps(cur);
                                        for ( Point pp : ops ) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                                if ( new Random().nextInt(1000) % randomMod == 0 && !closed.contains(pp)) {
                                                        connect( cur , pp );
                                                        closed.add(pp);
                                                        q.offer(pp);
                                                }
                                        }. 1point 3acres 璁哄潧
                                }
                                if ( sz == res.size() ) {
                                        if ( p.x == 0 || p.y == 0 || p.x == MazeX || p.y == MazeY ) {
                                                hit = hit - 1;. 鍥磋鎴戜滑@1point 3 acres
                                        }. From 1point 3acres bbs
                                }. 鍥磋鎴戜滑@1point 3 acres
                        }
                }
                return res;
        }        . From 1point 3acres bbs
        private List< Point > getOps( Point p ) {
                List< Point > res = new ArrayList< Point >();
                if ( (p.x > 1 || ( p.x == 1 && hit < 1 ) )&& p.y != 0  && p.y != MazeY) {
                        Point t = new Point( p.x - 1 , p.y);
                        if ( !closed.contains(t) )
                                res.add( t );
                }
                if (( p.y > 1 || ( p.y == 1 && hit < 1 ) ) && p.x != 0  && p.x != MazeX) {. visit 1point3acres.com for more.
                        Point t = new Point( p.x  , p.y - 1);
                        if ( !closed.contains(t) )
                                res.add( t );.1point3acres缃
                }
                if ( ( p.x < MazeX - 1 || ( p.x == MazeX - 1 && hit < 1 ) )&& p.y != 0 && p.y != MazeY) {
                        Point t = new Point( p.x + 1 , p.y);
                        if ( !closed.contains(t) )
                                res.add( t );
                }
                if ( (p.y < MazeY - 1 || ( p.y == MazeY - 1 && hit < 1 )) && p.x != 0 && p.x != MazeX) {. visit 1point3acres.com for more.
                        Point t = new Point( p.x , p.y + 1);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        if ( !closed.contains(t) )
                                res.add( t );. 1point3acres.com/bbs
                }
                return res;
        }
        private void connect( Point p1 , Point p2 ) {
                if ( p2.x == 0 || p2.y == 0 || p2.x == MazeX || p2.y == MazeY ) {
                        if ( hit != 0 ) {
                                return;. from: 1point3acres.com/bbs
                        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        ++hit;
                }
                res.add( new Wall( p1 , p2 ) );
        }
        public static void main(String args[]){
                List< Wall > lines = new MazeGenerator().drawMaze();
                for ( Wall l : lines ) {
                        System.out.println( String.format("( %s, %s ) -> (%s , %s )", l.p1.x, l.p1.y,l.p2.x,l.p2.y) );
                }
        }
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Williamslg 发表于 2015-9-17 03:45:48 | 显示全部楼层
楼主,那个friends recommendation 是指从2nd connection里的人推荐嘛?
回复 支持 反对

使用道具 举报

 楼主| zhouyoung1124 发表于 2015-9-17 09:17:02 | 显示全部楼层
Williamslg 发表于 2015-9-17 03:45
楼主,那个friends recommendation 是指从2nd connection里的人推荐嘛?

是的,当时的提议是这样
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-18 21:54:48 | 显示全部楼层
可以讲下最后一题用什么结构存储数据吗 墙用什么结构表示 是要当场写code吗
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-18 22:00:42 | 显示全部楼层
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 02:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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