yp onsite 41-50
P41 印度女 algo: Why developer over data scientist a long sentence, find the shortest distance between two words, duplicated word may appear
class Solution(object):
def shortest(self, s):
dic = {}
start = 0
flag = False
for i in range(len(s)):
if flag==False:
if s[i]!=' ':
flag = True
start = i
else:
if s[i]==' ':
flag = False
w = s[start:i]
if w in dic:
return start - dic[w]
else:
dic[w] = i
if s[start:] in dic:
return start - dic[s[start:]]
return None
s = 'a b a'
so = Solution()
ans = so.shortest(s)
print(ans)
P42 白人男： 背景出身后端， 现在全栈 algo: architecture: talking about the Amazon Internship Project longest substring with no duplicated characters
可能没回答好的地方：
1. architecture
2. API
3. design pattern
class Solution(object):
def longesSustringNoRepeating(self, s):
dic = {}
start = 0
res = ''
for i in range(len(s)):
if s[i] in dic and start<dic[s[i]]:
start = dic[s[i]]+1
res = s[start:i+1] if len(s[start:i+1])>len(res) else res
dic[s[i]] = i
return res
s = 'abcdeb'
so = Solution()
ans = so.longesSustringNoRepeating(s)
print(ans)
P43 俄罗斯男 algo: tireTree + DFS, search in a 2-d matrix, talks about idea how it works 可能没回答好的地方：
1. 深度算法，data structure
2. side project
这道题我写过。 https://leetcode.com/problems/word-search-ii/
P44 印度男 algo: programming language: java vs python copy a linked list with random pointer, the random pointer pointing to an external object that can be any type 可能没回答好的地方：
1. API
2. programming language: how to choose language; compare different PL
3. design pattern
https://leetcode.com/problems/copy-list-with-random-pointer/
random object这个不是感觉更好写么，我觉得连dic都不要了，直接过一遍linkedList，然后直接把新的node指向random的那个就好了啊。
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
m, n = head
dic = {}
while m:
dic[m] = RandomListNode(m.label)
m = m.next
while n:
dic[n].next = dic.get(n.next)
dic[n].random = dic.get(n.random)
n = n.next
return dic.get(head)
如果我没理解错的话，大概意思是这样？
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
m = head
dic = {}
root = None
while m:
node = RandomListNode(m.label)
if not root:
root = node
node.random = m.random
m = m.next
return root
P45（1）美国小哥，面善，健谈 why yelp ? 果然问了！ 谈project， 谈趣点 what's the reason a page is loading slow? How can we improve? coding: business id那道题，之前有人po过的，给你一个字符串小写的带数字，比如 asd7d2c，在所有字母大小写组合的可能性中，返回所有是valid的 id，没啥难度，但是已经是一天里最有难度的题了T^T
为了更省时间，其实可以建trie。这样prefix没有match到的，就不用继续往下recurse了。
class Solution(object):
def validID(self, s, words):
res = []
self.dfs(s, 0, words, '', res)
return res
def dfs(self, s, i, words, path, res):
if i==len(s):
if path in words:
res.append(path)
return
if s[i].isalpha():
self.dfs(s, i+1, words, path+s[i].lower(), res)
self.dfs(s, i+1, words, path+s[i].upper(), res)
else:
self.dfs(s, i+1, words, path+s[i], res)
s = 'as4bc'
words = ['aS4bc', 'As4bC']
so = Solution()
ans = so.validID(s, words)
print ans
P46（2）棕色小哥，面善，不健谈 why yelp ? 又问！ 谈 project，谈难点 how will you want to improve yelp? 我说的都是用户体验 coding: given a text file, print them out line by line in a random order
file = open(filename, "rb", 0)
# Read in the file once and build a list of line offsets
line_offset = []
offset = 0
for line in file:
line_offset.append(offset)
offset += len(line)
file.seek(0)
# Now, to skip to line n (with the first line being line 0), just do
file.seek(line_offset[n])
P47（3）美国小叔，面不善不恶，健谈 why yelp ? 还问！！ 谈project， 谈印象深刻 pick two languages you are comfortable with, talk about their difference. (选了 C++ and Java 因为经常与人议论) system design : a lirabry database system that has entity Book and Reader, 要调查某个读者度过的所有书，或所有读过某本书的读者，如何设计？于是设计了新的entity Log follow up (1) 如果一个读者反复读了很多次书呢？（要unique pair） follow up (2) 如果要获得读者读书的时间的记录呢？(多一个属性) follow up (3) 要查看一个读者读一本书的所有记录？(时间，读者，书 三个的组合要unique) coding: 给一个数组，一个target， 返回所有加起来sum是target的pair，不重复。好吧这题算碾压，因为leetcode随便一个3sum, 4sum都能做了，这个只是其中的一部分
三个table, book, user, readingrecord tables.然后设计几个query就行了 我心中已有丘壑。
P48（4）美国大叔，面不善不恶，不健谈 why yelp ? 问了四遍啊！！！ 谈project， 谈细节，谈优化，谈设想 问了一个蛮蠢的问题，过一个文件，打其中一行，求复杂度？我很莫名，说过一遍是O(n), 打一行是O(1)。大叔居然执着地问一句：所以总共的复杂度是？丫的看不起我个子矮呢（>_<） coding 1 给个文件，读一遍以后把每行以 string 形式存在 array 中，随机打出所有 coding 2: 给个文件，能 O(1) 返回文件长度，以及某个位置的数据，要求随机打出一行。 这题就是用文件长度随机定点，然后移动坐标找到 '\n' 也就是前一行的行末，打到本行的行末。 缺陷呢？每行长短不同会引起被选中的概率不同。 好处呢？时间空间复杂度都低
Link P49 第一轮. 美国小哥，先自我介绍一下，然后要我选择一个project，假定给一个非CS的朋友讲一下，还问了word count怎么用mapreduce实现，接下来就是coding了 给一个map， 里面包含了{"Monday" : 200 - 300, 500 - 700, 300 - 500, "Tuesday", 300 - 500, 700 - 900 ......}, 把value里面重叠的部分合并，仍然输出一个map
class Solution(object):
def mergeTime(self, days):
"""
:type dic: Dict[str:List[List[int]]]
:rtype dic: Dict[str:List[List[int]]]
"""
for d in days:
days[d] = self.mergeIntervals(days[d])
return days
def mergeIntervals(self, intervals):
intervals.sort()
res = []
for i in intervals:
if res and i[0]<=res[-1][1]:
res[-1][1] = max(res[-1][1], i[1])
else:
res.append(i)
return res
days = {"Monday": [[200, 300], [500, 700], [300, 500]], "Tuesday": [[300, 500], [700, 900]]}
so = Solution()
ans = so.mergeTime(days)
print ans
P50 第二轮. 亚裔小哥， 先自我介绍，简单聊了一下project，然后就是coding，给一个任意的binary tree， encode成string，再decode成tree
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if root:
res = str(root.val) + ' '
res += self.serialize(root.left)
res += self.serialize(root.right)
return res
return '# '
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
s = data.split(' ')
return self.helper(s)
def helper(self, s):
if s[0]=='#':
s.pop(0)
return
root = TreeNode(int(s.pop(0)))
root.left = self.helper(s)
root.right = self.helper(s)
return root
a = TreeNode(2)
b = TreeNode(1)
c = TreeNode(3)
a.left = b
a.right = c
so = Codec()
ans = so.serialize(a)
print ans
a = so.deserialize(ans)
print a.right.right