Pinterest onsite 跪经

上周四刚面完,面了四轮,还挺intense的。。。中间就上了一次厕所。。。第一轮一个白人小哥,先问了我research project,问了好久,然后最后十五分钟出了个小的算法题,我居然忘记是啥了。。。应该是不难,所以真没印象。。。第二轮国人,问了min window substring

第三轮国人,也问了个string的问题,一个很长的string T,只有(A-Z), 然后很多query(eg. ADD),然后问T中是否能够找出包含query的substring,中间可以隔着一些字母,比如ABCDED是一个合格的case。我给了个dict的算法,然后又问了优化
第四轮白人小哥,问了system design的问题,给定很多keywords,每个keyword都对应了很多documents id and frequencies(d1, f1) (d2, f2)…(dn, fn), d1~dn是in sorted order. 然后问该如何优化存储空间。这一题是开放式的,之前也没做过SD的问题,所以被问的有点懵。。。给了很多提示,最后讲出了一些idea来。自我感觉不太好。。。

能细说一下什么是优化存储空间吗?

请问system design那轮是schedule上写了system design吗?表示害怕突然冒出system design来毫无准备

1 Like

写的是system design (ML), 我以为会问ml相关的问题,没想到问到的是这么基础的data retriever的问题。。。一脸懵逼。。。

能问下楼主timeline么?

就是对每个关键词存documents id和frequency都需要很大空间嘛,问如何能够优化。比如因为documents id都是sorted,所以也许可以存一个共同的pre-fix, 然后再存不一样的,就像是000001 000011, 你可以存一份0000,然后只存末尾的那个01和11.

这位小姐姐,第三题方法是dict记录每个字母的位置维护成list,然后遍历短string进行二分查找不断找满足条件的最小index吗。

求问一下第三题是什麽思路啊? 我完全没有思路唉。。 感觉跟minimum window substring很像 但是好像又不一样。。 谢谢谢谢~

我的思路是,用字典储存每个字母的位置比如ABBA存成{A:[0,3], B:{1,2}}. 对于短的字符串BA。从头开始遍历。目前最小的index可以为0,那么对B的位置数组,二分查找0在[1,2] 的位置,选0,目前最小index变成1+1=2。对于A的位置数组[0,3] 找2,发现可以选3。 那么index数组【2,3】在原来的串里对应的subsequence就是短的串。

补充内容 (2018-11-9 04:14):
说错了,二分查找0在[1,2] 的位置,选1

写了个小代码,如果有错误希望大家指出。时间复杂度为O(m*log N). 双指针解法的时间复杂度为O(m+n)

import bisect
s = ''abfdbsfsdfsfbpouapupccb''
t = ''abccc''

def IsSubSequence(s, t):
    D = {}
    for i in xrange(len(s)):
        if s[i] not in D:
            D[s[i]] = []
        D[s[i]].append(i)
    print D
    R = []
    curidx = 0
    for c in t:
        if c not in D:
            return False, R
        pos = bisect.bisect_left(D[c], curidx)
        if pos == len(D[c]):
            return False, R
        curidx = D[c][pos]
        R.append(curidx)
        curidx += 1
    return True, R

print IsSubSequence(s, t)

请问是一周出的结果么?怎么通知的呀?