脸书跪经

发一个11月的脸书面经回报地里，11月去的onsite

• Behavior问想做什么，为什么跳槽，之前都干了什么之类的，没有问比如你的弱点之类的tricky问题， 后来出了一道算法题，find pair for domino，题的意思是有一袋子的多米诺骨牌，每个牌上有两个数字，上下各一个，都在1-6之间，要找出有没有两个match的骨牌，match的定义是两组数加起来都是6，比如一个骨牌是（1,5），那么match的骨牌是（1,5）或者（5,1），总之相当弱智的一题，用哈希表解决，存的时候存个pair，找的时候找两下就行了。但是楼主用C++，pair没有自动的hash function，我也不知道咋写，我就说那就用个嵌套的hash table就好了，unordered_map<int, unordered_map<int, bool>>这样
• most frequent char in string，一个谷歌跳过来的美国人，感觉很有经验也很厉害，全程调戏我，这题就是给个string，找出最常出现的char，我就说建个vector<int>数组统计一下ASCII的字符
  您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  使用VIP即刻解锁阅读权限或查看其他获取积分的方式

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

给的是
class Narray {

    vector<int> dimensions;
    int getNum(vector<int> index);
}

让写的是
int getSum(Narray narray) {
}

clone graph就是lc原题了

最后hr反馈是design不太好，coding不错，表示认了，外国manager人也真好，觉得我不行还安慰我说希望我来，希望能有大神给解释一下design，还挺感兴趣的。第一次发帖，有点啰嗦，见谅。

leixiang5 发表于 2016-12-18 08:25
1. 骨牌是不是可以直接存2个int 组合起来的string..找的时候..直接reverse下..看看那个string在不在map里.
...

1.对哦，这样更简单些，赞
2.我写的是vector<int> count(256, 0), 然后scan string的时候是 for (char c: str), count[c]++这样，他说的意思是c作为数组的index应该是正的，所以应该是unsigned char c: str, 这个意思
优化的时候他一开始没说多机，我就没往那方面想，以为是算法上能有提升，后来越想越觉得没可能。mapreduce肯定可以，但是既然都是char，我觉得就分开机器算，最后汇总256个也差不多的感觉。
3. chord前阵子刚知道一点，dynamo我就不懂了，这个design讨论的很具体细节，数字是可以，他后来又问像 "A and B and C have messages for you."这类的翻译，这里的问题是A，B，C这三个名字也得翻译，而且不是提前存在table里面的，and这个词也得翻译，当然也可以存成%s %s %s，但是我又觉得比如说要是这类信息可以显示很多名字，1-10个这样的，这个信息就得存10遍感觉很浪费，因为后面“have messages for you”都是重复的，我就说就把信息分开存，不如存成and是个连词，然后“message for you”是后缀，最后再根据有几个名字翻译完再拼起来这样，但是这样好像有点麻烦，怎么拼也得programmer来管。其实我感觉讨论的氛围还可以，但可能没答道他想要的点子上吧。

zhangyanuuuuu 发表于 2016-12-18 09:13
1.对哦，这样更简单些，赞
2.我写的是vector count(256, 0), 然后scan string的时候是 for (char c: str ...

2. 哦哦哦哦哦....C++好像有这个问题..Java没有~
如果多机 or multi-thread..那就是O(N / # of threads or machines)...就会快很多了吧~
3. 哦哦哦...懂了..设计题真恶心...这样感觉有点像是NLP了...把单词分开..也不对...因为每个单词照翻译..拼凑在一起..有时候读不通的...
如果message for you这样...万一是多个message..又要一个messages for you...万一message是你发的..又要messages from you....每个都有pros and cons吧...如果是面Google的话..直接说用Google translate API翻译下。哈哈哈。。然后扔给user～哈哈哈哈

1. 骨牌是不是可以直接存2个int 组合起来的string..找的时候..直接reverse下..看看那个string在不在map里.
2. 楼主当时是用unsigned char来代表char?  为什么不直接用char呢?...第二题面试官的优化..是不是就是把input 分开好几段..用mapreduce啊?..感觉蛮像google以前的那种面试风格..
3. 感觉这轮是不是要讨论chord, dynamo 这些...楼主的本来设计有什么问题呀?多个数字..有多个%d不就好了吗?? 然后programmer要加信息的话..直接在hash table里insert下不就好了吗?

觉得设计题真的很难搞定

leixiang5 发表于 2016-12-18 09:42
2. 哦哦哦哦哦....C++好像有这个问题..Java没有~
如果多机 or multi-thread..那就是O(N / # of threads  ...

我当时也有点感觉跟语法分析什么的相关，完全没学过NLP。。。当时我还真说了用google translate，估计面试官怀恨在心了

设计没那么复杂。 就是一个多语言的Template，像这种系统提供的信息一般语句都不会很多。对每一种语言生成一个模板然后存在Cache里就行了，甚至就打包放在app里面也不会很大。

Gee, 都是地里没看过的题目， 楼主在职几年了？？

elvia 发表于 2017-1-19 05:42
Gee, 都是地里没看过的题目， 楼主在职几年了？？

一年半左右，不过是在做EE相关的，没做过软件工作

骨牌第一题为什么需要存两个数，或者存两个数合在一起的string啊？既然知道了是合法的骨牌，那只要存第一个就好啦啊。
比如(1,5), (2,4), (3,3)..
那么只要存下1，2，3就好啦。