https://www.1point3acres.com/bbs/thread-841626-1-1.html

今天面完了狗家SWE-MLE，分享一下新鲜面经，求大米~ 时间线： 11月海投，12月中收到HR联系，提出waive phone 直接onsite。当时用holiday为借口将面试拖到了1月中。因为是MLE，所以是2轮coding，2轮ML，1轮BQ。ML我选的是traditional ML。1月20面了3轮，21面了2轮第一轮 coding：给list of N strings with same length M，return True if there exists at least a pair of strings with ONLY 1 different character. 比如 [abc, abd] 就满足要求。要求时间NM^2。做法是把每个单词去掉一个字母，存进hash，秒了第二轮coding：三道题……第一题是个easy，写了个loop + counter；第二题是LC 尔拔漆；第三题列出两个BST里一样的数，我先提出dfs两次+2 pointer，也迅速写了出来，面试官不满意，希望我用iterator……当时没明白他意思，就又写了个recursive的。结束想想他意思应该是转化为linked list 然后遍历，这样空间复杂度就是1了第三轮ML：给一些review，设计如何判断review是positive还是negative。(开始前还给了几个概率，让我用Bayes 公式手算一个东西, 略过细节。) classification +/- 我提出了LR，然后把word先预处理一下；面试官要求用python写一下fit function， word encoding，其中 LR部分可以直接调包。follow up是word encoding怎么改进，有什么问题，如何online model，有什么privacy issue。。。考官见我回答完还有13分钟，就又丢给我一个 detect spam email，让我high level的说一下，我就强调了一下precision metric是关键；然后问我要是有客户自己标了spam，training是否应该采纳进去。总之这一轮感觉更多考的是产品思维和模型设计…… 第四轮ML：15分钟go over了我的简历，问了一些如何online model，怎么采集feature，问了问RNN， LSTM，GRU；relu和sigmoid的优缺点；然后给了个design：会议图像怎么把人给抠出来。我提可以做个像素分类器，面试官满意，然后问我 output的probability怎么denoise，我想了想说可以用clustering, 然后果不其然他让我手写一下kmeans，followup是kmeans 怎么output概率，我说每个点算一下到center的距离，然后output个rat‍‌‍‍‍‌‍‌‍‌‍‍‍‌‍‍‌io BQ略过总体感觉还挺顺利，基本所有问题都回答上了，面试官也都非常nice。楼主2年蕉厂RS，math phd背景。刷题刷了2遍前200 +分题型刷+乱七八糟400多道，这次准备了半年左右。求offer，求TM顺利~ 补充内容 (2022-01-28 09:31 +8:00): 1/27 hc通过，开始team match 补充内容 (2022-02-08 09:47 +8:00): 1/28 和A1 demographic聊了，给utube等平台用户做画像，推/筛广告，决定去 2/2 HR通知TM成功 2/7 拿到offer

online model意思是如何把你offline的model变成online的，我说比如用sgd啥的min loss，把loss和weight都存起来，每当有一些新的数据进来，存一下batch，然后继续min； denoise的意思是：每个像素点一开始都output了一个概率，相邻很近的两个点可能一个是0.1，一个是0.9，但他们俩在图片上距离很近，且RGB值差不多，那我们就可以把他们cluster到一起，然后assign相同的概率；面试官没有问细节，我提了这个思路他就满意了，然后就让我implement clustering算法（Kmeans）

我说“this is an interesting question” hhh；我举了个栗子，比如google登录时会给用户发安全提醒，我说我自己可能收到这种邮件都不想看，可能点成spam，但这种邮件对所有人都很重要，不能因为少数人点了spam就被归到spam；所以我建议还是不放进training，以防造成不必要的bias，毕竟spam detection关键是precision；然后我问面试官他的看法，他说这是个产品问题，open question，觉得我说的挺好的

找人内推了狗家跳过店面直接5轮VO，面的L4

给一个log文件，有开始时间到结束时间，问任意时刻有多少个log在处理中一开始想到的是线段树，但是好久没用线段树把自己绕进去了，后来面试小哥使劲往回拉，才想排序后用优先队列遍历，然后输出一个数组，最后没时间follow up
给一个二叉树，二叉树要么是internal node要么是leaf node，只有leaf有string value。要求定义一个数据结构 a) 输出第i个字符 b) 输出[i, j)的字符串 a写完了，b写的磕磕绊绊最后dry run没跑完时间到了
nim博弈，有很多堆卡片，每堆卡片有颜色，每一轮可以move一堆到另一堆上，但必须堆顶颜色或者数量相同用dfs解决了，一开始代码有点跑偏导致面试官闭麦关摄像头了（不确定是否有其他事情）。最后快写完了，又加上了memory和compress，小哥说correct。没follow up也没时间
给一个二叉树， a) 要求每次删除一个leaf node，并且返回删除的顺序 b) 每次只能先删除所有的leaf，然后下一轮才能删除成为leaf的internal 这轮是最气的，面试官是国女，但是语气很凶，并且表现的极不耐烦。面试中一直手撑着头歪着脑袋，时不时滑滑手机。本来我以为我的口语就很差了，此女口语比我还差。当我尝试clarify的时候她一直凶我。面完了就找HR投诉了，HR说会调查 a很快就写完了，b卡了‍‌‍‍‍‌‍‌‍‌‍‍‍‌‍‍‌半天，给了提示用队列和记录parent。时间到之前写完了，没follow up
BQ轮没什么好说的，和面试官谈笑风生。面试官说自己从毕业就在狗家干了10年，牛逼…

https://www.1point3acres.com/bbs/thread-847499-1-1.html

coding. 1~n n个数和一个prime p，求n个数中除去所有的p的multiplers的剩下的数之和。脱口而出暴力解，被要求优化；然后用了求和公式，不知道这样算不算过；follow-up: 求有两个prime number的情况下的和. 需要考虑两个prime的倍数有相同的情况。也是先暴力解，然后优化

def brute_force(n, ps):
    total = 0
    for i in range(1, n + 1):
        for p in ps:
        	if i % p == 0: break
        else:
        	total += i
    return total

def f(n, p):
    total = n * (n + 1) // 2
    m = n // p
    total -= (m + 1) * m // 2 * p
    return total

assert brute_force(2000, [5]) == f(2000, 5)
assert brute_force(3000, [7]) == f(3000, 7)
assert brute_force(5000, [11]) == f(5000, 11)

def h(n, p):
    m = n // p
    total = (m + 1) * m // 2 * p
    return total

def f2(n, p1, p2):
    total = n * (n + 1) // 2
    total -= h(n, p1)
    total -= h(n, p2)
    total += h(n, p1 * p2)
    return total

assert brute_force(2000, [5, 7]) == f2(2000, 5, 7)
assert brute_force(3000, [7, 3]) == f2(3000, 7, 3)
assert brute_force(5000, [11, 13]) == f2(5000, 11, 13)

一个relation list，每个entry代表两个id的关系 friend or enemy 类似 [0, 1, “F”]的结构；一个relation chain，比如 “FEF” ； start: id1； end: id2 output: 需要求从id1开始，根据relation chain的关系，能否得到一个list的id符合chain的关系且最后一个id是id2. 求这个list。 i.e. “FEF”，先找到id1的friend idx，然后找idx的enemy idy, 最后找idy的friend idz, 如果idz == id2, 那么找到一个解，返回这个解。花了很多时间clarify, 用了DFS做，但最后脑子一热 time complexity说错了。。。

BFS? since given fixed chain length.
有很多记录RPC的streaming log [id, timestamp, action]. action ‍‌‍‍‍‌‍‌‍‌‍‍‍‌‍‍‌is start/end. 还有一个timeout。在一个log analyzer class里面设计一个 violate function 找出是否有violate timeout的log，如果有返回true，没有返回false ，每个function call只处理一个log。一开始用hashmap存，每次处理log时，check hashmap里面的entry，如果violate 或者 end，remove entry。但是如果很多RPC都没有end，hashmap会越来越大，不行；后来想了queue和hashset，还是有问题，最后发现面试官要的是linkedlist，但是删除已经end的log还是需要O(n)，最后时间来不及了，这个问题一直没想清楚，求大神指点

LRU cache, implemented with doubly linked list and hashmap?

https://www.1point3acres.com/bbs/thread-847482-1-1.html

752. Open the Lock BFS
3
第一题 find # of target value in sorted duplicated list 34. Find First and Last Position of Element in Sorted Array

问的给两个string，问第二个是否是比第一个刚好多一个元素（无顺序要求），followup是给两个string list，问第二个list里面所有与第一个list里任意一个string刚好多一个元素的string，原题写出了O(N)， followup一开始没有思路，面试官当时给的提示是让优化原题解法，但后来说他的思路的时候也没有优化原题（无语），反而是用了precompute all situation（1st list) + set检查2nd list，不过楼主觉得python set里面比较两个dictionary还是O（N）所以感觉并没有比暴力解优化，大佬麻烦解释一下

Rabin Karp hash on all varients of char counts?

1554. Strings Differ by One Character ??

第三轮给一个多叉树的编码器，写一个解码器，要求给定一个encoded string，输出decoded string。当天的第一轮写码，不太在状态，有点磕磕盼盼，写出来了个O(NlogN）

428. Serialize and Deserialize N-ary Tree

第四轮给了directory下面所有的文件路径，要求对于每个directory必须先删除完所有文件才能删除directory，给定一个directory和里面子文件所有的路径，返回删除里面所有文件的路径的顺序，Time O(NlogN), Space O(N)

第五轮是个老员工，听说是转码选手大放水直接问了二叉树的遍历，从leaf node到root先遍历所有leaf node然后往上走，要求一种删除node的解法和另外一种不删除node，然后考察了一下遍历的种类（postorder之类的）