Chapter 69 Oscar Health

贡献一个Oscar实习面经.一共两轮. 第一轮,美国小哥.自我介绍+介绍一个project.问了两个题目. 第一题,给了一个数组和一个数字k,返回这个数组中是否有一个长度为k的windows中存在duplicates. 第二题,给了一个string.返回top k words by frequency.问了heap的实现,以及各种操作的时间复杂度. 第二轮,印度小姐姐.直接做题. 一开始先定义了摩斯密码.给了一个string,要求返回共有几种方式可以translate这个摩斯密码.

第一轮,一个有亚洲血统的小哥,reverse a immutable linked list with a space complexity < O(n).楼主写了个space O(sqrt(n))的算法 (immtutable不能改呀,没说清楚的一点是reverse print 出来,不需要reverse)
第二轮,一个美国小姐姐,LC17,手机键盘输入数字,输出字母combination.backtracking

https://stackoverflow.com/questions/41542257/reverse-print-an-immutable-linked-list-with-less-than-on-space

其实这个是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;
}