要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 3172|回复: 11
收起左侧

Google MTV Onsite

[复制链接] |试试Instant~ |关注本帖
我的人缘0
mc422 发表于 2015-10-19 04:37:36 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

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:楼主现在在小公司上班,平时比较忙,可以不能马上回复问题。请大家见谅。

评分

2

查看全部评分


上一篇:Bloomberg phone interview
下一篇:有人做过amazon的retail system promotion team的OA

本帖被以下淘专辑推荐:

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

使用道具 举报

我的人缘0
宝贝忆彼岸 发表于 2015-10-20 06:18:35 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
感觉有几题还挺难的,不知道lz能否再解释一下机票那个题,谢谢啦!!!
回复 支持 反对

使用道具 举报

我的人缘0
newlxnewlx 发表于 2015-10-24 05:24:52 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
Mark.  Thanks !

# 4 - 2
interface FileChunk { int getFileId(); }
interface Machine {}

class Proto {
    Machine machine;
    FileChunk fileChunk;
    Long sum;
. 留学申请论坛-一亩三分地    Proto(Machine machine, FileChunk fileChunk, Long sum) {
        this.machine = machine;
        this.fileChunk = fileChunk;
        this.sum = sum;
    }. Waral 博客有更多文章,
}

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

    Long getSum() {
        ExecutorService service = Executors.newFixedThreadPool(machines.size());. 1point 3acres 论坛
        BlockingQueue<Proto> partialRes = new LinkedBlockingQueue<>();
        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(() -> {. from: 1point3acres
                partialRes.offer(new Worker(machine, fileChunkIterator.next()).getSum());
            });
        }

        // block until finished
        while (fileChunkIterator.hasNext()) {
            try {
                Proto result = partialRes.take();
                sum.get(result.fileChunk.getFileId()).getAndAdd(result.sum);
                service.submit(() -> {. from: 1point3acres
                    partialRes.offer(new Worker(result.machine, fileChunkIterator.next()).getSum());
                });
            } catch (InterruptedException e) {

            }.留学论坛-一亩-三分地
        }

        Long total = 0L;
        for (AtomicLong s : sum.values())
            total += s.get();
来源一亩.三分地论坛.
        service.shutdown();
        return total;
    }. more info on 1point3acres
}

class Worker {
    Machine machine;
    FileChunk fileChunk;
. visit 1point3acres for more.
    Worker(Machine machine, FileChunk fileChunk) {
        this.machine = machine;
        this.fileChunk = fileChunk;
    }
来源一亩.三分地论坛.
    Proto getSum() {
        // simulating a blocking call
        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);
        }
    }
}
回复 支持 反对

使用道具 举报

我的人缘0
newlxnewlx 发表于 2015-10-24 05:26:26 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一题每个机器单独sort 再merge ?
回复 支持 反对

使用道具 举报

我的人缘0
gorilazz 发表于 2015-10-24 05:51:51 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
楼主能把第二轮的第二题再解释下么?为什么起点出发的要比回来的多一张,比如A->B->A这种的不行?
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
怪兽岛 发表于 2015-10-29 04:15:53 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
问一下楼主投的什么职位?是new grad?因为有经验的一般不是面五轮吗?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| mc422 发表于 2015-11-1 01:13:06 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
gorilazz 发表于 2015-10-24 05:51
楼主能把第二轮的第二题再解释下么?为什么起点出发的要比回来的多一张,比如A->B->A这种的不行?

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

使用道具 举报

我的人缘0
 楼主| mc422 发表于 2015-11-1 01:13:48 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
怪兽岛 发表于 2015-10-29 04:15
问一下楼主投的什么职位?是new grad?因为有经验的一般不是面五轮吗?

是new grad
回复 支持 反对

使用道具 举报

我的人缘0
djjkobe 发表于 2015-11-1 08:58:47 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
谁来讲一下第二轮第二题具体怎么做。。找到起点终点之后怎么找出路径?
回复 支持 反对

使用道具 举报

我的人缘0
sophialyj 发表于 2015-11-3 09:41:45 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
楼主有消息了没?
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-27 22:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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