一亩三分地论坛

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

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

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

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

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

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

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

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..鐣欏璁哄潧-涓浜-涓夊垎鍦
        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     ". more info on 1point3acres.com
    Solution: It's an open ended question, you can propose different approches.. From 1point 3acres bbs

    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:. visit 1point3acres.com for more.
        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
. 鍥磋鎴戜滑@1point 3 acres
    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:
        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.
        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. From 1point 3acres bbs
请问楼主在哪里面的?我也是13号面的,到现在还没消息。

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

使用道具 举报

wuplus 发表于 2015-11-20 11:16:07 | 显示全部楼层
小小平民 发表于 2015-11-20 11:10. more info on 1point3acres.com
我在Mountain View 面的啊,HR比较nice,主动联系我的。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
祝楼主接下来顺利啊。我的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?谢谢。
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (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. more info on 1point3acres.com
LinkedList的思路是 吧每行每列的元素的cell存下来,node记的是与前面cell的差值。这样删除一行就只用改 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
谢谢回答。只是改成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

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这个的最优解怎么搞?

求教。
回复 支持 反对

使用道具 举报

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搞定?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 01:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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