Google Onsite 面经

第一轮 国人小哥

Recurring decimal leetcode 原题，轻松秒掉，聊了下原题

第二轮 印度大叔

给两个Set A,B, 求 A – B的set,忽略B有A没有的元素，只输出A中有B中没有，或者B中也有但出现次数较少的元素， hashmap,轻松摆平。

设计功能，可能认识的人。做对1s

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

候还是细节挺多的，，，我当时已经心里各种草泥马家不淡定了，代码只写了一半时间就到了，而且面试官一开始也不怎么理解我判断没有封闭空间的标准，我拖着半挂的大脑和费了不少口舌。。。

大家去面试的时候长个心一定要上午问HR那好schedule sheets,我的HR早上说还没拿到具体安排，我就没留心也没坚持要，以后碰到这种情况的话，至少也要问清面几场，怎么安排。。。

还有各位在东部要飞去面试的同胞，一定记得多请一天假上午就飞去，，，我到旅馆已经是12点了。。。加上时差对我们而言就已经是3点，，，

最后一题判断封闭空间那个不可以直接用disjoint set吗？就跟做最小生成树的时候判断加一条边后会不会有环类似

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;
        }
       
        // Override these two methods for the collection method .contains(Object o)
        @Override
        public boolean equals( Object o ) {
                if ( o instanceof Point  ) {
                        Point p = (Point) o;
                        return p.x == this.x && p.y == this.y;
                }
                return false;
               
        }
        @Override
        public int hashCode(){
                final int prime1 = 31, prime2 = 19;
        return prime1 * x + prime2 * y;
        }       
}

// Only for record output, Name "Wall" sounds much more appropriate than line
class Wall {
        Point p1;
        Point p2;
        public Wall( Point p1, Point p2 ) {
                this.p1 = p1;
                this.p2 = p2;
        }
}

public class MazeGenerator {
        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{               
                for ( int i = 0; i <= MazeX; ++i ) {
                        for ( int j = MazeY; j >= 0; --j ) {
                                // For each point not in closed set do a BFS to add lines
                                // 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;
                                }
                                int sz = res.size();
                                Queue< Point > q = new LinkedList< Point >();
                                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);
                                                }
                                        }
                                }
                                if ( sz == res.size() ) {
                                        if ( p.x == 0 || p.y == 0 || p.x == MazeX || p.y == MazeY ) {
                                                hit = hit - 1;
                                        }
                                }
                        }
                }
                return res;
        }       
        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) {
                        Point t = new Point( p.x  , p.y - 1);
                        if ( !closed.contains(t) )
                                res.add( t );
                }
                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) {
                        Point t = new Point( p.x , p.y + 1);
                        if ( !closed.contains(t) )
                                res.add( t );
                }
                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;
                        }
                        ++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) );
                }
        }
}

hj867955629 发表于 2015-9-11 04:37
祝福楼主！求问像海量数据这种题咋做啊？哪有范例。。

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

BLESS LZ,  听上去还行，lz好人，祝lz早日拿到大offer !

感谢楼主分享经验，Bless

祝福楼主！求问像海量数据这种题咋做啊？哪有范例。。

zhouyoung1124 发表于 2015-9-11 04:40
http://blog.csdn.net/v_july_v/article/details/7382693
这篇我觉得就不错，忽略它那个传销一样的标题 ...

谢谢！那像ood这种题怎么准备呢？

hj867955629 发表于 2015-9-11 04:50
谢谢！那像ood这种题怎么准备呢？

OOD没什么定式的准备，面试的时候注意交流问清要求，别的都和算法题一样

请问楼主是什么时候投的简历，什么时候拿到的phone interview 和 onsite

memorizing fib，楼主这个啥意思？可以细说嘛？是指可以O(1)取出某个fib值嘛？

最后一题画墙，能否用并查集来做？就是说，如果发现碰撞到的墙和自己属于一个集合，就意味着闭环了？