Thumtack跪经

楼主一直在LA一小公司工作了三年多，公司要垮了，于是准备了半年多找新工作。
8月下旬onsite了thumbtack，本以为很有把握，结果还是挂了，现把面经发上来。(和地里面其他的thumbtack面经差不多)

7月底的时候在mitbbs jobhunting版找到ala cat内推software engineer职位，很快就被HR联系安排OA。
OA题大家都一样： 时间不限。
设计时做到SET/UNSET/GET/NUMEQUALTO/BEGIN/COMMIT O(1)的时间复杂度就应该很容易过了。

接下来两个电面：（直接copy这个帖子的内容 ）
phone1:
nearestPalindrome,返回输入的最近的palindrome的数字
for example：
input 9 ouput 9
input 98 output 99
input 100 output 101

phone2:

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

在讲，小哥也没问啥问题。然后我说既然系统要求high availability，便指出了瓶颈在哪里，可以牺牲一下consistency（比如上传后别的用户不一定立马就能看到）。结论是需要cdn来缓存，小哥表示肯定，然后我把类似淘宝图片的缓存机制讲了一遍，说获取图片时最多一次hard drive IO read然后存入缓存，这样可以大大降低延迟。美国小哥一直在听，几乎没问啥问题。这一轮HR最后的反馈说面试官希望看到stronger signal。我后来想想当时他问了一两个问题貌似被我忽略了，没给我很好的评价很可能是因为交流不太好的原因（当时觉得有很多要讲，就在白板上写得很快，怕像第一轮那样没弄完）。

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

eko910817 发表于 2016-9-19 13:25
楼主。刚拿到thumbtack OA, 有点疑惑为什么它会把OA放到网上呢？是不是和hackerrank上的有出入？不一样呀？ ...

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

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

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. 
   
8. using namespace std;
   
9. 
   
10. /*
    
11. input: vector<string> keys, vector<vector<string>> docs
    
12. keys: a few key words to query
    
13. docs: a list of docs, each doc is a list of strings
    
14. return: highest ranking docs for query keys
    
15. tf_idf definition:
    
16. tf_idf=sum of each key's tf_idf
    
17. key's tf_idf=keyCount/maxCount * log(n/docCount)
    
18. */
    
19. 
    
20. vector<int> tf_idf(vector<string> & keys, vector<vector<string>> & docs) {
    
21.     int n=docs.size(); // total number of the docs
    
22.     vector<unordered_map<string, int>> keyCount(n); //each word's count in each doc
    
23.     vector<int> maxCount(n); //the most freq word's count in each doc
    
24. 
    
25.     for(int i=0; i<n; ++i) {
    
26.         for(auto & word:docs[i]) {
    
27.             ++keyCount[i][word];
    
28.             maxCount[i]=max(maxCount[i],keyCount[i][word]);
    
29.         }
    
30.     }
    
31. 
    
32.     unordered_map<string, int> docCount; //each word appears in how many docs
    
33.     for (int i=0; i<n; ++i) {
    
34.         for(string & key:keys) {
    
35.             if(keyCount[i].count(key)) ++docCount[key];
    
36.         }
    
37.     }
    
38. 
    
39.     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
    
40.     for (int i=0; i<n; ++i) {
    
41.         for(string & key:keys) {
    
42.             tfidf[i].first+=(keyCount[i][key]+0.0)/maxCount[i]*log((n+0.0)/docCount[key]);
    
43.         }
    
44.         tfidf[i].second=i;
    
45.     }
    
46.     sort(tfidf.begin(),tfidf.end(),greater<pair<double,int>>());
    
47.     int m=2; //output first 2 highest tf_idf doc's index
    
48.     vector<int> ret(m);
    
49.     for(int i=0; i<m; ++i) {
    
50.         ret[i]=tfidf[i].second;
    
51.     }
    
52.     return ret;
    
53. }
    
54. 
    
55. int main() {
    
56.     vector<string> keys={"dog","cat"};
    
57.     vector<vector<string>> docs={ //testing case, given by myself
    
58.         {"dog", "dog", "cat", "a", "big"}, // 2/2*log(4/2)+1/2*log(4/2)
    
59.         {"cat", "dog", "a", "big"}, // 1/1*log(4/2)+1/1*log(4/2)
    
60.         {"cow", "a", "the"},
    
61.         {"the", "a"}
    
62.     };
    
63.     vector<int> ret;
    
64.     ret=tf_idf(keys,docs);
    
65.     for(auto & r:ret) cout << r << endl; //output doc's index
    
66. }
    

复制代码

谢谢楼主分享，感觉这个OA好耗时间啊，网上能找到类似的代码吗？

一直没有找到 “O(1) space insert getMean getMedian for data stream [0, 1000)”的完整题目。
哪位大虾给个链接啊？
看到好像有人说贴过答案，但是没找到。
求链接：）

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.
   
4.     void addNum(int num) {
   
5.         int c=cnt; //previous cnt
   
6.         ++cnt;
   
7.         avg=(avg*c+num)/cnt;
   
8.         ++numbers[num];
   
9.     }
   
10. 
    
11.     float getAvg() {
    
12.         return avg;
    
13.     }
    
14. 
    
15.     // Returns the median of current data stream
    
16.     double findMedian() {
    
17.         int half=cnt/2+1;
    
18.         int c=0;
    
19.         if(cnt%2==1) {
    
20.             for(int i=0; i<N; ++i) {
    
21.                 c+=numbers[i];
    
22.                 if(c>=half) return i;
    
23.             }
    
24.         } else {
    
25.             int half1=half-1;
    
26.             int m1=-1;
    
27.             for(int i=0; i<N; ++i) {
    
28.                 c+=numbers[i];
    
29.                 if(c>=half1 && m1==-1) m1=i;
    
30.                 if(c>=half) return 0.5*(m1+i);
    
31.             }
    
32.         }
    
33.     }
    
34. 
    
35. private:
    
36.     int cnt=0;
    
37.     double avg=0;
    
38.     const int N=1000;
    
39.     vector<int> numbers=vector<int>(N);
    
40. };
    
41. 
    
42. int main() {
    
43.     MedianFinder mf;
    
44.     mf.addNum(1);
    
45.     cout << mf.findMedian() << endl;
    
46.     mf.addNum(100);
    
47.     cout << "avg: " << mf.getAvg() << endl;
    
48.     cout << mf.findMedian() << endl;
    
49.     mf.addNum(1000);
    
50.     cout << mf.findMedian() << endl;
    
51.     mf.addNum(500);
    
52.     cout << mf.findMedian() << endl;
    
53.     mf.addNum(30);
    
54.     cout << mf.findMedian() << endl;
    
55.     mf.addNum(0);
    
56.     cout << mf.findMedian() << endl;
    
57.     mf.addNum(2000);
    
58.     cout << "avg: " << mf.getAvg() << endl;
    
59.     cout << mf.findMedian() << endl;
    
60. }

复制代码

楼主。刚拿到thumbtack OA, 有点疑惑为什么它会把OA放到网上呢？是不是和hackerrank上的有出入？不一样呀？谢谢楼主。

私信请教楼主了。求回复

tf_idf coding这题到底是什么样子的。。。

想问下 tf_idf  这题到底是什么？谢谢了

tf_idf coding这题到底是什么样子的。。。+1...