一亩三分地论坛

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

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

Thumtack跪经

[复制链接] |试试Instant~ |关注本帖
厉害的超人 发表于 2016-9-17 16:58:06 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 全职@Thumbtack - 内推 - Onsite |Fail在职跳槽

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

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

x
楼主一直在LA一小公司工作了三年多,公司要垮了,于是准备了半年多找新工作。
8月下旬onsite了thumbtack,本以为很有把握,结果还是挂了,现把面经发上来。(和地里面其他的thumbtack面经差不多). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

7月底的时候在mitbbs jobhunting版找到ala cat内推software engineer职位,很快就被HR联系安排OA。
OA题大家都一样:https://www.thumbtack.com/challenges/simple-database 时间不限。. Waral 鍗氬鏈夋洿澶氭枃绔,
设计时做到SET/UNSET/GET/NUMEQUALTO/BEGIN/COMMIT O(1)的时间复杂度就应该很容易过了。

接下来两个电面:(直接copy这个帖子的内容 http://www.1point3acres.com/bbs/thread-202203-1-1.html
phone1:
nearestPalindrome,返回输入的最近的palindrome的数字
for example:
input 9 ouput 9.1point3acres缃
input 98 output 99
input 100 output 101
. From 1point 3acres bbs
phone2:. from: 1point3acres.com/bbs
O(1) space insert getMean getMedian for data stream [0, 1000)
和bucket排序一样,生成1000个bucket,每个bucket记录有多少个该bucket index的数字。

onsite:
上午11:00,在google呆了10年的国人大哥来了,互相介绍后,问些背景问题后开始做个design/coding题。一个web crawler不停地收集网页、图片等信息,设计一个cache缓存这些东西(假设内存无穷大)。第一感觉就是个key-value cache,value是抓到的网页/图片存在local drive的path。我当时就想内存无穷大,就把网页图片都放内存吧,value就是一个object,用了一个c++的template来设计这个cache。后来他就问这个value究竟该用指针还是值,纠结了一会儿我又把value改成了指针。然后在白板上implement那个put函数。差不多了就说现在内存有限,用LRU保持cache里的内容。我就给他讲了LRU的原理和实现,然后开始写代码。在白板上写的慢,最后时间快到的时候还有些没有写完。我说再给我几分钟,反正后面是吃饭时间。结果国人大哥貌似挺不高兴说你吃饭也没多少时间的,就让我停下来了。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
根据后来的HR的反馈,我觉得挂在了这一轮国人大哥手里。说实话,LRU这些东西都已经非常熟悉了,只是国人大哥不苟言笑,要求挺高。

中午12:00吃饭,国人小哥陪同,全程中文,随便聊,说到了呆满两年options就不用买了,貌似就直接变成RSU了,觉得还挺神奇。. more info on 1point3acres.com
. more info on 1point3acres.com
中午12:30另一亚洲小哥来了(口音不像一般国人小哥,我并不能确定是不是中国人),聊背景好像还聊了挺久,然后做一道binary tree serialize/deserilize的题。Thumbtack面经就那么几道题,估计谁都见过。只好假装想一会儿了说一下思路几分钟就在电脑写完了测些case也没啥bug。最后问问时间空间复杂度之类的。HR最后的反馈是很好。

下午1:30和co-founder聊天,纯behavior问题,问为啥来thumbtack,以前的经历啊,工作的压力,passion之类的,和team member的关系啊等等。

下午2:00一美国小哥带一shadow欧洲小哥,互相介绍后问问most challenging的project之类的问题,然后就是tf_idf coding题,非常straight forward,面经里提到的必考题,早就写过了,只好又假装想一会儿然后慢慢写,自己随便测了一个case,美国小哥很开心都不用再测其他case了。HR最后的反馈也是很好。(thumbtack也不换换题,这些都是面试前刚刚写过一遍的,基本上不会出岔子)

下午3:00又一美国小哥面试官。先聊聊做过什么,随便问了些问题,然后一个系统设计题。这是一个类似图片分享的系统,有些具体要求,查看图片请求延迟希望小于300ms之类的,图片量多大等等。分析完user cases后就先给出了abstract design,具体讨论要用到哪些api,全程基本我在讲,小哥也没问啥问题。然后我说既然系统要求high availability,便指出了瓶颈在哪里,可以牺牲一下consistency(比如上传后别的用户不一定立马就能看到)。结论是需要cdn来缓存,小哥表示肯定,然后我把类似淘宝图片的缓存机制讲了一遍,说获取图片时最多一次hard drive IO read然后存入缓存,这样可以大大降低延迟。美国小哥一直在听,几乎没问啥问题。这一轮HR最后的反馈说面试官希望看到stronger signal。我后来想想当时他问了一两个问题貌似被我忽略了,没给我很好的评价很可能是因为交流不太好的原因(当时觉得有很多要讲,就在白板上写得很快,怕像第一轮那样没弄完)。.鐣欏璁哄潧-涓浜-涓夊垎鍦

最后下午4:00多离开的时候当时还想除了第一轮没写完,其他轮都感觉不错,只要第一轮的国人大哥不那么计较应该就有八成把握拿下的。但是最后还是挂了,现在的startup要求都非常高啊。
.鏈枃鍘熷垱鑷1point3acres璁哄潧


评分

2

查看全部评分

 楼主| 厉害的超人 发表于 2016-9-20 06:50:30 | 显示全部楼层
eko910817 发表于 2016-9-19 13:25
楼主。刚拿到thumbtack OA, 有点疑惑为什么它会把OA放到网上呢?是不是和hackerrank上的有出入?不一样呀? ...

这个OA给你的时间不限,是不是public无所谓了。题目完全一样,不会有出的。

网上能直接找到别人的Implement,但是不一定过的了他的要求。我就看到一个别人给出的很不错的Implement,先还照着这个思路写,但是要提交前发现COMMIT的时间不是O(1),然后自己重新思考一下,找到了符合要求的解法。Thumtack的HR就说过好多Google的software engineer去面他家还有不少过不了这个OA的。
回复 支持 2 反对 0

使用道具 举报

 楼主| 厉害的超人 发表于 2016-11-17 00:40:38 | 显示全部楼层
zfrancica 发表于 2016-11-15 21:59
tf_idf coding这题到底是什么样子的。。。+1...

鉴于不少地里的朋友问这题到底啥样子,其实这题很简单,不是什么算法题,就是把一个数学公式简单的用coding来实现而已。
首先他会问你知不知道tf_idf,我说基本了解(其实烂熟于胸了),他说不知道也没关系,然后他会把wiki上的tf_idf解释给你听,装着仔细听就行了,注意他的定义可能会稍微不一样,不过他会把公式写出来的。可以参考:https://zh.wikipedia.org/zh-hans/TF-IDF
他当时给的定义是输入要查询的几个关键字,每个文档的tf_idf的定义是:
要查询的几个关键字在该文档各自的tf_idf之和。
每个关键字的tf_idf的定义基本和wiki上的一样,稍微有点不同的是分母不是该文档中所有词出现的次数之和,而是频率最高的词出现的次数,其他一样:
tf_idf=keyCount/maxCount * log(n/docCount),这里keyCount是要查询的词在该文档中出现的次数,maxCount是该文档中频率最高的词出现的次数,n是总文档数,docCount是要查询的词出现在几个文档中。
最后的要求就是输入要查询的几个关键字,输出最高tf_idf的几个文档的序号,自己随便输入一些文档的词(他要考察你给的例子好不好),然后和他一起计算结果对不对。反正onsite都写了代码,这里就顺便贴在下边:
  1. #include <unordered_set>
  2. #include <unordered_map>
  3. #include <vector>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <iostream>

  7. using namespace std;

  8. /*
  9. input: vector<string> keys, vector<vector<string>> docs
  10. keys: a few key words to query
  11. docs: a list of docs, each doc is a list of strings
  12. return: highest ranking docs for query keys. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13. tf_idf definition:
  14. tf_idf=sum of each key's tf_idf. from: 1point3acres.com/bbs
  15. key's tf_idf=keyCount/maxCount * log(n/docCount)
  16. */
  17. . 鍥磋鎴戜滑@1point 3 acres
  18. vector<int> tf_idf(vector<string> & keys, vector<vector<string>> & docs) {
  19.     int n=docs.size(); // total number of the docs-google 1point3acres
  20.     vector<unordered_map<string, int>> keyCount(n); //each word's count in each doc. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  21.     vector<int> maxCount(n); //the most freq word's count in each doc
  22. . from: 1point3acres.com/bbs
  23.     for(int i=0; i<n; ++i) {
  24.         for(auto & word:docs[i]) {. 鍥磋鎴戜滑@1point 3 acres
  25.             ++keyCount[i][word];
  26.             maxCount[i]=max(maxCount[i],keyCount[i][word]);
  27.         }
  28.     }

  29.     unordered_map<string, int> docCount; //each word appears in how many docs
  30.     for (int i=0; i<n; ++i) {
  31.         for(string & key:keys) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  32.             if(keyCount[i].count(key)) ++docCount[key];
  33.         }
  34.     }

  35.     vector<pair<double, int>> tfidf(n); //each doc's tf_idf, pair.first: tf_idf, pair.second: file's index, pair is used for sorting
  36.     for (int i=0; i<n; ++i) {
  37.         for(string & key:keys) {
  38.             tfidf[i].first+=(keyCount[i][key]+0.0)/maxCount[i]*log((n+0.0)/docCount[key]);. visit 1point3acres.com for more.
  39.         }
  40.         tfidf[i].second=i;
  41.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  42.     sort(tfidf.begin(),tfidf.end(),greater<pair<double,int>>());
  43.     int m=2; //output first 2 highest tf_idf doc's index
  44.     vector<int> ret(m);
  45.     for(int i=0; i<m; ++i) {.1point3acres缃
  46.         ret[i]=tfidf[i].second;
  47.     }. Waral 鍗氬鏈夋洿澶氭枃绔,
  48.     return ret;
  49. }. Waral 鍗氬鏈夋洿澶氭枃绔,

  50. int main() {
  51.     vector<string> keys={"dog","cat"};
  52.     vector<vector<string>> docs={ //testing case, given by myself
  53.         {"dog", "dog", "cat", "a", "big"}, // 2/2*log(4/2)+1/2*log(4/2)
  54.         {"cat", "dog", "a", "big"}, // 1/1*log(4/2)+1/1*log(4/2).1point3acres缃
  55.         {"cow", "a", "the"},
  56.         {"the", "a"}
  57.     };
  58.     vector<int> ret;
  59.     ret=tf_idf(keys,docs);
  60.     for(auto & r:ret) cout << r << endl; //output doc's index
  61. }
复制代码
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-9-17 17:16:23 | 显示全部楼层
谢谢楼主分享,感觉这个OA好耗时间啊,网上能找到类似的代码吗?
回复 支持 反对

使用道具 举报

francis2016 发表于 2016-9-18 09:38:59 | 显示全部楼层
一直没有找到 “O(1) space insert getMean getMedian for data stream [0, 1000)”的完整题目。
哪位大虾给个链接啊?. 1point 3acres 璁哄潧
看到好像有人说贴过答案,但是没找到。
求链接:)
回复 支持 反对

使用道具 举报

 楼主| 厉害的超人 发表于 2016-9-18 12:39:11 | 显示全部楼层
francis2016 发表于 2016-9-17 17:38
一直没有找到 “O(1) space insert getMean getMedian for data stream [0, 1000)”的完整题目。
哪位大虾 ...

这个题哪有难度嘛,自己稍微想一下就写出来了。
还是给你把代码贴出来吧:
  1. class MedianFinder {
  2. public:.鐣欏璁哄潧-涓浜-涓夊垎鍦
  3.     // Adds a number into the data structure.. Waral 鍗氬鏈夋洿澶氭枃绔,
  4.     void addNum(int num) {
  5.         int c=cnt; //previous cnt
  6.         ++cnt;
  7.         avg=(avg*c+num)/cnt;
  8.         ++numbers[num];
  9.     }

  10.     float getAvg() {. From 1point 3acres bbs
  11.         return avg;
  12.     }

  13.     // Returns the median of current data stream
  14.     double findMedian() {
  15.         int half=cnt/2+1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  16.         int c=0;. 1point 3acres 璁哄潧
  17.         if(cnt%2==1) {
  18.             for(int i=0; i<N; ++i) {
  19.                 c+=numbers[i];
  20.                 if(c>=half) return i;
  21.             }
  22.         } else {
  23.             int half1=half-1;. 1point3acres.com/bbs
  24.             int m1=-1;
  25.             for(int i=0; i<N; ++i) {
  26.                 c+=numbers[i];
  27.                 if(c>=half1 && m1==-1) m1=i;
  28.                 if(c>=half) return 0.5*(m1+i); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  29.             }
  30.         }
  31.     }

  32. private:
  33.     int cnt=0;
  34.     double avg=0;
  35.     const int N=1000;. visit 1point3acres.com for more.
  36.     vector<int> numbers=vector<int>(N);
  37. };

  38. int main() {
  39.     MedianFinder mf;
  40.     mf.addNum(1);
  41.     cout << mf.findMedian() << endl;
  42.     mf.addNum(100);-google 1point3acres
  43.     cout << "avg: " << mf.getAvg() << endl;
  44.     cout << mf.findMedian() << endl;
  45.     mf.addNum(1000);
  46.     cout << mf.findMedian() << endl;
  47.     mf.addNum(500);
  48.     cout << mf.findMedian() << endl;
  49.     mf.addNum(30);
  50.     cout << mf.findMedian() << endl;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  51.     mf.addNum(0);
    . 1point 3acres 璁哄潧
  52.     cout << mf.findMedian() << endl;
  53.     mf.addNum(2000);
  54.     cout << "avg: " << mf.getAvg() << endl;. 鍥磋鎴戜滑@1point 3 acres
  55.     cout << mf.findMedian() << endl;
  56. }
复制代码
回复 支持 反对

使用道具 举报

eko910817 发表于 2016-9-20 05:25:42 | 显示全部楼层
楼主。刚拿到thumbtack OA, 有点疑惑为什么它会把OA放到网上呢?是不是和hackerrank上的有出入?不一样呀?谢谢楼主。
回复 支持 反对

使用道具 举报

eko910817 发表于 2016-9-20 11:16:32 | 显示全部楼层
私信请教楼主了。求回复
回复 支持 反对

使用道具 举报

direfire 发表于 2016-9-20 15:39:43 | 显示全部楼层
tf_idf coding这题到底是什么样子的。。。
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-10-31 11:03:56 | 显示全部楼层
想问下 tf_idf  这题到底是什么?谢谢了
回复 支持 反对

使用道具 举报

zfrancica 发表于 2016-11-16 13:59:51 | 显示全部楼层

tf_idf coding这题到底是什么样子的。。。+1...
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 14:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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