yp onsite 51-60

P51 第三轮. Manager, 先说一下enter yelp.com会发生什么，说了整个过程以后他会挑了一些具体的细节继续问，例如get 之后返回什么之类的。 然后coding部分是toplogical 排序

我发现好像现在的弯曲公司，面试一般里面都会有一轮topological sort，然后另外一轮考一个trie的题。是弯曲标配么？

P52 第四轮. 美国小哥，先聊了一下project，然后就是coding，leetcode原题，Longest Substring Without Repeating Characters， follow up是如果一台机器的memory不够呢，再follow up就是如果用assii码表示呢

class Solution(object):
    def longesSustringNoRepeating(self, s):
        dic = {}
        start = 0
        res = ''
        for i in range(len(s)):
            if s[i] in dic and start<dic[s[i]]:
                start = dic[s[i]]+1
            res = s[start:i+1] if len(s[start:i+1])>len(res) else res
            dic[s[i]] = i
        return res

s = 'abcdeb'
so = Solution()
ans = so.longesSustringNoRepeating(s)
print(ans)

代码之前写过了，memory不够的话，我们可以切块来做。最差的情况是每一个char对应一个index，所以dict的size最多也就255。然后我们只用使用这个dict来更新longest就行了。

link 昨天面了y家的onsite，纠结了一下还是决定发个面经攒攒人品求保佑求保佑。

他家喜欢周五下午面试，中午有engineer的免费午餐和learning group然后下午一点四十五面试。午餐体验很好，感觉他家员工都好年轻，朝气蓬勃。 P53 一轮：主要聊一个分布式系统的project，问了下map和reduce分别做什么工作，算法的参数怎么选，还有一些behavior问题，coding是给n门课程，每个课程有k个timeslot，问能不能排出一个n门课都选的课程表，用dfs，中间出了个小bug，改对的，这面觉得一般。

这道题跟movie schedule一样的道理

class Solution(object):
    def movieSchedule(self, movies):

        res = []
        self.dfs(movies, 0, [], len(movies), res)
        schedule = [sorted(zip(i,range(len(movies)))) for i in res]
        return schedule

    def dfs(self, movies, i, path, l, res):

        if len(path)==l:
            res.append(path)
            return

        for m in movies[i]:
            if m not in path:
                self.dfs(movies, i+1, path+[m], l, res)

movies = [[14,15,16,17], [14,15,16], [14,15], [14,15,17]]
so = Solution()
ans = so.movieSchedule(movies)
print ans

P54 二轮：manager面 问网站慢什么原因，然后洋洋洒洒扯数据库，总之这轮聊天环节很不错，coding类似permutation，dfs，bug free但我觉得我的板书写得好乱，有一处中间箭头加进去一行那种。

P55 三轮：问了web development经验， 如何维护streaming data 的top k， coding是longest prefix of strings，bug free，写得也算干净，之后还剩十分钟，他说比我预期快一点，问了几个问题结束了。这轮聊天一般，前面体力有点费太多，有点累。

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs or not strs[0]:
            return ''

        if len(strs)==1:
            return strs[0]

        res = len(strs[0])
        for i in range(len(strs)-1):
            a, b = strs[i], strs[i+1]
            index = 0
            while index<min(res, len(a), len(b)):
                if a[index]!=b[index]:
                    break
                index += 1
            res = index
        return strs[0][:index]

P56 四轮：manager 问一个网站可能受到哪些安全攻击，对答算顺利，但后面他说的一个csrf attack确实没印象了。coding是encode decode 二叉树，他说有点complex，不一定做完，边做边讲思路就好。我做完了小超了两分钟，基本bug free吧，中间一个地方map.get(preorder[cur]) 写成了map.get(cur)，他应该也没有发现。说了句did a good job之类。

写过了

总之题都很简单，很幸运算是遇到三个原题，觉得按照我的水平都一次bug free且clean有点难度，在stressful的环境下有时确实容易短路。但是并不知道他家如何评判candidate，与我同面的都是名校的大神，而且感觉他家题都做好都难有offer，聊天的重要性又和coding不相上下且headcount还少，哎，只能说一切都是命。。。求点大米。

link backend 的职位，一共四轮：

P57 java 基本概念问题：garbage collection hashmap list 和 javascript 区别（我的第二语言） 数据库问题： Nosql 和 mysql 的选择 （从 resume project 延伸） 文化问题： 对 yelp 的功能提建议 why yelp why cs why sde

算法题： P58 load balancer
就是一个地址轮询，最多就是轮询前检查一下healthy不。具体情况具体讨论吧

class LoadBanlancer(object):
    def __init__(self, ips):
        self.ips = ips
        self.index = 0

    def getIP(self):
        if self.ips:
            ip = ips[self.index]
            self.index = (self.index+1)%len(self.ips)
            return ip


    def checkHealth(self, ip):
        pass

ips = ['1.0.0.1', '1.1.1.2', '1.0.0.2']
so = LoadBanlancer(ips)
a = so.getIP()
print(a)
a = so.getIP()
print(a)
a = so.getIP()
print(a)
a = so.getIP()
print(a)
a = so.getIP()
print(a)
a = so.getIP()
print(a)

P59 search matrix II 给你一串 string 里面一些小写字母可能原来是大写求所有可能解. https://leetcode.com/problems/search-a-2d-matrix/ 先偷个懒

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]:
            return False

        nums = [i for row in matrix for i in row]

        l, r = 0, len(nums)

        while l<r:
            mid = (l+r)//2
            if nums[mid]==target:
                return True
            elif nums[mid]<target:
                l = mid + 1
            else:
                r = mid
        return False


matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

so = Solution()
ans = so.searchMatrix(matrix, 50)
print(ans)

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]:
            return False


        l, r = 0, len(matrix)*len(matrix[0])

        while l<r:
            mid = (l+r)//2
            x, y =  mid//len(matrix[0]), mid%len(matrix[0])
            print(x, y, mid)
            if matrix[x][y]==target:
                return True
            elif matrix[x][y]<target:
                l = mid+1
            else:
                r = mid
        return False


matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

so = Solution()
ans = so.searchMatrix(matrix, 50)
print(ans)

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]:
            return False

        i, j = 0, len(matrix[0])-1

        while 0<=i<len(matrix) and 0<=j<len(matrix[0]):
            if matrix[i][j]==target:
                return True
            elif matrix[i][j]>target:
                j -= 1
            else:
                i += 1

        return False

matrix =[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
so = Solution()
ans = so.searchMatrix(matrix, )
print(ans)

P60 如何对ordered input stream 进行搜索（从搜索延伸开），不用写代码只讲四轮和画图~

不太懂这道题木的意思。如果是stream data的话，一个一个进来就直接check就行了啊。一片一片进来，那么就先检查首尾两个，看target是否在里面。在的话就binary search