Google Onsite 面经

jiebour 发表于 2015-9-11 06:30
memorizing fib，楼主这个啥意思？可以细说嘛？是指可以O(1)取出某个fib值嘛？

它不是fib的规则，是另一种计数规则，奇数作A处理，偶数做B处理，最终都会回到1

坐看云起 发表于 2015-9-11 08:27
最后一题画墙，能否用并查集来做？就是说，如果发现碰撞到的墙和自己属于一个集合，就意味着闭环了？

感觉可以的，这题应该很多做法的

memorizingfib 这个具体说说麻？

补充内容 (2015-9-11 08:54):
能贴下code吗？

楼主， 工作几年了。。

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) );
                }
        }
}

楼主，那个friends recommendation 是指从2nd connection里的人推荐嘛？

Williamslg 发表于 2015-9-17 03:45
楼主，那个friends recommendation 是指从2nd connection里的人推荐嘛？

是的，当时的提议是这样

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

可以讲下最后一题用什么结构存储数据吗 墙用什么结构表示 是要当场写code吗

https://en.wikipedia.org/wiki/Maze_generation_algorithm