ramibotros
BAN USERSolved it with a binary search tree.
O(n) runtime: Creation of tree takes O(n) time and then inorder traversal takes O(n) time.
O(n) extra space complexity.
class Node: #BST
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def iter_in_order(self):
if self.left:
yield from self.left.iter_in_order()
yield self.value
if self.right:
yield from self.right.iter_in_order()
def decode(arg_script):
root = Node(1)
fresh_idx = 2
I_node = root
D_node = root
for char in arg_script:
if fresh_idx > 9:
return -1 #invalid input, would force me to use digits > 9
new_node = Node(fresh_idx)
if char == "I":
I_node.right = new_node
I_node = new_node
D_node = new_node
elif char == "D":
D_node.left = new_node
D_node = new_node
fresh_idx += 1
return "".join([str(idx) for idx in root.iter_in_order()])
print(decode("DDIDDIID"))
Not optimal.
IDIIIDD can be "deciphered" to be 13245876 , which is smaller than 1723465
Same solution as most guys but Python's iterator using the yield makes it particularity simpler to write out:
class Node:
def __init__(self, value):
self.left_child = None
self.right_child = None
self.value = value
def insert(self, value):
if value < self.value:
if self.left_child is None:
self.left_child = Node(value)
else:
self.left_child.insert(value)
else:
if self.right_child is None:
self.right_child = Node(value)
else:
self.right_child.insert(value)
def __repr__(self):
return "<" + str(hex(id(self))) + ">(" + str(self.value) + ")"
def min_iterator(self):
if self.left_child:
for node in self.left_child.min_iterator():
yield node
yield self
if self.right_child:
for node in self.right_child.min_iterator():
yield node
def max_iterator(self):
if self.right_child:
for node in self.right_child.max_iterator():
yield node
yield self
if self.left_child:
for node in self.left_child.max_iterator():
yield node
def tree_from_list(lst):
root = Node(lst[0])
for item in lst[1:]:
root.insert(item)
return root
def find_pair(root, sum_value):
min_iter, max_iter = root.min_iterator(), root.max_iterator()
min_node = next(min_iter)
max_node = next(max_iter)
while True:
if min_node is max_node:
return None, None
cur_sum = min_node.value + max_node.value
if cur_sum == sum_value:
return min_node, max_node
elif cur_sum > sum_value:
max_node = next(max_iter)
elif cur_sum < sum_value:
min_node = next(min_iter)
tree = tree_from_list([60, 41, 74, 16, 53, 65, 25, 46, 55, 63, 70, 42, 62, 64])
print find_pair(tree, 41 + 74)
Here is my simple solution.
Requires sorting then traversing the list of persons once.
1) Sort persons by multiple indexes : First index is height, second index is their B value (how many taller people are standing in front of them)
2) Traverse that sorted list in reversed order. If a person's B value is b > 0 ,
shift the person's position in the list b steps to the right (i.e. towards the taller people's direction).
Python code:
def sort_people(A, B):
sorted_persons = sorted(zip(A, B))
for idx, person in reversed(list(enumerate(sorted_persons))):
if person[1] > 0:
sorted_persons.pop(idx)
sorted_persons.insert(idx + person[1], person)
return zip(*sorted_persons)[0]
print sort_people([3, 2, 1], [0, 1, 1])
list pop() and insert() are O(n), so this solution is probably O(n²)
- ramibotros August 05, 2016
- ramibotros March 18, 2017