yp onsite 31-40

P31 链接 问题是 edit distance的变形题。就是给 两个string (e.g. 'query', 'quray'），然后有三个打分 （类似与 edit distance 的 insert, replace, delete），但每个分数不同，然后叫你算出最小值。反正DP类问题，不难。

class Solution(object):
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """

        if len(s)==len(t):
            dif = 0
            for i in range(len(s)):
                if s[i]!=t[i]:
                    dif += 1
            return dif == 1
        elif abs(len(s)-len(t))==1:
            if len(s)>len(t):
                s, t = t, s
            i, j = 0, 0
            while i<len(s) and j<len(t):
                if s[i]==t[j]:
                    i += 1
                    j += 1
                else:
                    j+=1
            return i==len(s) and j==len(t)
        else:
            return False

so = Solution()
ans = so.isOneEditDistance('abc','aac')
print(ans)

我觉得这个也挺难的呀

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """

        dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]

        for i in range(len(word1)):
            dp[i+1][0] = i+1
        for j in range(len(word2)):
            dp[0][j+1] = j+1

        for i in range(len(word1)):
            for j in range(len(word2)):
                if word1[i] == word2[j]:
                    dp[i+1][j+1] = dp[i][j]
                else:
                    delete = dp[i][j+1] + 1
                    add = dp[i+1][j] + 1
                    replace = dp[i][j] + 1
                    dp[i+1][j+1] = min([delete, add, replace])

        return dp[-1][-1]

P32 给你1，2，3，4，5个business id, 这里面的business可能是duplicates, 如果是，把它们merge,然后每次只返回最小的那个id. e.g. 1,3,5都是重复的，如果输入3,5 都会返回1。然后他给你三个function 分别是， mark_business(id1,id2), represent(id)， compare(id1,id2)。不是的，可以用union find的方法，或者更好的话DFS with strong connectivity，这也是我后来发现的。

class Solution(object):
    def reduce(self, ids, n):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        dic = {}
        for i in range(n):
            dic[i]=i

        print(dic)

        for a,b in ids:
            i, j = self.find(dic, a), self.find(dic, b)
            if i<j:
                dic[j] = i
            else:
                dic[i] = j

        res = [dic[i] for i in range(n)]
        return list(set(res))

    def find(self, dic, i):
        while dic[i]!= dic[dic[i]]:
            dic[i]=dic[dic[i]]
        return dic[i]

ids = [[1,2], [2,3], [5,6]]
so = Solution()
ans = so.reduce(ids, 9)
print(ans)

P33 给一组integer数据, 和 target num, 返回这组数据 +，-，x, /能不能得到 target num，每个数用一次。

class Solution(object):
    def ifTarget(self, nums, target):
        return self.dfs(nums, '', target)

    def dfs(self, nums, path, target):

        if len(nums)==1:
            if nums[0]==target:
                print(path)
                return True
            else:
                False

        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                a, b = nums[i], nums[j]
                candidates = [a+b, a-b, a*b, b-a] + ([b/a] if a else [])  + ([a/b] if b else [])
                for c in candidates:
                    if self.dfs(nums[:i]+nums[i+1:j]+nums[j+1:] + [c], path + str(a) + str(b), target):
                        return True
        return False

nums = [1,2,3,4]
so = Solution()
ans = so.ifTarget(nums, 24)
print(ans)

P34 讲intern project，biggest challenge 是什么。 链接 问了database， index。 如何用几句话讲明白什么是index coding: maximal square

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """

        if not matrix or not matrix[0]:
            return 0

        dp = [[0]*len(matrix[0]) for _ in range(len(matrix))]

        for i in range(len(matrix)):
            dp[i][0] = matrix[i][0]
        for j in range(len(matrix[0])):
            dp[0][j] = matrix[0][j]

        res = 0
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if matrix[i][j]==1:
                    dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])+1
                    res = max(res, dp[i][j])

        return res**2

matrix =   [[1, 0, 1, 0, 0],
            [1, 0, 1, 1, 1],
            [1, 1, 1, 1, 1],
            [1, 0, 0, 1, 0]]


so = Solution()
ans = so.maximalSquare(matrix)
print(ans)

P35 大概讲讲实习经历。问了inverted index。 coding: Word Serach 2, word search 给个board 里面有字母，给个dictionary，search board里面上下左右走能不能找到这个词 做过了P13题 link

P36 聊简历，why yelp？ 为什么你适合这个职位？ 讲intern project，问garbage collection如何实现？ 问了database index 是什么？如果有一个query 非常慢，为什么？ 怎么找到原因。如何优化？如果是因为index的问题，解释为什么index影响query 速度。 coding: data stream return top k most frequent items (strings)

import heapq
class Solution(object):
    def __init__(self, k):
        self.q = []
        self.dic = {}
        self.k = k

    def add(self, num):

        if num not in self.dic:
            self.dic[num] = 1
        else:
            self.dic[num] += 1

        cnt = self.dic[num]
        if self.q and (cnt-1,num) in self.q:
            self.q.remove((cnt-1,num))
            self.q.append((cnt,num))
            heapq.heapify(self.q)
        else:
            if len(self.q)<self.k:
                heapq.heappush(self.q, (cnt, num))
            else:
                if cnt>self.q[0][0]:
                    heapq.heappop(self.q)
                    heapq.heappush(self.q, (cnt, num))
        return self.q

nums = [1,1,1,1,2,2,3,4,5,6,4,4,4,4,4,4]
so = Solution(3)
for i in nums:
    ans = so.add(i)
    print ans

P37 yelp有哪里需要improve？如何improve？需要收集什么数据？如何test 你的方法有效？ 如何检查fraud，安全漏洞，或者安全问题。 coding: 给一个字符串“aBc1D2”, 其中的大小写可能不对，bool is_valid(string s) 函数，找到正确唯一的valid的字符串。

这都是什么面经啊！完全没懂什么意思！

P38 link 这部分之后是代码，leetcode的LRU cache，让我主要实现插入的逻辑。我就是hashmap加linked list，然后问了一下优化，说记录链表的尾巴可以加速插入。

import collections
class LRUCache(object):
    def __init__(self, capa):
        self.dic = collections.OrderedDict()
        self.capa = capa

    def get(self, key):
        if key in self.dic:
            value = self.dic.pop(key)
            self.dic[key] = value
            return value

    def set(self, key, val):
        if key in self.dic:
            self.dic.pop(key)
        elif len(self.dic)==self.capa:
            self.dic.popitem(last=False)
        self.dic[key]=val


so = LRUCache(5)
so.set(1,1)
so.set(2,2)
so.set(3,3)
so.set(4,4)
so.set(5,5)
so.set(6,6)
so.set(7,7)
print so.dic

P39 然后是一个华人女性，主要问了我缓存机制。然后问了给了好多课表，然后有先修课要求修完先修才能修后面的，就是一个dependency graph，然后考的就是topological sort。用一个hashmap记录每门课的indegree，码完问了一下时间复杂度。说是O(n^2)，n是节点个数，这里不同的课程数。

import collections
class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """

        pre = collections.defaultdict(set)
        nex = collections.defaultdict(set)
        for a,b in prerequisites:
            nex[b].add(a)
            pre[a].add(b)

        print(pre)
        print(nex)

        s = [i for i in range(numCourses) if i not in pre]
        visted = []
        while s:
            tmp = s.pop()
            visted.append(tmp)
            if tmp in nex:
                children = nex[tmp]
                for c in children:
                    pre[c].remove(tmp)
                    if not pre[c]:
                        s.append(c)

        return visted if len(visted)==numCourses else []

numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
so = Solution()
ans = so.findOrder(numCourses, prerequisites)
print(ans)

P40 第三个是一个manager，白人小哥。大哥感觉不是很钻技术的，上来主要跟我讲我是一个manager，主要和人打交道，然后问了问偏behavioral的像是平常做过项目里那次最challenging啊，实习里做的项目我没用过你能给我讲明白么，让你再做一次实习项目你会如何改进。说完之后问了一个很简单的anagram的题，就是找一堆单词里哪两个是anagram。sort单词以后作为key然后hash就行了。

import collections
class Solution(object):
    def findAnagram(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """

        dic = {}

        for w in words:
            if tuple(sorted(w)) not in dic:
                dic[tuple(sorted(w))] = w
            else:
                return [w, dic[tuple(sorted(w))]]

        return []

words = ['abc', 'aaa', 'ccc', 'bca']
so = Solution()
ans = so.findAnagram(words)
print(ans)

P40 第四个是一个英国小哥，在公司十年了，感觉是tech lead，然后前面也是客套几句介绍公司，然后问了我一个网站如果相应速度很慢如何解决。上别的网课讲了如何提高网站性能，然后我就基本照着“当在地址栏里输入网址发生了什么”里面每一个步骤将可能发生的问题和相应的解决方案，说了很多，感觉他还很满意。然后问了我一个Word count的题目，要求求出一个单词stream里面最常出现的前十个，先说一个弱弱的把stream里单词变成键值对（key是单词value是出现次数）然后sort。问更好方法，说了用min heap，变成键值对后再放进堆里，堆深度一定时间变成线性的。 然后HR姐姐进来问了我是否有offer，然后问了细节。最让我开心的是她问了我有没有人可以做reference check，因为之前看到面经里表现不错要发offer的结束后都问了reference所以觉得应该还不错。送走之后等了两周HR打电话恭喜我拿到offer。

这道题写过，就不再写了。

import heapq
class Solution(object):
    def __init__(self, k):
        self.q = []
        self.dic = {}
        self.k = k

    def add(self, num):

        if num not in self.dic:
            self.dic[num] = 1
        else:
            self.dic[num] += 1

        cnt = self.dic[num]
        if self.q and (cnt-1,num) in self.q:
            self.q.remove((cnt-1,num))
            self.q.append((cnt,num))
            heapq.heapify(self.q)
        else:
            if len(self.q)<self.k:
                heapq.heappush(self.q, (cnt, num))
            else:
                if cnt>self.q[0][0]:
                    heapq.heappop(self.q)
                    heapq.heappush(self.q, (cnt, num))
        return self.q

nums = [1,1,1,1,2,2,3,4,5,6,4,4,4,4,4,4]
so = Solution(3)
for i in nums:
    ans = so.add(i)
    print ans