一亩三分地论坛

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

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

GOOGLE电面面经 估计跪了

[复制链接] |试试Instant~ |关注本帖
nickmyself 发表于 2014-3-14 03:07:34 | 显示全部楼层 |阅读模式

2014(7-9月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Fail

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

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

x
已知条件1)K个文件,编号 0 到 K-1。每个文件里存着的都是数字          2)有N台计算机,编号从0到N-1.    N远大于K 。 而且所有文件能被所有的机器访问到          3)一个函数 long sum(int FileID,int MachineID)   用指定机器计算指定文件 返回该文件里所有数总和. From 1point 3acres bbs
. 鍥磋鎴戜滑@1point 3 acres

Question:写一个function 求所有文件里的数字总和


楼主最后还是没写出来 估计已经跪了

本帖被以下淘专辑推荐:

 楼主| nickmyself 发表于 2014-8-14 04:47:36 | 显示全部楼层
额 这好久以前写的了  再补充完整吧
回复 支持 反对

使用道具 举报

 楼主| nickmyself 发表于 2014-9-28 10:42:23 | 显示全部楼层
楼主现下身:
那会我后来写了个map reduce思路的代码发过去 , 那边回复我问我有什么简单的方法么 。 然后我说其实只要用个多线程 把得到的结果加起来就可以了 。 只需一个线程锁。 然后那个人就貌似开心的给了我个一般的feedback(因为第一面实在太糟糕了,这样已经太给面子了). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

之后有了第二面. 第一道 是 atoi 的简单版(不用考虑那么多coner case)  第二道是写个(iterator 的iterator) 第三道是他发了3个java文件给我 让我改错(大概是个扑克比大小的class 中间有个很明显的逻辑错误)

onsite 4轮: 题记不大清楚了,  . Waral 鍗氬鏈夋洿澶氭枃绔,
1 leetcode 的 Surrounded Regions 原题小变形
2  写个方法,返回第x位对应的数字 (比如 1,2,3,4,5,6,7,8,9,10,11,12,13,14 ~ 无限....  index 0 对应 1, 9对应1, 10对应0  , 依次类推)( 其实是道数学题)
3  找一个普通的二叉树里的最大元素 (我给了个 BFS 的解法 不过那人不大满意)
4  设计题 (现在有个url的 arrayList, 你要写个加密算法 把它压缩成一个string, 然后还要写个解密算法 把这个string 还原成 url的arraylist);

还有一些leetcode的原题, 有点想不起了。  
然后这次面挂了, 觉得蛮可惜的, 那会leetcode才刷了一遍 感觉准备还不够充分。

最后再推荐个找工作的网站 hired.com. 主要的employer都是初创公司。
近期搞到好多面试,觉得挺好用的。大家可以点我的邀请进去,poriority会比自己申的相对高些。
http://join.hired.com/x/2Dmddb

祝大家早日手握各种offer.
                     

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

asdfyou6 发表于 2014-3-14 03:21:47 | 显示全部楼层
这是啥思路?求点拨
回复 支持 反对

使用道具 举报

lixiang.xjtu 发表于 2014-3-14 03:27:03 | 显示全部楼层
MapReduce!
回复 支持 反对

使用道具 举报

blackrose 发表于 2014-3-14 03:39:28 | 显示全部楼层
回复 支持 反对

使用道具 举报

Lisepher 发表于 2014-3-14 10:32:46 | 显示全部楼层
google不是很看重结果,而是更看中解题的过程,我第一轮店面也是第二道题没写完,最后还是过了
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-3-14 11:22:38 | 显示全部楼层
这题的关键条件是machine的个数比文件的个数大。为了提高计算的效率,就不能让一个机器去执行一整个文件,必须让所有的机器都参与到运算中。从这个角度出发考虑的话,应该用mapreduce的思想来做。
回复 支持 反对

使用道具 举报

MackeyZheng 发表于 2014-3-14 17:11:25 | 显示全部楼层
祝好运~!
回复 支持 反对

使用道具 举报

cgdong2012 发表于 2014-9-23 08:47:32 | 显示全部楼层
之前看不少面试题, 大家都有提到用 Map reduce 的思路去做。 做大数据和 Hadoop 也很多都用map reduce , 但是针对这个很典型的用 map reduce 题, 我想问 用map reduce 具体怎么实现? 面试用难道只提一下这个就行了?  小白一个, 忘解惑
回复 支持 反对

使用道具 举报

littlecoolblaxk 发表于 2014-9-24 12:59:49 | 显示全部楼层
同问啊 这道题我能想到的思路就是 先处理数据  把file们分成小file(这个算shard么? 感觉shard好像是在说把一堆数据分散到不同的服务器上。所以应该是不算了?)并且给小file赋上新的ID 这样mapper就可以处理小file 啦 处理好了以后 再把所有结果reduce一下  reduce的输出就是每个文件里数字的sum 然后因为K不是很大 再求和就行了 具体思路和大致代码如下:

假设把一个文件拆成10个小文件 那么就需要十个mapper 每个mapper负责一个小文件 mapper的输入就是大文件的ID (key) 和小文件的内容 (value)输入以后 利用输入的value生成新文件 并给新文件一个ID 这样就可以利用上题目中给的sum函数 sum函数返回算出来的总和 传给reducer
map (String key, String value) {
    //key : fileID
    //value : part of the file (1/10 for instance)

. 1point3acres.com/bbs    String FileID = genernateNewID();.鏈枃鍘熷垱鑷1point3acres璁哄潧
    File = new File(FileID, value);. 鍥磋鎴戜滑@1point 3 acres
    //the constructor is made up by myself. It returns a new file
    //with the new ID I just created in the previous step. And the content of
    // new file is the value from input (which is part of the original file)

    String MachineID = getMachine();
    // returns an available machine.鏈枃鍘熷垱鑷1point3acres璁哄潧

    long subSum = sum(FileID, MachineID);
    EmitReducer(key, sum);
}

鉴于我们有10个mapper都在处理同一个文件 那么我们会得到10个相同ID的mapper结果 那我们就得到了一个ID (也就是reducer的key) 和一个数组 数组存放的是这十个运算结果(也就是reducer的value啦) 传入后 把这十个小文件的sum求和 就得到了这个ID文件的总和。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

reduce(String key, Iterator values) {
    //key : fileID .鐣欏璁哄潧-涓浜-涓夊垎鍦
    //values : results from mapper
   
    long fileSum = 0;
    while (values.hasNext()) {
        fileSum += valuse.next();
    }
    Emit(key, fileSum);
}

最后 把所有reducer传来的结果求和 这个应该不是大数据了 就直接加就行了吧 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
代码写得有点恶心 一会儿真代码一会儿伪代码的 凑合看吧

是这样么 但是有个小问题 因为要用给定的函数sum(fileID, MachineID)  所以觉得似乎有必要把拆分大文件后的部分生成小文件 那是不是拆分后的小file又要占用磁盘空间?(感觉内存应该放不下) 这不是有点坑爹么?
. more info on 1point3acres.com

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

shinichish 发表于 2014-9-25 06:02:12 | 显示全部楼层
littlecoolblaxk 发表于 2014-9-24 12:59
同问啊 这道题我能想到的思路就是 先处理数据  把file们分成小file(这个算shard么? 感觉shard好像是在说 ...

请问,面试的时候要写到什么程度?没写过MapReduce的代码啊
回复 支持 反对

使用道具 举报

littlecoolblaxk 发表于 2014-9-25 10:29:16 | 显示全部楼层
shinichish 发表于 2014-9-25 06:02
请问,面试的时候要写到什么程度?没写过MapReduce的代码啊

我也没面过。。。。正忐忑准备面试中- -感觉这些题网上都在讨论 但就是没人说怎么答。。。。。。。。。。。。。。。。
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-9-26 14:22:19 | 显示全部楼层
littlecoolblaxk 发表于 2014-9-25 10:29
我也没面过。。。。正忐忑准备面试中- -感觉这些题网上都在讨论 但就是没人说怎么答。。。。。。。。。。 ...

是的。。如果有答案就好了,感觉可以学到很多。anyway,谢谢了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 18:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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