yp onsite 1-10
已经跪了辣么多公司啦。这个dream company可是不能再跪啦！ 奔跑吧咸鱼！
P1 How do I find the greatest sum on a path from root to leaf (that can only touch one node per level—no going up and down) in this tree like structure? Question Quora link
class Solution(object):
def findMax(self, root):
if not root:
return 0
left = self.findMax(root.left)
right = self.findMax(root.right)
return max(left, right) + root.val
这道题抽空写一下吧 https://leetcode.com/problems/binary-tree-maximum-path-sum/
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.max_val = float('-inf')
self.helper(root)
return self.max_val
def helper(self, root):
if not root:
return 0
l = self.helper(root.left)
r = self.helper(root.right)
l, r = [0,l][l>0], [0,r][r>0]
self.max_val = max(self.max_val,l+r+root.val)
return max(l, r) + root.val
P2 第一轮面，上来就问 why yelp，然后问简历的project。完了之后做题目，leetcode 121 best time to buy and sell stock 原题。我一上来居然想到了trapping water那题。。。用了两个数组来存某个位置其左边最小值，和其右边最大值。在面试官引导优化了空间，最后其实不用额外空间就可以的。。。
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices:
return 0
small = prices[0]
res = 0
for p in prices:
small = min(p, small)
res = max(res, p-small)
return res
prices = [7, 1, 5, 3, 6, 4]
so = Solution()
ans = so.maxProfit(prices)
print ans
P3 第二轮面，还是问 why yelp，然后问简历的project。然后是一道 smallest k elements in an array的题，用个max heap搞定。我感觉挺满意。结果面试官又来一题。简易版的 lc 290 word pattern， 比如 foo 对应 app 就是对的，要是 foo 对应 apg 那就是错啦。很简单吧。结果我上来只用了一个HashMap，写完了后，他让我写test case，我自己写了下，发现不对，赶紧又加了一个HashMap.. 险过。
import heapq
class Solution(object):
def kthSmall(self, nums, k):
"""
:type nums: List[int]
:rtype: int
"""
q = []
for num in nums:
if len(q)<k:
heapq.heappush(q, -num)
elif num<-q[-1]:
heapq.heappushpop(q, -num)
res = [-i for i in q]
return res
nums = [10,9,8,7,6,5,4,3,2,1]
so = Solution()
ans = so.kthSmall(nums, 3)
print ans
class Solution(object):
def wordPattern(self, pattern, s):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
string = s.split(' ')
p2s = {}
used = set()
if len(pattern)!=len(string):
return False
for i in range(len(pattern)):
if pattern[i] not in p2s:
if string[i] in used:
return False
else:
p2s[pattern[i]] = string[i]
used.add(string[i])
else:
if p2s[pattern[i]]!=string[i]:
return False
return True
pattern = 'abba'
s = 'dog dog dog dog'
so = Solution()
ans = so.wordPattern(pattern, s)
print ans
P4 第三轮面，还是问 why yelp，然后问简历的project。需要提一下，每轮面试官结束后，他会和下个面试官交流个两三分钟，然后下个面试官再进来。我前两轮介绍的project都是我最熟的那个，结果第三个面试官就直接问我，你咋总是讲那一个project。。。 好吧，换个project开始侃了。侃完了后，出一道题，懵了。
你们帮我看一看。题目是：给一串movie，假定每个movie都是一个小时，并且都在整点播放；给你一个List的movies，让你安排播放时间，如果没有答案throw一个exception。
比如 电影A: 14, 15, 16, 17 电影B: 14, 15, 16 电影C: 14, 15 电影D: 14, 15, 17
比如 电影A: 14, 15, 16, 17 电影B: 14, 15, 16 电影C: 14, 15 电影D: 14, 15, 17
返回一个解就行，比如 A 14, B 16, C 15, D 17。 如果你要 A 14, B 15, 后面 C就没法看了。
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
P5 然后上题，设计一个Rate limitor。就是一小时内访问第六次时，就返回false。这也没啥算法啊，我没太明白，就是HashMap，存访问的IP和ArrayList\
import collections
class RateLimiter(object):
def __init__(self, k):
"""
:type k: int
"""
self.dic = {}
self.capa = k
def checkIP(self, ip, timestamp):
"""
:type ip: string
:type timestamp: int
:rtype: bool
"""
if ip not in self.dic:
self.dic[ip] = collections.deque([timestamp])
return True
else:
dq = self.dic[ip]
if len(dq)<self.capa:
dq.append(timestamp)
return True
else:
if dq[0]-timestamp>=60:
dq.popleft()
dq.append(timestamp)
return True
return False
r = RateLimiter(6)
print r.checkIP(1,1)
print r.checkIP(1,2)
print r.checkIP(1,3)
print r.checkIP(1,4)
print r.checkIP(1,5)
print r.checkIP(1,6)
print r.checkIP(1,7)
P6 coding：设计一个函数，给定一个list，能够返回一个内部元素random permutation过后的该list。很快写出一共不到10行，随后问一些基于permutation的概率题，最后说你如何测试该函数。楼主答的一测试edge cases，二测试overall results是否uniformly distributed。由于并不是很懂伪随机的原理，可能在这里答一些伪随机的内容会更好。
import collections
from random import randint
class Solution(object):
def randomPermute(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
res = []
self.getPermute(nums, [], res)
index = randint(0,len(res)-1)
return res[index]
def getPermute(self, nums, path, res):
if not nums:
res.append(path)
for i in range(len(nums)):
self.getPermute(nums[:i]+nums[i+1:], path+[nums[i]], res)
nums = [1,2,3]
so = Solution()
ans = so.randomPermute(nums)
print ans
res = []
for i in range(1000):
res.append(tuple(so.randomPermute(nums)))
print collections.Counter(res).items()
P7 1轮skype的美国大哥：聊简历，coding题是给你一群nodes，每一个node里有3个invariants: unique的id，可能重名的label，其parent的id。要求将一组乱序的nodes按照如下方式print出来： Node A Node B Node C Node D Node E 这里BD的parent为A，C的为B，AE的为一个id=0的默认root（不print），也就是子node按照depth要缩进相应的空格。 这题不难，我是先遍历nodes重建了储存children关系的hash table，然后写了一个基于stack的方法，中间卡了下壳，还好大哥人很nice，提示了下，就“looks great to me”了。Follow up是“我看你写的是iteration，告诉我写成recursion的话pros和cons是啥”，我答了一些基本比较，他满意，后面就闲聊
思路：我觉得这道题还是有点意思的啊。
import collections
class Node(object):
def __init__(self, id, label, p):
self.id = id
self.label = label
self.p = p
class Solution(object):
def printNodes(self, nodes):
"""
:type nodes: List[Node]
:rtype: None
"""
dic = collections.defaultdict(set)
roots = []
for n in nodes:
if n.p:
dic[n.p].add(n)
else:
roots.append(n)
res = []
for node in roots:
self.dfs(dic, node, 0, res)
def dfs(self, dic, cur, numspace, res):
print (' '*numspace + cur.label)
if cur not in dic:
return
children = dic[cur]
for c in children:
self.dfs(dic, c, numspace+1, res)
a = Node(1, 'A', None)
b = Node(2, 'B', a)
c = Node(3, 'C', a)
d = Node(4, 'D', None)
nodes = [a,b,c,d]
so = Solution()
so.printNodes(nodes)
用stack的写法
import collections
class Node(object):
def __init__(self, id, label, p):
self.id = id
self.label = label
self.p = p
class Solution(object):
def printNodes(self, nodes):
"""
:type nodes: List[Node]
:rtype: None
"""
dic = collections.defaultdict(set)
s = []
for n in nodes:
if n.p:
dic[n.p].add(n)
else:
s.append((n,0))
while s:
node, num = s.pop()
print (' '*num + node.label)
if node in dic:
children = dic[node]
for c in children:
s.append((c, num+1))
a = Node(1, 'A', None)
b = Node(2, 'B', a)
c = Node(3, 'C', a)
d = Node(4, 'D', None)
nodes = [a,b,c,d]
so = Solution()
so.printNodes(nodes)
P9 3轮美国小哥：Physics PhD帅哥。聊简历，设计题：yelp现在要给附近一些新发掘的店铺定制category label，问你如何根据user对该新店铺的review得知该店铺属于restaurant, gas station,...的哪一个。classification问题，也是开放性的。Followup是如何对应“I just had a meal nextdoor”这种容易将一般店铺误判为restaurant的review。coding题出乎意料的简单。说是yelp每次有人访问会给一个临时id，6位digits，问你如何判断这6数字里有重复的…一行搞定，第二问是给了一个当天所有临时id的log，求今天id中带有重复数字的比率是多少…套用前问结果10行搞定，最后又来permutation相关的概率题，但都很简单。
class Solution(object):
def ifDuplicate(self, id):
return len(id)==len(set(id))
class Solution(object):
def percent(self, ids):
cnt = 0
for id in ids:
if self.ifDuplicate(id):
cnt +=1
return float(cnt)/len(ids)
def ifDuplicate(self, id):
return len(id)==len(set(id))
ids = [1,2,3,4,5,7,8,9,10,11]
ids = map(str,ids)
so = Solution()
ans = so.percent(ids)
print ans
P8 4轮三哥：不好好听就提问打断，玩手机，全程站起来转椅子玩（醉了），不交流不帮助不给思考时间，楼主卡壳他就直接下一题。聊简历，coding题是leetcode原题longest palindromic substring，还问我之前见过这题没。我说没，然后想不起来O(n)的方法了就只好写了最土的从每个字符往两边搜的O(n^2)方法。Followup是我只有一个只能获得最长odd length palindrome的函数f_odd，问如何调用这个得到原函数，也就是 f (s) = g1(f_odd(g2(s)))，求g1，g2。楼主答了给原string插入#再处理，最后得到结果后每隔一个字去除#，被问原string含#怎么办，卡壳不到30秒就说算了我问你behavioral question，然后心不在焉地听了会就结束了。
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
res = ''
for i in range(len(s)):
tmp = self.helper(i, i, s)
if len(tmp)>len(res):
res = tmp
tmp = self.helper(i, i+1, s)
if len(tmp)>len(res):
res = tmp
return res
def helper(self, i, j, s):
while 0<=i<=j<len(s) and s[i]==s[j]:
i -= 1
j += 1
return s[i+1:j]
P9 TinyURL 用最简单的发号的方法写了一个
class TinyUrl(object):
def __init__(self):
self.l2s = {}
self.s2l = {}
self.prefix = 'zach.cn/'
def longToShort(self, url):
"""
:type url: str
:rtype: str
"""
if url in self.l2s:
return self.l2s[url]
else:
s = str(len(self.l2s))
self.l2s[url] = s
self.s2l[s] = url
return self.prefix + s
def shortToLong(self, url):
"""
:type url: str
:rtype: str
"""
if url[:8] == self.prefix:
if url[8:] in self.s2l:
return self.s2l[url[8:]]
s = 'abc'
so = TinyUrl()
print so.longToShort('www.abc.com/sadjasnvxvx')
print so.shortToLong('zach.cn/0')
print so.longToShort('www.aaa.com/dsakhzxhvcx')
print so.shortToLong('zach.cn/1')
print so.longToShort('www.bbb.comwqruwqifqin')
P10 第二个是个印度manager，聊projects，让写merge interval，问了dns, tcp, 数据库等基本知识。
class Solution(object):
def mergeIntervals(self, intervals):
if not intervals:
return []
intervals.sort()
s, e = intervals[0]
res = []
for i in range(1, len(intervals)):
cur_start, cur_end = intervals[i]
if cur_start<=e:
e = cur_end
else:
res.append([s,e])
s, e = cur_start, cur_end
res.append([s,e])
return res
intervals = [[0,5], [10,20], [15,30]]
so = Solution()
ans = so.mergeIntervals(intervals)
print ans