一亩三分地论坛

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

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

Google MTV Onsite

[复制链接] |试试Instant~ |关注本帖
mc422 发表于 2015-10-19 04:37:36 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
上周5Google MTVonsite,先把面经发上来,
第一轮: 一个中国小哥面的,人很nice。 第一题, 1.thereare n machines each contain different size of unsorted numbers, find the medianof all numbers. 要求尽量减少数据在machine之间的传输次数。我一开始想到 Hash +relocation的方法来处理所有数,在算中数位置,面试官问有没有能减少mahcine传输的方法。提醒之后想到了quicksort找中数的方法,用在N machines 上面。
2. Leetcode decode way.
第二轮: 一个美国哥们。1. write aninterface of random get number。写一个interface,insert() 插入 object,get() method随机返回一个object,remove()随机返回并删除object。写出method并减少complexity。写出来在他的要求下改进的code,但被他发现了不少bug。2. given random list of ticket, decide if all tickets cancombine into a trip path。 意思给一堆机票,能否吧所有机票连在一起成为一条path,可以从A出发,直接走到B。要求用掉所有机票。我给出的方法一直不能满足他的一些case,比如可以A---B---C---A----B---D这样的case。他给的提示方法,但还是没想出来。思路是拿到所有ticket之后找出起点和终点,起点出发的ticket一定比回来的多一张,终点回来的ticket比出发的多一张,找到之后再分析路径。最后才把方法搞明白,没写code。这轮有点惨。
第三路:像是个ABC,题目是Given a Iterator of iterator, create a iterator which pop outelement of each iterator one by one. 意思是给一个iterator iterator, 比如
Iterator A:   1à 2à3à4
Iterator B:   5-à6
Iterator C:   7à 8 à9
Createiterator需要next()这样的顺序: 1,5, 7, 2, 6, 8, 3, 9, 4
写的时候问了思路,做法是把iterator存到array里面了,通过index判断next()的iteratorarray哪一位。写完代码后他举例一种情况我的代码不能跑,想了之后改进说只存hasNext()的iterator。这轮只有一题,写代码和go through代码花了不少时间。
第四轮:一个老印,人挺友善的。题目都是抽象题,将思路为主。上来先让我解释TreeGraph,以及他们的区别。让后给了个题目:一个类似graph,里面的每个element都是一个node,每个node都有若干个connecting 到其他nodes。从一个点出发,找到所有在这个neighbor中的node。一个Node不在这个neighbor中表示他和那个neighbor中所有点都没有connection。简答想了个DFS,然后讲下思路他说就可以了。第二题:给了NmachinesMfile,里面有若干个数(N>>M),还有一个 sum(machine_id , file_id)的函数,算出所有filesum 一开始谢了个for循环,他说这样只能用一个machine。让后我说可以用MPI之类的东西,但code我一下子写不出来。让后他说用Java Thread也可以。我说我Thread不常用,可能写的不对(有点尴尬,Java基本只拿来刷题)。他说没关系,我大概写出了codeThread 应该写错了),他就说可以了。
基本就这些,请大家祝我好运,谢谢。
PS:楼主现在在小公司上班,平时比较忙,可以不能马上回复问题。请大家见谅。
. From 1point 3acres bbs

评分

2

查看全部评分

本帖被以下淘专辑推荐:

hyliu0000 发表于 2015-10-20 03:11:00 | 显示全部楼层
第一题换我就挂了。。主要是对quicksort不熟。。 楼主能详细说说这个吗?
第二题第二问有点像拓扑排序,但是又不完全是。 能想到的是建图,dfs从任意一点出发,然后看能不能把所有票用光。 第三题貌似也是leetcode原题?
第四题第二问用future 做async call? 然后sum一下?
第四题第一问没看懂。。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-20 06:18:35 | 显示全部楼层
感觉有几题还挺难的,不知道lz能否再解释一下机票那个题,谢谢啦!!!
回复 支持 反对

使用道具 举报

newlxnewlx 发表于 2015-10-24 05:24:52 | 显示全部楼层
Mark.  Thanks !
. visit 1point3acres.com for more.
# 4 - 2
interface FileChunk { int getFileId(); }
interface Machine {}

class Proto {
    Machine machine;
    FileChunk fileChunk;
    Long sum;
    Proto(Machine machine, FileChunk fileChunk, Long sum) {-google 1point3acres
        this.machine = machine;
        this.fileChunk = fileChunk;
        this.sum = sum;
    }
}

class Master {
    List<FileChunk> fileChunks; // assume now fileChunks.size() >= machines.size()
    List<Machine> machines;

    Long getSum() {
        ExecutorService service = Executors.newFixedThreadPool(machines.size());
        BlockingQueue<Proto> partialRes = new LinkedBlockingQueue<>();
-google 1point3acres        Iterator<FileChunk> fileChunkIterator = fileChunks.iterator();
        Map<Integer, AtomicLong> sum = new HashMap<>();

        for (FileChunk fileChunk : fileChunks) {
            sum.putIfAbsent(fileChunk.getFileId(), new AtomicLong(0));
        }

        for (Machine machine : machines) {
            service.submit(() -> {.1point3acres缃
                partialRes.offer(new Worker(machine, fileChunkIterator.next()).getSum());
            });
        }

        // block until finished. from: 1point3acres.com/bbs
        while (fileChunkIterator.hasNext()) {. 1point 3acres 璁哄潧
            try {
                Proto result = partialRes.take();
                sum.get(result.fileChunk.getFileId()).getAndAdd(result.sum);. more info on 1point3acres.com
                service.submit(() -> {. more info on 1point3acres.com
                    partialRes.offer(new Worker(result.machine, fileChunkIterator.next()).getSum());. 鍥磋鎴戜滑@1point 3 acres
                });
            } catch (InterruptedException e) {

            }
        }

        Long total = 0L;
        for (AtomicLong s : sum.values())
            total += s.get();
. From 1point 3acres bbs
        service.shutdown();
        return total;
    }
}
.鏈枃鍘熷垱鑷1point3acres璁哄潧
class Worker {.鏈枃鍘熷垱鑷1point3acres璁哄潧
    Machine machine;
    FileChunk fileChunk;
. from: 1point3acres.com/bbs
    Worker(Machine machine, FileChunk fileChunk) {
        this.machine = machine;
        this.fileChunk = fileChunk;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    }. 1point 3acres 璁哄潧
. more info on 1point3acres.com
    Proto getSum() {
        // simulating a blocking call. 1point 3acres 璁哄潧
        try {
            Random rnd = new Random();
            TimeUnit.SECONDS.sleep(rnd.nextInt(5));
            return new Proto(machine, fileChunk, rnd.nextLong());
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
}
回复 支持 反对

使用道具 举报

newlxnewlx 发表于 2015-10-24 05:26:26 | 显示全部楼层
第一题每个机器单独sort 再merge ?
回复 支持 反对

使用道具 举报

gorilazz 发表于 2015-10-24 05:51:51 | 显示全部楼层
楼主能把第二轮的第二题再解释下么?为什么起点出发的要比回来的多一张,比如A->B->A这种的不行?
回复 支持 反对

使用道具 举报

gorilazz 发表于 2015-10-24 06:08:22 | 显示全部楼层
第二轮第二题这么做行不行?
首先用票构建一个directed graph,两个城市之间有票的就是有edge,多张票也只算一次edge。在这个graph上做dfs,如果不是全连通的,那就没戏了。如果全连通,再挨个点数inbound和outbound edge的数量,只能有最多一个点的outbound edge数目比inbound多1
回复 支持 反对

使用道具 举报

怪兽岛 发表于 2015-10-29 04:15:53 | 显示全部楼层
问一下楼主投的什么职位?是new grad?因为有经验的一般不是面五轮吗?
回复 支持 反对

使用道具 举报

 楼主| mc422 发表于 2015-11-1 01:13:06 | 显示全部楼层
gorilazz 发表于 2015-10-24 05:51
楼主能把第二轮的第二题再解释下么?为什么起点出发的要比回来的多一张,比如A->B->A这种的不行?

这算是corner case,找不到起点和终点,因为A和B都可以是起点。普通的情况A-B-C, A只有出发一张,C只到达一张。
回复 支持 反对

使用道具 举报

 楼主| mc422 发表于 2015-11-1 01:13:48 | 显示全部楼层
怪兽岛 发表于 2015-10-29 04:15
问一下楼主投的什么职位?是new grad?因为有经验的一般不是面五轮吗?

是new grad
回复 支持 反对

使用道具 举报

djjkobe 发表于 2015-11-1 08:58:47 | 显示全部楼层
谁来讲一下第二轮第二题具体怎么做。。找到起点终点之后怎么找出路径?
回复 支持 反对

使用道具 举报

sophialyj 发表于 2015-11-3 09:41:45 | 显示全部楼层
楼主有消息了没?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 04:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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