10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 9013|回复: 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. from: 1point3acres.com/bbs

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';. more info on 1point3acres.com
    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?. 鍥磋鎴戜滑@1point 3 acres
    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;.1point3acres缃
          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). From 1point 3acres bbs
       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:
        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
请问楼主在哪里面的?我也是13号面的,到现在还没消息。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我在Mountain View 面的啊,HR比较nice,主动联系我的。
回复 支持 反对

使用道具 举报

wuplus 发表于 2015-11-20 11:16:07 | 显示全部楼层
小小平民 发表于 2015-11-20 11:10
我在Mountain View 面的啊,HR比较nice,主动联系我的。

祝楼主接下来顺利啊。我的HR总是半天没反应,之前onsite约时间也是半天才给回信。等的好纠结。
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

补充内容 (2015-11-21 13:55):
同时恭喜楼主。
回复 支持 反对

使用道具 举报

 楼主| 小小平民 发表于 2015-11-22 00:23:27 | 显示全部楼层
maomaoxiong 发表于 2015-11-21 13:55
请问第二题 linkedlist这么做?第三题怎么从两边sort?谢谢。
. 1point3acres.com/bbs
补充内容 (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。还要拓展成二维的. From 1point 3acres bbs

第三题不是从两边sort,而是按照starting point sort。
比如intervals给的是 vector<pair<int,int>> ins;
先把节点存起来,存到另一个vector<pair<int,int>> points.
points 为节点值和-/+1. -1 代表右断点,+1代表左端点。.鏈枃鍘熷垱鑷1point3acres璁哄潧
for (pair<int,int> p:ins) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
    points.push_back(make_pair(p.first, 1));
    points.push_back(make_pair(p.second, -1));.鏈枃鍘熷垱鑷1point3acres璁哄潧
}
sort(points.begin(),points.end());. Waral 鍗氬鏈夋洿澶氭枃绔,
回复 支持 反对

使用道具 举报

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

-google 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


这个的最优解怎么搞?. 1point 3acres 璁哄潧

求教。
回复 支持 反对

使用道具 举报

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

楼主,能详细说说每行每列的元素cell如何存储吗?. Waral 鍗氬鏈夋洿澶氭枃绔,
你是用二维array来存吗?-google 1point3acres

还是像这样 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-9-20 10:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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