有5年经验，做Security方面的
在 Mountain View 直接onsite，跳过店面
第一轮: Coding
We’re given a list of internvals and the corresponding speed for that interval. This list represents ranges within an infinite road and the speed of vehicles in those ranges. We are supposed to return the final list of smallest ranges and the average speed of vehicles in each of those ranges.
input = [(5, 15, 20), (10, 20, 30)]
output = (5, 10, 20), (10, 15, (20 + 30)//2), (15, 20, 30)
output = (5, 10, 20), (10, 15, 25), (15, 20, 30)
input = [(5, 15, 20), (10, 20, 30), (7, 25, 10)]
output = [(5, 10, 20), (10, 15, 25), (15, 20, 30)] merged with (7, 25, 10)
output = [(5, 7, 20), (7, 10, (20 + 10)//2), (10, 15, (25 + 10)//2), (15, 20, (30 + 10)//2), (20, 25, 10)
output = [(5, 7, 20), (7, 10, 15), (10, 15, 17.5), (15, 20, 20), (20, 25, 10)
Solution:
- I used a solution similar to My Calendar II, III.
- Here, where we’ll have unlimited bookings.
- I use an approximate average. However, it is better to keep a total of how many interval merged into a node (number of bookings for that interval) and the total speed for that interval
class Node:
def __init__(self, s, e, sp):
self.s, self.e, self.sp = s, e, sp
self.left, self.right = None, None
class Events:
def __init__(self):
self.root = None
def insert(self, s, e, sp):
if not self.root:
root = Node(s, e, sp)
return
self._insert(s, e, sp, root)
def _insert(self, s, e, sp, i_root):
if s == e: return
if e <= i_root.s:
self._insert(s, e, sp, i_root.left)
elif s >= i_root.e:
self._insert(s, e, sp, i_root.right)
else:
a = min(i_root.s, s)
b = max(i_root.s, s)
c = min(i_root.e, e)
d = max(i_root.e, e)
if i_root.s != s and i_root.s == b:
left_sp = sp
else:
left_sp = i_root.sp
if i_root.e != e and i_root.e == c:
right_sp = sp
else:
right_sp = i_root.sp
self._insert(a, b, left_sp, i_root.left)
self._insert(c, d, right_sp, i_root.right)
i_root.sp = (i_root.sp + sp) / 2
# return in order traversal
Didn’t have time to complete. Didn’t see any such problem on LC before.
第二轮: More Coding
Interviewer gave me a story regarding how I wanted to cut a chocolate by sweetness such a way that the sweetest piece was least sweet so that the one who gets the least sweet piece get the maximum sweetness and some nonsense. I was thoroughly confused and didn’t solve it.
Important bit was that the problem was this one https://leetcode.com/problems/split-array-largest-sum/description/
Solved using DP or Binary Search with some analysis of the mid at every stage of the search.
第三轮: More Coding Wowie
The problem was to implement a monarchy. Where we’re to implement a class.
class Monarchy:
def __init__(self, king_name):
pass
def birth(self, name, parent):
pass
def death(self, name):
pass
def get_order_of_succession(self):
pass
I used an nary-tree and did this like so:
class Node:
def __init__(self, name):
self.name = name
self.children = []
class Monarchy:
def __init__(self, king_name):
self.root = king_name
self.names_map = {king_name: Node(king_name)}
def birth(self, name, parent):
node = self.names_map[parent]
child = Node(name)
node.children.append(child)
self.names_map[name] = node
def death(self, name):
node = self.names_map[name]
if node == self.root:
first_c = self.root.children.pop(0)
self.root = first_c
first_c.children.extend(self.root.children)
for n in self.root.children:
if self._delete(node, n, self.root):
break
def _delete(self, delete_node, node, parent):
if node == delete_node:
i = parent.children.index(node)
for c in node.children:
parent.children.insert(i, c)
i += 1
return True
for c in node.children:
if self._delete(delete_node, c, node):
return True
return False
def get_order_of_succession(self):
self._dfs(self.root)
def _dfs(self, node):
print(node.name)
for c in node.children:
self._dfs(c)
Never saw such a problem on LC before. Anyone know any similar problems?
I didn’t get to complete the code in the interview as it took forever to clarify and understand how the interviewer expected the death of a person to be handled. It was a little non-intuitive. A point to note is that a if a person dies high children, grandchildren and so on take his place in line of succession.
Lunch: Fajitas! Yes, Please.
Interviewer was very curious about my work and interests and I was constantly engaged during the whole lunch.
第五轮: Security Domain
Attack Google users, go ahead do your worst, you have unlimited budget! 
I answered with lots of good stuff namely:
phising using fake login pages, password stealing, brute-force, ARP spoofing, DNS rebinding, HSTS downgrade, near domain name hijacking, IP spoofing, Fake OAuth and password stealing.
Need your collective knowledge to figure out what I did wrong during the interview. It was as good as I could do. 
It still wasn’t enough. The chocolate problem was patirularly brutal!