Onsite 面经

Onsite 1. 跪 2017-10-19

1 第一轮：老白，简单问了一下简历后design，要求是设计一个app让人在搭uber车的时候玩游戏，具体什么游戏无所谓。我跟他交流一下后，同意相当于在uber app里面再调一个app玩游戏，但是可以access uber app里面的用户信息什么的，挑了设计中国象棋（其实其他游戏也行，无所谓），从澄清use case开始，估算QPS和数据量什么的，再扯到后端的cache/DB这些。老白还算nice，中间问问题不是特别尖锐，自我感觉还行。

这道题目没发准备啊，我能怎么答。那就我准备针对uber pool出一个你画我猜得游戏了。

2 第二轮：老白，hiring manager，就是问简历上的东西还有一些behavior什么的，最后问了些team的情况和uber的culture这类问题。

hmmm, 仍然属于没法准备。

3 第三轮：年轻三哥，先问了怎么设计load balancer，讲了一些主要的算法，20分钟左右。然后问知不知道cache，都有些什么cache，主要讲了LRU/LFU，以为要让写LRU，结果让写LFU，白板写的。关键剩的时间不多了，跟他讲了用的hash table + double-ended linked list，分析清楚了怎么work，最后只写了1个半的function，这里怀疑可能会被黑，尼玛让写LFU不早点弄，非要扯掉一大半的时间才开始写code

好的今晚学习了一下load balancing。

然后我们来写一下LRU cache吧。

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.dic = {}
        self.array = []
        self.capacity = capacity


    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.dic:
            self.array.remove(key)
            self.array.insert(0, key)
            return self.dic[key]
        else:
            return -1


    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """

        if key in self.dic:
            self.array.remove(key)
            self.array.insert(0, key)
        else:
            if len(self.array) == self.capacity:
                del self.dic[self.array.pop()]
                self.array.insert(0, key)
            else:
                self.array.insert(0, key)
        self.dic[key] = value


s = LRUCache(2)
s.put(1, 1)
s.put(2, 2)
print s.get(2)
s.put(3, 3)
print s.get(2)
s.put(4, 4)
print s.get(1)
print s.get(3)
print s.get(4)

LFU 有一个test case就是过不了。放弃了！！有一个哥哥的答案写得很好。有空照着写一个。

class Node():

    def __init__(self, key, val):
        self.cnt = 1
        self.key = key
        self.val = val
        self.left = None
        self.right = None

    def __repr__(self):
        return repr(self.val)


class LFUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.head = None
        self.tail = None
        self.dic = {}


    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.dic:
            return -1
        else:
            node = self.dic[key]
            node.cnt += 1
            self.moveForward(node)
            return node.val

    def put(self, key, val):
        """
        :type key: int
        :type val: int
        :rtype: void
        """
        if not self.capacity:
            return

        if not self.dic:
            node = Node(key, val)
            self.dic[key] = node
            self.head = node
            self.tail = node
        elif key not in self.dic:
            node = Node(key, val)
            if len(self.dic) == self.capacity:
                self.replaceTail(node)
            else:
                self.tail.right = node
                node.left = self.tail
                self.tail = node
                self.moveForward(node)
            self.dic[key] = node
        else:
            node = self.dic[key]
            node.val = val
            node.cnt += 1
            self.moveForward(node)

    def moveForward(self, node):
        if not node.left:
            return
        else:
            while node.left and node.cnt >= node.left.cnt:
                if self.tail  == node:
                    self.tail = node.left
                self.swapNode(node.left, node)
            if not node.left:
                self.head = node

    def swapNode(self, left, right):
        leftLeft = left.left
        rightRight = right.right
        left.left = right
        left.right = rightRight
        right.left = leftLeft
        right.right = left
        if rightRight:
            rightRight.left = left
        if leftLeft:
            leftLeft.right = right

    def replaceTail(self, node):
        tail = self.tail
        pre = tail.left
        if pre:
            pre.right = node
            node.left = pre
        else:
            self.head = node
        self.tail = node
        del self.dic[tail.key]


s = LFUCache(3)
s.put(1, 1)
s.put(2, 2)
s.put(3, 3)
s.put(4, 4)
print s.get(4)
print s.get(3)
print s.get(2)
print s.get(1)
s.put(5, 5)
print s.get(1)
print s.get(2)
print s.get(3)
print s.get(4)
print s.get(5)

第四轮：老白，问了些简历之后来了个小的design，怎么实现一个系统，如果key不在里面就新加一个entry并返回true，如果key在里面就直接返回false，类似unix系统里的touch这个命令。先讲了单机版的，主要focus在write lock怎么整；然后scale，我是用consistent hashing做的。这个老白挺nice的，一旦他觉得我懂某个东西，就认可，然后不再追问下去了。最后剩了15分钟左右聊天。

hmmm, 完全没法准备。

第五轮：年纪大的三哥，在硅谷工作多年了。出了个题是只有一个院子，两个人要遛狗，两人的狗不合，所以不能同时在院子里，这两个人各有两面旗子，只能通过举旗来通信。其实就是多线程的信号灯问题，写了代码，并walk through。最后剩下10分钟左右聊天。

这都什么抽象题啊。随便写了一个。

class Garden(object):
    def __init__(self):
        self.in_use = False
        self.owner = None

    def raise_flag(self, person):
        if self.in_use:
            return False
        else:
            self.in_use = True
            self.owner = person

    def is_available(self):
        return not self.in_use


    def exit(self, person):
        if person == self.owner:
            self.in_use = False
            self.owner = None

g = Garden()
print g.raise_flag('a')
print g.is_available()
print g.exit('b')
print g.is_available()
print g.exit('a')
print g.is_available()

第六轮：小白，他在1455那个楼，所以视频聊的。纯behavior，谈了team work，怎么处理冲突，以及uber的culture这些问题。这轮本来只有45分钟，到时候了本来安排是我的recruiter跟我聊一下送人的，但他一直没来，这个小白陪着我多聊了15分钟直到他的会议室有meeting把他踢出去了，这15分钟有在kill some time的感觉，略有点尴尬。最后是coordinator来把我送走的，说1天左右出结果。

Onsite 2. 跪。 2017-12-11

感觉Uber现在面试都好迷啊！

1: manager 问 BQ，project。

无法准备

2:问系统设计：问如何设计一个系统，给你task come in，在spark里跑，跑完有一些log，apply ML model 去分析这些log。他问得非常混乱，我就说写一些script就都可以操作了。他又临时改主意了，
无法准备

问怎么统计一个月里uber rider发出的打车request。我说用什么DB，然后去DB里检索就行。然后他又问了一个地区DB不够大怎么办？

3：game of life

这道题还是有点经典的！

class Solution(object):
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]:
            return

        for i in range(len(board)):
            for j in range(len(board[0])):
                cnt = 0
                for d, p in [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (1, -1), (-1, -1)]:
                    r, c = i+d, j+p
                    if 0 <= r < len(board) and 0 <= c < len(board[0]) and board[r][c] & 1:
                        cnt += 1
                if board[i][j] & 1:
                    if cnt == 2 or cnt == 3:
                        board[i][j] = board[i][j] ^ 2
                elif cnt == 3:
                    board[i][j] = board[i][j] ^ 2


        for i in range(len(board)):
            for j in range(len(board[0])):
                board[i][j] = board[i][j] >> 1

        return board

s = Solution()
print s.gameOfLife([[1,1],[1,0]])

4: level order print BST

我靠，为什么当年考我那么难！

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []

        res = []
        q = [root]

        while q:
            length = len(q)
            curLevel = []
            for i in range(length):
                tmp = q.pop(0)
                curLevel.append(tmp.val)
                if tmp.left:
                    q.append(tmp.left)
                if tmp.right:
                    q.append(tmp.right)
            res.append(curLevel)

        return res


a, b, c = TreeNode(1), TreeNode(2), TreeNode(3)
b.left, b.right = a, c
s = Solution()
print s.levelOrderBottom(b)

5:一个数组，print top k freq的数。

强还是py强啊！

from collections import Counter

class Solution(object):
    def topKFreq(self, k, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        return [i[0] for i in Counter(nums).most_common(k)]


s = Solution()
print s.topKFreq(2, [1, 2, 3, 1])