sc onsite 31-40

P31 给两个节点，判断两个人是不是6度之内的朋友并且返回中间有多少人，之前面经看到，没写，真是后悔啊。一开始给了用queue和set的bfs解法，他说空间复杂度太高了，后来说用dfs，他说空间还是高，毕竟要用set存访问过的节点，我实在想不出来了，要了提示，可是感觉提示也并不是那么明显，我说能不能从两个点分别开始搜？他说你觉得这对复杂度有优化吗？我就觉得这估计也没戏。折腾了半天，好像也就剩20多分钟了，他说你先写一个你的解法，有时间我们再优化。写了那个bfs的，写完他让给test case，我忘了a和b是同一个人以及a和b中间人数多于6个的情况了，他提醒了一下加上了一两句判断。写好之后他看了觉得应该没bug了，让我问问题了，我还在纠结优化，他说10min估计不够了，优化是optional的(估计是安慰我的)，然后让我问问题了。白人小哥是搞discovery的，我提了一个使用不是很顺的情况，他也说有蛮多人有抱怨的。中国小哥还给我讲了一些隐藏功能，他说他们也在想办法弄用户手册之类的，不然真的蛮难上手的

import collections
class Solution(object):
    def friend6(self, relations, a, b):
        dic = collections.defaultdict(set)
        for s,e in relations:
            dic[s].add(e)
            dic[s].add(e)

        visited = set([a])
        q = [(a, 0, [])]

        while q:
            p, d, path = q.pop(0)
            if d>6: return
            if p==b: return path+[p]
            for c in dic[p]:
                if c not in visited:
                    visited.add(c)
                    q.append((c, d+1, path+[p]))

        return

relations = [[1,2], [2,3], [3,4],[4,5]]
so = Solution()
ans = so.friend6(relations, 1, 5)
print ans

不知道优化空间是不是这个意思。

import collections
class Solution(object):
    def friend6(self, relations, a, b):
        dic = collections.defaultdict(set)
        for s,e in relations:
            dic[s].add(e)
            dic[s].add(e)

        visited = set([a])
        q = [(a, 0)]
        indegree = {}

        while q:
            p, d = q.pop(0)
            if d>6: return
            if p==b: break
            for c in dic[p]:
                if c not in visited:
                    visited.add(c)
                    indegree[c] = p
                    q.append((c, d+1))
        path = []
        while b!=a:
            path = [b] + path
            b = indegree[b]
        if b==a:
            path = [a] + path
        return path



relations = [[1,2], [2,3], [3,4],[4,5]]
so = Solution()
ans = so.friend6(relations, 1, 5)
print ans

P32 第四轮是个国人姐姐。问了问project，她好像也做过类似的，所以稍微多问了一点点。题目挺简单的，merge two sorted list， follow up是merge k sorted list，写完test case跑过了，问了问复杂度。她看还有好久再写一个吧，给inorder和postorder建树，我用recursion做，结果最后在子数组边界的地方加一减一的地方老是有问题，然后让她说没事，我相信你很快就能调好的，思路是对的，不用纠结了。

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(None)
        head = dummy

        while l1 and l2:
          if l1.val<l2.val:
            dummy.next = l1
            dummy = dummy.next
            l1 = l1.next
          else:
            dummy.next = l2
            dummy = dummy.next
            l2 = l2.next

        dummy.next = l1 or l2

        return head.next

已经不知道写过多少遍了。

import heapq
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        dummy = ListNode(None)
        head = dummy

        q = [(n.val, n) for n in lists if n]
        heapq.heapify(q)

        while q:
            val, node = heapq.heappop(q)
            dummy.next = node
            dummy = dummy.next
            if dummy.next:
                heapq.heappush(q, (dummy.next.val, dummy.next))

        return head.next

P33 给一个nn的chess board，knight可以跳2\3的格子的对角线，就是国际象棋的规则。求给出一个起始点，knight能否跳到给定的重点。BFS搞定。followup print出来路径，backtrace就可以了，把每个格子上个格子的方位存下来，允许使用额外空间。写完后跑了test，小哥说：you did a good job

没太懂瞎写了一个。

class Solution(object):
    def knightMove(self, n, start):

        board = [[False]*n for _ in range(n)]

        q = [(start,[start])]

        while q:
            cur = q.pop(0)
            tmp, path = cur[0], cur[1]

            for dp in [(1,2), (-1,2), (1,-2), (-1,-2), (2,1), (2,-1), (-2,1),(-2,-1)]:
                i, j = tmp[0]+dp[0], tmp[1]+dp[1]
                if (i,j) == start: return path+[(i,j)]
                if 0<=i<n and 0<=j<n and not board[i][j]:
                    board[i][j] = True
                    q.append(((i,j), path+[(i,j)]))

so = Solution()
ans = so.knightMove(4, (0,0))

print ans

P34 给一个数组，A,B轮流从头尾处选出一个数字，求当B使用（1）贪心和（2）最优策略时，A能取到所有数字之和最大。我使用的recursive写的，优化用的是hash 存储从子数组（i, j）上能得到的最优解。写了几个test跑过了。

这道题跟我收录的dp的里面很像

B使用贪心的时候 A的解法。

class Solution(object):
    def maxCoin(self, nums):

        self.memo = {}
        res = self.helper(0, len(nums)-1, nums)
        print self.memo
        return res

    def helper(self, i, j, nums):

        if j-i<2:
            return max(nums[i:j+1])

        if (i, j) not in self.memo:
            l = nums[i]
            if nums[i+1]>nums[j]:
                l += self.helper(i+2,j,nums)
            else:
                l += self.helper(i+1,j-1,nums)
            r = nums[j]
            if nums[i]>nums[j-1]:
                r += self.helper(i+1,j-1,nums)
            else:
                r += self.helper(i, j-2, nums)
            self.memo[(i,j)] = max(l,r)
        return self.memo[(i,j)]

nums = [1,2,5,3]
so = Solution()
ans = so.maxCoin(nums)
print ans

B使用最优的时候的A的解法。

class Solution(object):
    def maxCoin(self, nums):

        self.memo = {}
        res = self.helper(0, len(nums)-1, nums)
        print self.memo
        return res

    def helper(self, i, j, nums):

        if j-i<2:
            return max(nums[i:j+1])

        if (i, j) not in self.memo:
            p2 = min(self.helper(i+1,j,nums), self.helper(i,j-1, nums))
            self.memo[(i,j)] = sum(nums[i:j+1]) - p2
        return self.memo[(i,j)]

nums = [1,9,1,3]
so = Solution()
ans = so.maxCoin(nums)
print ans

P35 第二轮，韩国大叔，Leetcode的symmetric tree。这题我一开始上来用了最精简的方法，然后似乎大叔不太能follow，要我从最简单的BFS做一遍，然后又从DFS做一遍。现在回过头来总结，其实面试的时候不要一开始给出最优解，给出一个相对naive但是直观的解，然后逐步改进，这样可以向面试官展现你的thinking process，一上来就最优的，很多面试官都不是很喜欢的。

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return self.helper(root.left, root.right)

    def helper(self, l, r):
        if not l and not r: return True
        if not l or not r: return False
        if l.val!=r.val: return False

        return self.helper(l.left, r.right) and self.helper(l.right, r.left)

老天爷啊，求面试给我一道这种题目吧！！一道就行！！

就到这里了吧。不写了。考到没做过的。就看命咯。

祝看到这里的同学都能有个好前程，

哎呀，还是再写一个word break吧，有点不放心。

先来一个暴力的哈

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        if not s:
            return []

        res = []
        self.dfs(s, wordDict, '', res)
        return res

    def dfs(self, s, wordDict, path, res):
        if not s:
            res.append(path)

        for w in wordDict:
            if s[:len(w)] == w:
                self.dfs(s[len(w):], wordDict, path+(' ' if path else '')+w, res)

s = "catsanddog"
dict = ["cat", "cats", "and", "sand", "dog"]
so = Solution()
a = so.wordBreak(s, dict)
print a

然后在用memo优化

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        if not s:
            return []

        self.memo = {}
        return self.dfs(0, len(s), s, wordDict)

    def dfs(self, i, j, s, wordDict):

        if (i,j) not in self.memo:
            path = []
            if s[i:j] in wordDict:
                path += [s[i:j]]

            for w in wordDict:
                if len(w)<=j-i and s[i:i+len(w)]==w:
                    res = self.dfs(i+len(w), j, s, wordDict)
                    path += [w+' '+p for p in res]
            self.memo[(i,j)] = path
        return self.memo[(i,j)]


s = "catsanddog"
dict = ["cat", "cats", "and", "sand", "dog"]
so = Solution()
a = so.wordBreak(s, dict)
print a

酱油版的Dijkstra再写一遍吧。

class Solution(object):
    def dijkstra(self, graph, start, end):
        Q = {}
        P = {}
        D = {}

        Q[start] = 0

        while Q:
            k = self.findMin(Q)
            D[k] = Q[k]
            children = graph[k]
            for c in children:
                dis = D[k]+children[c]
                if c in D:
                    if dis<D[c]:
                        return
                elif c not in Q or dis<Q[c]:
                    Q[c] = dis
                    P[c] = k
            del Q[k]

        print P
        path, res = [], D[end]
        while end in P:
            path = [end] + path
            end = P[end]
        path = [end] + path

        return path,res

    def findMin(self, Q):
        m = (None, float('inf'))
        for k in Q:
            if Q[k]<m[1]:
                m = (k, Q[k])
        return m[0]


# example, CLR p.528
G = {'s': {'u':10, 'x':5},
    'u': {'v':1, 'x':2},
    'v': {'y':4},
    'x':{'u':3,'v':9,'y':2},
    'y':{'s':7,'v':6}}

so = Solution()
print so.dijkstra(G, 's', 'v')

再写个topo sort吧

import collections
class Solution(object):
    def toposort(self, graph):
        """
        :type graph: dict[int:List[int]]
        :rtype: List[int]
        """
        indegree = collections.defaultdict(set)
        outdegree = collections.defaultdict(set)
        for k in graph:
            for c in graph[k]:
                outdegree[k].add(c)
                indegree[c].add(k)



        s = [k for k in outdegree if k not in indegree]
        res = s[:]
        while s:
            tmp = s.pop()
            if tmp in outdegree:
                children = outdegree[tmp]
                for c in children:
                    indegree[c].remove(tmp)
                    if not indegree[c]:
                        s.append(c)
                        res.append(c)

        node = set(outdegree.keys()+indegree.keys())
        return res if len(res)==len(node) else []



graph = {1:[2,3,4,5],
        2:[3,4],
        3:[5]}
so = Solution()
a = so.toposort(graph)
print a

class Solution(object):
    def toposort(self, graph):
        """
        :type graph: dict[int:List[int]]
        :rtype: List[int]
        """
        children = []
        for k in graph:
            children += graph[k]
        s = [k for k in graph if k not in set(children)]

        res = []
        while s:
            while s[-1] in graph and graph[s[-1]]:
                c = graph[s[-1]].pop()
                if c in s:  # find circle
                    return []
                if c not in res:  # have visited node
                    s.append(c)
            res.append(s.pop())

        print res[::-1]

不管了，不管了。拿不到奥佛就算了！