Onsite 3-4
onsite 3. 跪 2017-12-11
1 :给一堆users，和她们的上下车的时间，然后给出所有的乘车数目变化的时间点，扩展是有可能同一个user id，应该不同的人打开了app，乘车. 所以时间有overlap，如何handle
我就写一个meeting room吧。
class Interval(object):
def __init__(self, s=0, e=0):
self.start = s
self.end = e
class Solution(object):
def minMeetingRooms(self, intervals):
"""
:type intervals: List[Interval]
:rtype: int
"""
times = []
for interval in intervals:
times.append((interval.start, 'start'))
times.append((interval.end, 'end'))
times.sort()
cnt = 0
res = []
for t in times:
if t[1] == 'start':
cnt += 1
else:
cnt -= 1
if res and res[-1][0] == t[0]:
res[-1] = (t[0], cnt)
else:
res.append((t[0], cnt))
return res
times = [[0, 30],[5, 15],[15, 20]]
intervals = [Interval(t[0], t[1]) for t in times]
s = Solution()
ans = s.minMeetingRooms(intervals)
print ans
2: long polling, push, user based, geograph based and mixed hashing, pros and cons, if a rider is assigned a driver, and the server really got the ack, why the rider does not know he is assigned.... 这个问题最后回到的是rate limiting,要求写一个Mt 的rate limiter, 用circular buffer
Just for the sake of argument.
Both are http request (xhr), and its at least partially untrue it uses more server resources (depends totally on technology, will explain later).
Short polling.
Lot of request that are processed as they come on server. Creates a lot of traffic (uses resources, but frees them as soon as response is send back):
00:00:00 C-> Is the cake ready?
00:00:01 S-> No, wait.
00:00:01 C-> Is the cake ready?
00:00:02 S-> No, wait.
00:00:02 C-> Is the cake ready?
00:00:03 S-> Yeah. Have some lad.
00:00:03 C-> Is the other cake ready? ..
Long polling
One request goes to server and client is waiting for the response to come (its unresolved). In case of Server with php/apache would mean a spawned thread to handle, that reserve resources, till its done. So the traffic is smaller, but you eat up your resources fast (or rather you block resources). But if you use for example Node (or any other async approach - c++ qt for example), you can potentially minimize the resource usage a lot (store response object for http request and use it when the work is ready)
12:00 00:00:00 C-> Is the cake ready?
12:00 00:00:03 S-> Yeah.Hame some lad.
12:00 00:00:03 C-> Is the cake ready?
If you compare that to short polling, you will see that potentially in short poll you used more transfer, but during those 3s you actually take 1,5s of processing time (means something could execute in between your calls). In case for long poll the same resources were used all the time. Now usually php with all libs starts with 4MB memory - then you have a framework 4-20MB. Assume you have 1024MB RAM available (free). Say lets be pessimistic and assume that you will use 25 MB per one php instace. It means you can get only as much as 40 long polled connection scripts.
Its precisely the reason why you could serve potentially a lot more with Node, as node would not spawn its instances (unless you want to use workers etc), so with same memory you could probably get easily to 10k connections hanging. You would get a spike in the CPU as they will come, and when they will potentially be released, but when they are idle its like they are not there (you pay only for the memory structures you would keep in node/c++).
Websocket
Now if you want to send few things, whenever they are in or out of client, go for the websockets (ws protocol). First call is size of http request, but later you send just the messages, from the client to server (new questions) and server to client(answers or pushes - can even do broadcast for all connected clients). There are php websocekts libs but again, use some different technology - node or c++ preferably.
Some libs, like socket.io have a hierarchy of its own, so when websocket fails, it goes back to long or short polling.
When to use.
Short polling - well, never ^^.
Long polling - potentially when you are exchanging single call with server, and server is doing some work in background. Also when you won't query server on the same page anymore. Also when you are not using php as layer to handle the long polled connection (node/c++ can be a simple middle layer). Note long polling can be really beneficial, but only when you make it so.
Websocket - you potentially will exchange more then one or two calls with server, or something might come from server you did not expected / asked, like notification of email or something. You should plan different "rooms", depend on functionalities. Embrace the event based nature of javascript ;]
3: behavior +turing code related brain storming
没法准备
4: hiring mgr, project and behavior
没法准备
5: Design a feature that the riders can share the trip with the followers
有点像design news feed。
Onsite 4. 2017-11-23 02:43:41
第一轮 给一个很大的数组，还有一个数组是 blacklist, 要求在大数组中return 不在blacklist 里的数with equal probabity. 只能用O(blacklist)空间
from random import randint
import collections
class Solution(object):
def __init__(self, blackList):
"""
:type blackList: List[int]
:rtype: None
"""
self.blackList = blackList
self.selectedNum = None
def getRandom(self, num):
"""
:rtype: int
"""
if num not in blackList:
if not self.selectedNum:
self.selectedNum = num
else:
self.selectedNum = [num, self.selectedNum][randint(0, 1)]
return self.selectedNum
nums = [1, 4, 5, 2, 3, 5, 1, 3, 5]
blackList = [2, 3]
so = Solution(blackList)
for n in nums:
print so.getRandom(n)
第二轮 工作经验闲聊
没发准备
第三轮 现场笔记本coding 数据库死锁检测
这道题感觉像一道原题。可是就是找不到了。
第四轮 系统设计 design 吴波
第五轮 现场笔记本coding 利特口数倒二 follow up grid 是不定size的
number of island II.用union find。来来来我们写一遍！哇，这么久不写硬是被我写出来了。
class UF():
def __init__(self):
self.dic = {}
self.cnt = 0
def find(self, p):
start = p
if p not in self.dic:
self.add(p)
while p != self.dic[p]:
p = self.dic[p]
self.dic[start] = p
return self.dic[start]
def union(self, p, q):
p_anc, q_anc = self.find(p), self.find(q)
if p_anc != q_anc:
self.cnt -= 1
self.dic[p_anc] = q_anc
else:
return
def add(self, p):
if p not in self.dic:
self.dic[p] = p
self.cnt += 1
class Solution(object):
def numIslands2(self, m, n, positions):
"""
:type m: int
:type n: int
:type positions: List[List[int]]
:rtype: List[int]
"""
uf = UF()
lands = set()
res = []
for x, y in positions:
uf.add((x, y))
lands.add((x, y))
for d, p in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
i, j = x + d, y + p
if (i, j) in lands:
uf.union((i, j), (x, y))
res.append(uf.cnt)
return res
s = Solution()
print s.numIslands2(3, 3, [[0,0],[0,1],[1,2],[2,1]])