yp onsite 61-70
小弟在此奉上yelp on-site面經 攢攢人品先說yelp很喜歡 聊天問之前的project 因為我mapreduce, sql db, nosql db的經驗比較多, 所以他們一直問我之前的項目, 還有這些東西的相關知識 所以做題時間都不多, 一輪大概就一道coding題
1 是一個白人可愛的正妹, 先是一些知識性問題. i.Difference between SQL v.s NoSQL, when to use each one? what is SQL’s index? ii.What is load balancer, why we need it? how to detect load balancer really work?
iii. 接著要我實作Implement load balancer, 他給的code是c++, 包含幾個送資料給後端servers的function call, 會返回ok, busy, or offline(server 掛了), 我們必須根據這個去implement load balancer的mechanism, 當然這有很多種做法, 就是一陣討論跟分析
Load balancer有一下。具体怎么做，到时候具体分析吧。 Round Robin – Requests are distributed across the group of servers sequentially. Least Connections – A new request is sent to the server with the fewest current connections to clients. The relative computing capacity of each server is factored into determining which one has the least connections. IP Hash – The IP address of the client is used to determine which server receives the request.
- 一個臉很臭的白人manager, 感覺不大喜歡我, i. 先是一堆behavior 問題 previous project’s big challenge, and have you ever made wrong decision and how did you solve it, and have you ever disagreed with you team members’ idea and how did you solve it.
ii. coding question, Implement a package manager (topological sort) Input : { p1 : {p2, p3}, p2 : {p3}, p3 : {} } p1 package is depend on p2, p3, and p2 package is depend on p3, and so on
Output : Any valid installation order p3, p2, p1
估計就掛在他這, 這題一開始沒想到是topological sort, 卡了一下, 出了點小bug.
你看嘛，这些厂就是喜欢变着法子考toposort。
import collections
class Solution(object):
def schedule(self, packages):
can = collections.defaultdict(set)
for key in packages:
for p in packages[key]:
can[p].add(key)
stack = [p for p in can if not packages[p]]
pre = packages
res = []
while stack:
tmp = stack.pop(0)
res.append(tmp)
if tmp in can:
children = can[tmp]
for c in children:
pre[c].remove(tmp)
if not pre[c]:
stack.append(c)
return res
package ={ "p1" : {"p2", "p3"},
"p2" : {"p3"},
"p3" : {}
}
so = Solution()
ans = so.schedule(package)
print(ans)
3 也是一個白人妹子, 這一輪水過 i. Difference between process and thread
ii. Ask me about my intern project
iii. Add two big integers (follow up: support any base(各種進制) for many numbers’ sum up)
https://leetcode.com/problems/add-strings/
class Solution(object):
def addStrings(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
num1, num2 = list(map(int, num1[::-1])), list(map(int, num2[::-1]))
if len(num1)<len(num2):
num1, num2 = num2, num1
carry = 0
for i in range(len(num1)):
n = num2[i] if i<len(num2) else 0
tmp = n + carry + num1[i]
num1[i] = tmp%10
carry = tmp//10
if carry:
num1.append(1)
return ''.join(map(str, num1))[::-1]
4 一個叫duncan的, 人很有趣 i. What is MapReduce?
ii. 問我雲計算的項目, 像是如何設計hbase的schema
iii. Anagrams (Leetcode), can also be done by MapReduce.
https://leetcode.com/problems/anagrams/
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
h = collections.defaultdict(list)
for s in strs:
h[''.join(sorted(s))].append(s)
return map(sorted, h.values())
其實他們家題不難, 但是據說不少人答得好都被拒, 大家good luck
link 本来想在店面贴补充 结果字数超了 重开吧 店面贴Yelp店面面经 onsite攒RP
onsite 面的是infrastructure team
coding题: leetcode anagram leetcode sort version number的一个变种 用随机方法(monte carlo)求Pi 怎么用mapreduce实现 (hadoop自带的example有) 给n个unique整数 实现一个iterator 每次next()返回从中随机抽取的k个不同的整数 不要求实现hasNext
class Solution(object):
def compareVersion(self, version1, version2):
"""
:type version1: str
:type version2: str
:rtype: int
"""
v1 = version1.split('.')
v2 = version2.split('.')
v1 = self.helper(v1)
v2 = self.helper(v2)
print(v1, v2)
if v1>v2:
return 1
elif v1<v2:
return -1
else:
return 0
def helper(self, v):
if len(v)==2:
tmp = list(v[1])
while len(tmp)>=1 and tmp[-1]=='0':
tmp.pop()
v[1] = ''.join(tmp)
return list(map(int,v))
version1 = '1.30'
version2 = '1.200'
so = Solution()
ans = so.compareVersion(version1, version2)
print(ans)
如果是不重复的数字的话，返回res前 需要把随机到的int给delete掉。正常的delete是O(n)的。但是我们如果把需要delete的数字跟最后一个数字swap的话，那么这个delete就是O（1）的。科科
import random
class randomGetK(object):
def __init__(self, nums, k):
self.nums = nums
self.k = k
def get(self):
indexs = random.sample(range(0, len(self.nums)), self.k)
res =[]
for i in indexs:
res.append(self.nums[i])
return res
nums = range(1,100)
so = randomGetK(nums, 5)
ans = so.get()
print(ans)
系统设计和基础知识 设计一个load balancer 解释一个页面请求的全过程 解释java的垃圾回收机制 其他记不得了。。。
他家真心挺好的 挺想去的 比较geek那种 给的包裹也不差的 base比FLG高 后来出于其他因素 选了别家 但是真心推荐大家去面 bar略低于flg 性价比不错
昨天onsite，今天一大早就收到email挂了。。。我这是表现的有多差啊，都不需要讨论一下呵呵 1, 白人大叔 谈project, 谈怎么改进yelp之类。 coding 题：算两个文本的cosin similarity
2, 国人 问project，全程板个脸 一个dp, 不过写完有个bug Given a set of currency denominations, find the minimum number of coins needed to represent an amount. Return 0 if you can't use your coins to represent the target amount. For example: Suppose you have two kinds of coins: 1, 2. In order to represent 3, you have two options: 1 + 1 + 1 = 3 or 1 + 2 = 3 So the minimum number of coins is 2.
class Solution(object):
def coinGame(self, nums, target):
dp = [0]*(target+1)
nums.sort()
for i in range(1, target+1):
res = []
for num in nums:
if (i-num)==0 or (num<=i and dp[i-num]):
res.append(dp[i-num]+1)
dp[i] = min(res) if res else 0
return dp[-1]
nums = [1,2,5]
so = Solution()
ans = so.coinGame(nums, 12)
print(ans)
３，烙印女manager 问project lc Search a 2D Matrix II binary search, 就是每次扔掉1/4数据。然后她说这不是最优解。。。说复杂度还是n^2（应该是O(n)吧，如果是n*n的矩阵） 哪个大牛能说说还有什么更好的解法？
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)
４，白男 概率题，我的最恨！提示下写出来了。 然后是给４个点的坐标，判断能否构成一个正方形。正方形与坐标轴不一定平行。
面完感觉就不太好，虽然题都做出来了。 没想到这么快啊。。。move on吧
Coding:
- 写一个Iterator的类，实现Iterator相加，比如[1,2] + [0] -> [1,2,0]
- Word Ladder II
import collections
class Solution(object):
def findLadders(self, beginWord, endWord, wordlist):
"""
:type beginWord: str
:type endWord: str
:type wordlist: Set[str]
:rtype: List[List[int]]
"""
dic = collections.defaultdict(set)
for w in wordlist+[endWord]:
for i in range(len(w)):
tmp = w[:i] +'_'+ w[i+1:]
dic[tmp].add(w)
res = []
q = [(beginWord, [beginWord])]
while q:
word, path = q.pop(0)
if not res or len(path)<len(res[0]):
for i in range(len(word)):
tmp = word[:i] +'_'+ word[i+1:]
if tmp in dic:
children = dic[tmp]
for c in children:
if c not in path:
if c==endWord:
res.append(path+[c])
q.append((c, path+[c]))
return res
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
so = Solution()
ans = so.findLadders(beginWord, endWord, wordList)
print ans
- Yelp给个business_id，比如3Ed2fU。但是有的时候会被parse成全部小写，这样会导致返回一个无效link。问题是怎么根据给的link，返回所有可能的link。讲白了就是dfs把每个小写字母换成大写字母，看看有多少组合（2^n）; Follow up, 假设找到了一堆合理的link，怎么知道哪个是user想要的？根据ip address返回user附近的business_id，也可以根据user的历史记录返回。
常识题：
- browser输入一个url后发生什么？
- 怎么优化网页loading速度？
- MySQL vs Mongo?
- iframe advantage vs disadvantage
- 假设向server发送请求只有90会成功，怎么提高成功率？
Yelp是python base的。
lc tag 题目
import collections
import heapq
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
dic = collections.defaultdict(int)
for n in nums:
dic[n] += 1
q = []
for key in dic:
cnt = dic[key]
if len(q)<k:
heapq.heappush(q, (cnt, key))
elif cnt>q[0][0]:
heapq.heappop(q)
heapq.heappush(q, (cnt, key))
res = []
while q:
res.append(q.pop()[1])
return res
nums = [1,1,1,2,2,3]
k = 2
so = Solution()
ans = so.topKFrequent(nums, k)
print ans
skyline https://leetcode.com/problems/the-skyline-problem/
import heapq
class Solution(object):
def getSkyline(self, buildings):
times = []
p = {}
for b in buildings:
start = [b[0], -b[2]]
end = [b[1], b[2]]
p[b[1]] = b[0]
times.append(start)
times.append(end)
times.sort()
pq = [(0, 'inf')]
res = []
for t, h in times:
cur_h = pq[0][0]
if h<0:
heapq.heappush(pq, (h, t))
else:
pq.remove((-h, p[t]))
heapq.heapify(pq)
if pq[0][0]!=cur_h:
res.append([t,-pq[0][0]])
return res
- Reverse Words in a String https://leetcode.com/problems/reverse-words-in-a-string/
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
stack = []
res = []
for i in range(len(s)-1, -1, -1):
c = s[i]
if c!=' ':
stack.append(c)
else:
while stack:
res.append(stack.pop())
res.append(' ')
while stack:
res.append(stack.pop())
return ''.join(res)
s = "the sky is blue"
so = Solution()
ans = so.reverseWords(s)
print ans