# 谷歌 L4 上门挂经

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.

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.

Solved using DP or Binary Search with some analysis of the mid at every stage of the search.

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.

Attack Google users, go ahead do your worst, you have unlimited budget! 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!  