Chapter 69 Oscar Health
贡献一个Oscar实习面经.一共两轮. 第一轮,美国小哥.自我介绍+介绍一个project.问了两个题目. 第一题,给了一个数组和一个数字k,返回这个数组中是否有一个长度为k的windows中存在duplicates. 第二题,给了一个string.返回top k words by frequency.问了heap的实现,以及各种操作的时间复杂度. 第二轮,印度小姐姐.直接做题. 一开始先定义了摩斯密码.给了一个string,要求返回共有几种方式可以translate这个摩斯密码.
s="12123j12l3412kj3412k3h412k"
k=3
m={}
for i in range(len(s)):
if m.has_key(s[i]) and i-m[s[i]]+1<=k:
print s[i], i
m[s[i]]=i第一轮,一个有亚洲血统的小哥,reverse a immutable linked list with a space complexity < O(n).楼主写了个space O(sqrt(n))的算法 (immtutable不能改呀,没说清楚的一点是reverse print 出来,不需要reverse)
第二轮,一个美国小姐姐,LC17,手机键盘输入数字,输出字母combination.backtracking
#include <henry.h>
struct node{
int v;
node* n;
node(int x, node* n_=0):v(x),n(n_){}
};
node* init(int num=100){
node* n=new node(0);
node* c=n;
for(int i=1;i<num;i++)
c->n=new node(i), c=c->n;
return n;
}
void post_traverse(node* h, node* t){ // postorder traversal
if(h==t){ cout << t->v << endl; return; }
post_traverse(h->n,t);
cout << h->v << endl;
}
void print_reverse(node* R){ // T: O(3*N), S:O(N^0.5)
int n=0;
node* c=R;
while(c->n) n++, c=c->n; // T: O(N)
auto tail=c;
int m=sqrt(n+1);
stack<node*> stk; //S: O(N^0.5)
stk.push(R);
c=R, n=0;
while(c){ // T: O(N)
if (++n%m==0) stk.push(c);
c=c->n;
}
if(stk.top()!=tail) stk.push(tail); // make sure to add tail
while(!stk.empty()){ // T: O(N^0.5)
auto t=stk.top(); stk.pop();
if(stk.empty()){
cout << t->v <<endl;
break;
}
auto h=stk.top()->n;
post_traverse(h,t); // T: O(N^0.5)
}
}
int main(){
print_reverse(init());
return 0;
}其实这个是2月16号面的.之前做了一道oa,题目是给你一个int array和一个int d,让你求这个array里值相差d的数有几对.
过了之后很快就联系了店面.店面我的人是个cmu的小哥,在amazon Google呆过,面试过程感觉语气很平淡,不怎么热情.
上来先问project,
然后上题,其实就是valid parentheses那道题,开始是最简单版本,只有’(‘和’)‘,没有其他字符,然后开始问followup,如果中间有其他字符怎么办?然后问我如果有很多对不同种类的括号,怎么做?你怎么存这些括号对?任意不同字母都可以组成括号对,比如’a’ ’b’也可以组成括号对.
http://sde.quant365.com/facebook-2016-interview-questions-part-1.html#remove-invalid-parentheses
http://sde.quant365.com/facebook-2016-interview-questions-part-1.html#valid-parentheses
一面是个韩国小哥,去年在Oscar实习.小哥人很好.一面楼主真的是稀里糊涂代码写得很糟糕.题目是两个两个数组 eg. ab和ac 判断第三个数组是不是这两个数组的combination,combination的要求就是是前两个数组的合成,保持各个character在原来String中的相对顺序.ab和ac的combination可以是 aabc abac acab等等.当时的做法比较brute force DFS算出前两个数组的全部组合,判断第三个数组是不是在其中.代码写得很糟糕,刚开始思路想错了,已经用BFS也可以,最后2分钟改成DFS,幸运的是改完之后bug free.面完以为肯定挂了,没想到几个小时后HR说约二面了,感谢韩国小哥不杀之恩.其实这题目DP也可以解.感觉面试太紧张了,只想到Brute force. 二面是个美国小哥,人感觉非常开心,经常会笑.题目也不难,里扣市其的变式,由于之前做过这题,就直接秒了,给了DFS的基础算法,问了时间复杂度,是指数的时间复杂度.Follow up如果我给了你一个dict里面有一些String,小哥说要求还是character 的combination但是要求在dict里面,能不能时间复杂度要好一些.小哥问我有什么data structure可以来优化吗?楼主刚开始脑子一懵,我说trie树吧. 感觉小哥不是特别熟悉trie树,然后问我具体讲讲,我就把trie树的结构给他讲了一遍,小哥说这是很多人最直接的想法,但是感觉好像并不能提高时间复杂度. 楼主一脸懵,没时间多想,感觉实现个trie树也挺麻烦的,他说不能就不能吧.赶紧换个思路,后来就想到很简单的想法就是把dict里面每个String映射成num,跟输入的num比较,小哥一直纠结于要用什么data structre.. 我是真的想不出需要用什么额外的data structure 我就说那需要一个Map来映射吧.又解释了一通,不知道最后小哥理解不理解我的意思.最后小哥问了我HashMap look up的时间复杂度.我想单纯回答个O（1)也不是很妥当,我就说O(length of String).小哥好像也挺开心的.小哥人很好,全程Cool Cool到底,搞得我很尴尬.
http://sde.quant365.com/dynamic-programming.html#interleaving-string
http://sde.quant365.com/bit.html#binary-trie
http://sde.quant365.com/trie-and-suffix-tree.html
http://sde.quant365.com/combinatorics.html#letter-combinations-of-a-phone-number
第一轮:尬聊 介绍产品 第二轮:reverse linkedlist没让写代码 先让列出所有可能的方法 比较时间复杂度空间复杂度 然后是说如果linkedlist非常大 具体不讲了面试时候正常发挥就行 (涉及到了互斥锁和内存不够问题 让写代码解决问题)
第三轮:买股票1,2,3 只写了1和2的代码
第四轮:interleaving string 只写了dp算法 先讲了dfs的解法
http://sde.quant365.com/linked-list.html#reverse-linked-list
http://sde.quant365.com/bloomberg-2016.html#best-time-to-buy-and-sell-stock-1
69.1 Morse Codec
地里面经不是非常多,但对公司的评价都挺好哒.感觉是很有意思的独角兽公司. 昂赛: 一.介绍产品 聊天 demo给你看 你问问题 二.白板 小姐姐问我了 摩尔斯码与字符转换 相互转换都写 比如 点点点 可能对应[S, EI, IE, EEE] 要求返回所有可能的组合 三.白板roman to integer 四.白板huffman code转换huffman code就是不会存在一个为另一个的prefix嘛 比如 a - 0, e - 100, b -101, d - 1101 给你一串数字 convert to 字符串 五. head of tech recruiter来聊聊天而已 真闲聊 消息一般两三个工作日就会出来～ 公司在puck building的6楼 完全开放式 感觉人来人往很年轻有活力 并且节奏很快
http://sde.quant365.com/linkedin-before-2015.html#roman-to-integer
// g++ MorseCodec.cpp -g -o MorseCodec && ./MorseCodec
#include <henry.h>
#define USE_UPPERCASE_MORSE
#if defined(USE_UPPERCASE_MORSE)
#define CASE(x) toupper(x)
#else
#define CASE(x) tolower(x)
#endif
class codec{
unordered_map<char, string> charMap;
unordered_map<string, char> morseMap;
public:
codec() {
charMap[CASE('a')] = ".-";
charMap[CASE('b')] = "-...";
charMap[CASE('c')] = "-.-.";
charMap[CASE('d')] = "-..";
charMap[CASE('e')] = ".";
charMap[CASE('f')] = "..-.";
charMap[CASE('g')] = "--.";
charMap[CASE('h')] = "....";
charMap[CASE('i')] = "..";
charMap[CASE('j')] = ".---";
charMap[CASE('k')] = "-.-";
charMap[CASE('l')] = ".-..";
charMap[CASE('m')] = "--";
charMap[CASE('n')] = "-.";
charMap[CASE('o')] = "---";
charMap[CASE('p')] = ".--.";
charMap[CASE('q')] = "--.-";
charMap[CASE('r')] = ".-.";
charMap[CASE('s')] = "...";
charMap[CASE('t')] = "-";
charMap[CASE('u')] = "..-";
charMap[CASE('v')] = "...-";
charMap[CASE('w')] = ".--";
charMap[CASE('x')] = "-..-";
charMap[CASE('y')] = "-.--";
charMap[CASE('z')] = "--..";
for (auto& e:charMap) morseMap[e.second]=e.first;
}
string to_morse(const string& s){
string r;
for(char c: s) r.append(charMap[c]);
return r;
}
//find all possible strings
vector<string> to_string(const string& morse){
static unordered_map<string,vector<string>> cache;////
vector<string> r;
if(morse.empty()) return r;
if(cache.count(morse)) return cache[morse];
string t;
for(int i=0;i<morse.size();++i){
t+=morse[i];
if(t.size()>4) break;
if(morseMap.count(t)){
if(i+1==morse.size()){ // cherry pick - BUG
r.push_back(string(1,morseMap[t]));
}else{
auto x=to_string(morse.substr(i+1));
for(string& y: x){
r.push_back(morseMap[t]+y);
}
}
}
}
return cache[morse]=r;
}
int decode_way(const string& morse, int h=0){
if(h==morse.size()) return 1; // 0 or 1
int r=0, i=0;
for(auto& pr: morseMap){
if((i=morse.find(pr.first,h))==h)
r+=decode_way(morse,i+pr.first.size());
}
return r;
}
// https://uva.onlinejudge.org/external/11/1113.pdf
int decode_way(const string& morse, vector<string>& vs){
int r=0;
vector<string> ms;
for(auto& s: vs)
ms.push_back(to_morse(s));
return dfs(morse,ms,0);
}
void test(){
string s=".---.--.-.-.-.---...-.---.";
codec coder;
vector<string> vs={"AT","TACK","TICK","ATTACK","DAWN","DUSK"};
assert(coder.decode_way(s, vs) == 2);
}
private:
unordered_map<string,unordered_map<int,int>> um; // string->starting pos->decode way
int dfs(const string& mr, vector<string>& ms, int h){
if(um.count(mr) and um[mr].count(h)) return um[mr][h];
if(h==mr.size()) return 1;
int sum=0;
for(string& m: ms){ // O(M) - number of strings
int i=mr.find(m, h); // startswith
if(i==h) sum+=dfs(mr,ms,i+m.size());
}
return um[mr][h]=sum;
}
};
int uva_oj(){
int n,m;
cin>>n;
while(n--){
codec coder;
string s;
cin>>s;
cin>>m;
vector<string> vs(m);
for(int i=0;i<m;++i) cin>>vs[i];
cout << coder.decode_way(s, vs) << endl;
if(n) cout << endl;
}
return 0;
}
int main(){
codec cc;
cc.test();
string dog=cc.to_morse("DOG");
auto r=cc.to_string(dog);
assert(r.size() == cc.decode_way(dog));
r=cc.to_string("...");
assert(r.size() == cc.decode_way("..."));
return 0;
}