推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 8954|回复: 23
收起左侧

google onsite 11/13 HR11/18来电话过了HC

[复制链接] |试试Instant~ |关注本帖
小小平民 发表于 2015-11-20 06:12:52 | 显示全部楼层 |阅读模式

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

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

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

x
电面请转这里:
http://www.1point3acres.com/bbs/thread-141774-1-1.html. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
http://www.1point3acres.com/bbs/thread-142665-1-1.html

Onsite questions:
    Round 1:
    Q1. Given char array and corresponding double array, return a random char that has the same probability as the double array.. more info on 1point3acres.com
        Eg: char * a = "abc",   double * d = [0.2, 0.7, 0.1]. You should have 20% chance to return 'a', 70% to return 'b' and 10% to return 'c';
    Follow up: how to test if the function is correct?
    Solution:  convert the double array to intervals and generate random number (0 - 1) and check which intervals is the number in.
         Eg: a:  0 - 0.2
               b:  0.2 - 0.9
               c: 0.9 - 1
    Q2.  given millions of electronic books and each book contains hundreds of pages. Given a function OCR to convert the electronic image of book pages to text file. That is to say, scan the books first to get photo copy and then convert the image to text file. So in the process, there is supposed to be 5% error. How do we tell if two books are identical considering the error?
    Error can come from several cases liek:  "word random" -> "word ran dom";  "word random" -> "worded random"; "word random" -> "word     "
    Solution: It's an open ended question, you can propose different approches.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    Round 2:
    Q1. Given a sparse excel file, design a data structure to effectively store all the informations.
        Sparse means most of the excel are empty.
        Write 4 functions: void set(int row, int col, int val),  int get(int row, int col), vector<int> getRow(int row), vector<int> getCol(int col)
        getRow and getCol returns the corresponding row or column that is indexed at the input number which neglect empty cells.
    Solution:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        Using this one:    unordered_map<int, unordered_map<int,int>> myMap1, myMap2;
          myMap1: (row -> (col -> val)) ;  myMap2: (col -> (row -> val))
       Follow up: what if there is a function eraseRow or eraseCol like in excel you can erase a whole row or column.
       Hash table solution becomes unefficient because row index and column index changes and this cause erase time complexity to be O(n)
       Solution : using LinkedList, and I have no time for coding

    Round 3: Overlapping Intervals
        Given a vector of intervals, return the interval that has the most overlap.
        Eg: [0, 1], [2, 8], [3, 5], [4, 6], [9, 10]
        return 3 and [4,5] because for interval [4,5] there are 3 overlapping intervals.
    Solution:. 1point3acres.com/bbs
        sort starting and ending points and then scan. plus one if left node met, minus one if right node met. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

.鐣欏璁哄潧-涓浜-涓夊垎鍦    Round 4: multiply strings
        Given two integers represented by strings, return their product.
        Follow up: how to increase time complexity and how to test it.. from: 1point3acres.com/bbs
        Solution is straightforward, just need to be careful about corner cases and invalid input.

评分

5

查看全部评分

本帖被以下淘专辑推荐:

wuplus 发表于 2015-11-20 10:38:07 | 显示全部楼层
请问楼主在哪里面的?我也是13号面的,到现在还没消息。
回复 支持 反对

使用道具 举报

 楼主| 小小平民 发表于 2015-11-20 11:10:47 | 显示全部楼层
wuplus 发表于 2015-11-20 10:38
请问楼主在哪里面的?我也是13号面的,到现在还没消息。

我在Mountain View 面的啊,HR比较nice,主动联系我的。
回复 支持 反对

使用道具 举报

wuplus 发表于 2015-11-20 11:16:07 | 显示全部楼层
小小平民 发表于 2015-11-20 11:10
我在Mountain View 面的啊,HR比较nice,主动联系我的。
. 1point3acres.com/bbs
祝楼主接下来顺利啊。我的HR总是半天没反应,之前onsite约时间也是半天才给回信。等的好纠结。
回复 支持 反对

使用道具 举报

 楼主| 小小平民 发表于 2015-11-21 13:21:08 | 显示全部楼层
已经给了offer哟
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-21 13:55:27 | 显示全部楼层
请问第二题 linkedlist这么做?第三题怎么从两边sort?谢谢。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. more info on 1point3acres.com
补充内容 (2015-11-21 13:55): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
同时恭喜楼主。
回复 支持 反对

使用道具 举报

 楼主| 小小平民 发表于 2015-11-22 00:23:27 | 显示全部楼层
maomaoxiong 发表于 2015-11-21 13:55
请问第二题 linkedlist这么做?第三题怎么从两边sort?谢谢。

补充内容 (2015-11-21 13:55):

LinkedList的思路是 吧每行每列的元素的cell存下来,node记的是与前面cell的差值。这样删除一行就只用改后面一个列的数据。
比如 原来有1 6 8 9 14 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
本来删除第6行的时候,要变成1 7 8 13 需要修改6 后面的 8 9 14 的index.
但是如果我们存的是前后index的差值,我们只需要修改删除行的后面那个index 。
比如 一样的例子: 1 5 2 1 5
我们还是删除一行,只需要改成 1 6 1 5  我们只需要修改一个就好了。
思路是这样,没写code。还要拓展成二维的

第三题不是从两边sort,而是按照starting point sort。
比如intervals给的是 vector<pair<int,int>> ins;
先把节点存起来,存到另一个vector<pair<int,int>> points.
points 为节点值和-/+1. -1 代表右断点,+1代表左端点。
for (pair<int,int> p:ins) {
    points.push_back(make_pair(p.first, 1));
    points.push_back(make_pair(p.second, -1));
}. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
sort(points.begin(),points.end());
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-22 01:41:55 | 显示全部楼层
小小平民 发表于 2015-11-22 00:23
LinkedList的思路是 吧每行每列的元素的cell存下来,node记的是与前面cell的差值。这样删除一行就只用改 ...

谢谢回答。只是改成linked list后get()的复杂度不是变成O(n)了么?
回复 支持 反对

使用道具 举报

likeulb 发表于 2015-11-22 03:49:37 | 显示全部楼层
请问楼主是mtv面的吗?感觉还挺迅速的啊
回复 支持 反对

使用道具 举报

虾米酱 发表于 2015-11-24 20:59:36 | 显示全部楼层
请教楼主最后一轮怎么降低时间复杂度丫,只想到把第二个字符串的每一位和第一个相乘移位, 再把这些乘好的字符串相加
回复 支持 反对

使用道具 举报

evil 发表于 2015-12-2 10:34:31 | 显示全部楼层
请问楼主拿到了offer了么?过了HC等了多久啊?
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-12-2 10:36:10 | 显示全部楼层
恭喜楼主 沾沾喜气啊
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-12-3 01:29:16 | 显示全部楼层
Round 4: multiply strings
        Given two integers represented by strings, return their product.
        Follow up: how to increase time complexity and how to test it.
        Solution is straightforward, just need to be careful about corner cases and invalid input.. f
. Waral 鍗氬鏈夋洿澶氭枃绔,

这个的最优解怎么搞?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

求教。
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-12-3 02:11:01 | 显示全部楼层
小小平民 发表于 2015-11-22 00:23
LinkedList的思路是 吧每行每列的元素的cell存下来,node记的是与前面cell的差值。这样删除一行就只用改 ...

楼主,能详细说说每行每列的元素cell如何存储吗?
你是用二维array来存吗?

还是像这样 List((差值, List(差值, cell)))
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-12-3 02:35:21 | 显示全部楼层
round1 其实也不简单啊。  楼主实力毋庸置疑。 楼主round1 去how to test if the function is correct?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2015-12-3 02:36):
round1 q1这个是怎么答得?另外 q2 楼主是怎么答得?
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-7 06:54:53 | 显示全部楼层
恭喜楼主...这么多test的面的是tools and infra吗
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-7 07:02:42 | 显示全部楼层
楼主厉害啊..问下round 1 q 2怎么答得
回复 支持 反对

使用道具 举报

csmargaret 发表于 2016-1-19 14:04:49 | 显示全部楼层
请问round2 q1 follow up linked list怎么存cell啊?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-27 05:15:13 | 显示全部楼层
请问楼主round1 的Q2是怎么答的?
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-10-12 06:37:22 | 显示全部楼层
round 1 q1 我觉得用cumulative distribution 然后hashmap搞定?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-21 09:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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