Nitish Garg
BAN USERdef find_parent(root, val):
if not root:
return None
if root.left and root.left.data == val:
return root
if root.right and root.right.data == val:
return root
find_left = find_parent(root.left, val)
if find_left:
return find_left
find_right = find_parent(root.right, val)
if find_right:
return find_right
return None
string = "3[a2[bd]g4[ef]h]"
def decoder(string, start=0):
decoded_string = ""
num = ""
i = start
while i < len(string):
x = string[i]
if x.isdigit():
num += x
i += 1
elif x.isalpha():
decoded_string += x
i += 1
elif x is "[":
temp, i = decoder(string, i+1)
decoded_string += temp*int(num)
num = ""
elif x is "]":
return decoded_string, i+1
return decoded_string
print decoder(string)
from collections import Counter
def check_sum(arr, k):
counter = Counter(arr)
for i, cnt in counter.items():
rem = k-i
if rem == i:
if cnt > 1:
return True
elif rem in counter:
return True
return False
arr = [1, 2, 2,3,4,5]
k = 6
print check_sum(arr, k)
def remove_triplicate(string):
res = ""
i = 0
while i < len(string):
if i < len(string) - 2 and string[i]*3 == string[i:i+3]:
i += 3
else:
res += string[i]
i += 1
if len(res) == len(string):
return res
else:
return remove_triplicate(res)
print remove_triplicate("aabbbacdddcccdcccdcc")
def merge(s1, s2, out):
if s1 == "":
print out+s2
return
if s2 == "":
print out+s1
return
merge(s1[1:], s2, out+s1[0])
merge(s1, s2[1:], out+s2[0])
merge("hey", "sam", "")
def print_padded_binaries(n):
format_str = "{0:{fill}" + str(n) + "b}"
for i in xrange(2**n):
print format_str.format(i, fill='0')
print_padded_binaries(3)
def special_insertion_sort(arr, k):
for i in xrange(1, len(arr)):
cur = arr[i]
j = i - 1
while j >= max(0, i - k) and cur < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = cur
arr = [4,3,2,1]
special_insertion_sort(arr, 2)
from itertools import combinations
def check_range(lb, ub, paint):
sets = set()
for i in xrange(len(lb)):
sets |= set(range(max(lb[i],paint[0]),\
min(ub[i],paint[1]) + 1))
if len(sets) == paint[1] - paint[0] + 1:
return True
else:
False
def minimize_cost(paint, costs):
min_cost = None
for i in xrange(1, len(costs) + 1):
for c in combinations(costs, i):
lb, ub, cost = zip(*c)
if check_range(lb, ub, paint):
cost_sum = sum(cost)
if not min_cost or min_cost > cost_sum:
min_cost = cost_sum
return min_cost
paint = [0, 5]
costs = [(0, 5, 10), (0, 4, 1), (0, 2,5), (2, 5, 1)]
print minimize_cost(paint, costs)
def print_pairs(n):
results = ["(1)"]
for i in xrange(2,n+1):
temp = []
for res in results:
temp.append(res[:-1] + str(i) + res[-1])
temp.append(res + "(" + str(i) + ")")
results = temp
return results
for pair in print_pairs(4):
print pair
from itertools import combinations
from collections import defaultdict
def find_good_number(n):
upper_bound = int(n**(1./3.))
cubes = [i**3 for i in xrange(upper_bound + 1)]
sums = defaultdict(list)
for i in combinations(cubes, 2):
sums[sum(i)].append(i)
result = [k for k,v in sums.items() if len(v) > 1 and k <= n]
return result
print find_good_number(5000)
def build_text_grid(w_list, row, col):
i = 0
j = 0
w = 0
words_num = 0
while i < row:
word = w_list[w]
added = False
if j == 0 and len(word) <= col:
j = len(word)
added = True
elif len(word) + 1 <= col - j:
j += len(word) + 1
added = True
else:
i += 1
j = 0
if added:
words_num += 1
w += 1
if w == len(w_list):
w = 0
return words_num
print build_text_grid(["do", "more"], 2, 20)
def check_toepliz(grid):
diag_val = dict()
for i in xrange(len(grid)):
for j in xrange(len(grid[0])):
diag = i - j
if diag not in diag_val:
diag_val[diag] = grid[i][j]
elif diag_val[diag] is not grid[i][j]:
return False
return True
grid = [[5,6,7],[4,5,6],[3,4,5]]
print check_toepliz(grid)
def zig_zag(matrix):
row = 0
col = 0
direction = 1
while col < len(matrix[0]):
while 0 <= row < len(matrix):
print matrix[row][col],
row += direction
row -= direction
direction = -1*direction
col += 1
m = [[1,2,3],[4,5,6],[7,8,9]]
zig_zag(m)
from collections import defaultdict
def get_hotels(scores, min_avg_score):
hotel_score = defaultdict(list)
for score in scores:
hotel_score[score['hotel_id']].append(score['score'])
hotel_avg = [key for key in hotel_score \
if sum(hotel_score[key])/len(hotel_score[key]) \
>= min_avg_score]
return hotel_avg
scores = [
{'hotel_id': 1001, 'user_id': 501, 'score': 7},
{'hotel_id': 1001, 'user_id': 502, 'score': 7},
{'hotel_id': 1001, 'user_id': 503, 'score': 7},
{'hotel_id': 2001, 'user_id': 504, 'score': 10},
{'hotel_id': 3001, 'user_id': 505, 'score': 5},
{'hotel_id': 2001, 'user_id': 506, 'score': 5}
]
print get_hotels(scores, 7)
from collections import Counter
def longest_palin(string):
cntr = Counter(string)
odd = False
palin = ""
for letter, cnt in cntr.items():
palin = letter*(cnt/2) + palin + letter*(cnt/2)
if not odd and cnt%2:
mid = len(palin)/2
palin = palin[:mid] + letter + palin[mid:]
odd = True
return palin
print longest_palin("ttaatbcgdjakkjgdtaat")
def min_moves(arr):
empty = len(arr) - 1
d0 = dict()
d1 = dict()
for i in xrange(len(arr) - 1):
if i + 1 != arr[i]:
d0[arr[i] - 1] = i
if i != arr[i]:
d1[arr[i]] = i
d = None
if len(d0) <= len(d1):
d = d0
else:
d = d1
moves = 0
while d:
moves += 1
if empty not in d:
key, val = d.items()[0]
d[key] = empty
empty = val
else:
temp = empty
empty = d[empty]
del d[temp]
return moves
a = [2,1,3,4, None]
b = [2,1,4,3, None]
print min_moves(a)
print min_moves(b)
"""
a c cc with b
0 -> 0 0 0 0
1 -> 1 1 0 1
2 -> 2 1 1 1(a + c + cc)*2
3 -> 4 2 1 2*(1(a + c + cc)+ 2(a + c + cc)*0(a + c + cc))
4 -> 7 4 2
5 -> 13 7 4
"""
def total_perms(n):
if n == 0:
return 0
if n == 1:
return 3
dp = [None]*(n+1)
s0 = (0, 0, 0)
s1 = (1, 1, 0)
dp[0] = (s0, 1)
dp[1] = (s1, sum(s1))
for i in xrange(2, n+1):
temp = (dp[i-1][1], dp[i-1][0][0], dp[i-1][0][1])
dp[i] = (temp, sum(temp))
perms = dp[-1][1]
for i in xrange(n):
perms += dp[i][1]*dp[n-1-i][1]
return perms
print total_perms(4)
from collections import defaultdict
class City(object):
def __init__(self, population):
self.population = population
def __str__(self):
return str(self.population)
class State(object):
def __init__(self):
self.cities = []
self.roads = defaultdict(list)
def add_cities(self, cities):
self.cities.extend(cities)
def add_road(self, c1, c2):
self.roads[c1].append(c2)
self.roads[c2].append(c1)
def get_max_traffic(self):
cache = dict()
for city in self.cities:
max_traffic = \
max([self.game_day_traffic(nbor, city, cache) \
for nbor in self.roads[city]])
yield str(city) + " " + str(max_traffic)
def game_day_traffic(self, from_city, to_city, cache):
key = (from_city, to_city)
if key not in cache:
cache[key] = from_city.population
for city in self.roads[from_city]:
if city is to_city: continue
else:
cache[key] += \
self.game_day_traffic(city, from_city, cache)
return cache[key]
c1 = City(1)
c2 = City(2)
c3 = City(3)
c4 = City(4)
c5 = City(5)
c7 = City(7)
c15 = City(15)
c8 = City(8)
c38 = City(38)
s = State()
s.add_cities([c1,c2,c3,c4,c5, c7, c15, c8, c38])
s.add_road(c1,c5)
s.add_road(c2,c5)
s.add_road(c4,c5)
s.add_road(c3,c5)
s.add_road(c2,c7)
s.add_road(c2,c15)
s.add_road(c7,c8)
s.add_road(c8,c38)
for max_traffic in s.get_max_traffic() :
print max_traffic
from collections import defaultdict
class Graph(object):
def __init__(self, nodes):
self.nodes = nodes
self.edges = defaultdict(list)
self.weights = []
def add_edge(self, u, v, weight):
self.edges[u].append(v)
self.edges[v].append(u)
self.weights.append((weight, (u,v)))
def weight_sum(self):
result = 0
for w, (u, v) in self.weights:
s1 = self.sub_graph_size(u, v)
s2 = self.nodes - s1
result += w*s1*s2
return result
def sub_graph_size(self, u, v):
cnt = 1
for edge in self.edges[u]:
if edge is v: continue
else:
cnt += self.sub_graph_size(edge, u)
return cnt
g = Graph(6)
g.add_edge(0, 1, 1)
g.add_edge(1, 2, 2)
g.add_edge(1, 3, 3)
g.add_edge(0, 4, 4)
g.add_edge(0, 5, 5)
print g.weight_sum()
class SparseMatrix(object):
def __init__(self):
self.vals = dict()
def set_val(self, row, col, val):
self.vals[(row, col)] = val
def sum_matrix(self, row, col):
result = 0
if len(self.vals) < (row+1)*(col+1):
for i, j in self.vals:
if i <= row and j <= col:
result += self.vals[(i, j)]
else:
for i in xrange(row+1):
for j in xrange(col+1):
if (i, j) in self.vals:
result += self.vals[(i, j)]
return result
sm = SparseMatrix()
sm.set_val(1,1,10)
sm.set_val(2,3,10)
print sm.sum_matrix(3,3)
def find_sum(l1, l2, val):
search_dict = set(l2)
for x in l1:
if val - x in search_dict:
return True
return False
a = [1,2,3,4,5,6,7,8,9,10]
b = [11,12,13,14,15,16,17,18,19,20]
print find_sum(a, b, 15)
a = [4, 5, 10, 1, 2, 7, 11, 8, 9]
b = a[:]
b.sort(reverse=True)
moves = len(a)
last_index = None
for i in xrange(len(b)):
cur_index = a.index(b[i])
if not last_index or cur_index < last_index:
last_index = cur_index
moves -= 1
else:
break
print len(a), moves
from collections import deque
a = [-3, -1, 2, 4]
neg = deque()
pos = deque()
for x in a:
if x < 0: neg.append(x**2)
else: pos.appendleft(x**2)
final = []
while neg or pos:
if not pos: final.append(neg.pop())
elif not neg: final.append(pos.pop())
elif neg[-1] > pos[-1]: final.append(pos.pop())
else: final.append(neg.pop())
print final
from collections import Counter
times = [(1,4), (6,8), (2, 4), (7,9), (10,15)]
room = Counter()
for time in times:
room[time[0]] += 1
room[time[1]] -= 1
room = room.items()
room.sort(key=lambda k:k[0])
count = 0
tv = 0
last_event = 0
for event in room:
if count:
tv += (event[0] - last_event)
last_event = event[0]
count += event[1]
print tv
def check_next_level(arr, i, j, depth):
if depth > i or depth > i \
or depth > len(arr)-1-i or depth > len(arr[0])-1-j:
return False
if arr[i-depth][j] and arr[i+depth][j] \
and arr[i][j-depth] and arr[i][j+depth]:
return True
return False
a = [[0,0,1,0,0], [0,0,1,0,0],[1,1,1,1,1],[0,0,1,0,0],[0,0,1,0,0]]
max_depth = 0
max_loc = None
for i in xrange(len(a)):
for j in xrange(len(a[0])):
depth = 1
while check_next_level(a, i, j, depth):
if depth > max_depth:
max_depth = depth
max_loc = (i, j)
depth += 1
print max_depth, max_loc
def get_leaves(pre_order, leaves):
if not pre_order:
return
root = pre_order[0]
if len(pre_order) == 1:
leaves.append(root)
return
left_start = None
left_end = None
right_start = None
righ_end = None
for i in xrange(1, len(pre_order)):
if not left_start and pre_order[i] <= root:
left_start = i
if not right_start and pre_order[i] > root:
right_start = i
if left_start:
if right_start: left_end = right_start
else: left_end = len(pre_order)
get_leaves(pre_order[left_start:left_end], leaves)
if right_start:
right_end = len(pre_order)
get_leaves(pre_order[right_start:right_end], leaves)
a = [5, 3, 2, 1, 4, 7, 6, 8]
a_leaves =[]
get_leaves(a, a_leaves)
print a_leaves
def spiral(self):
head = self.head
while head:
cur = head.next
pre = None
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
head.next = pre
head = pre
def product(*args):
prod = [[]]
for arg in args:
prod = [x + [y] for x in prod for y in arg]
return prod
a = [[1,2,3], [4,5,6], [7,8,9]]
print product(*a)
def calculate_glass_fill(litre, row):
litre_used = ((row)*(row - 1))/2
litre_left = float(max(0, (litre - litre_used)))
return min(1.0, litre_left/row)
print calculate_glass_fill(524, 32)
def pick_elems(arr):
arr_len = len(arr)
sol = [1]*arr_len
for i in xrange(1, arr_len):
for j in xrange(i):
if abs(a[i] - a[j]) <= abs(i- j):
sol[i] = max(sol[i], sol[j] + 1)
print max(sol)
a = [1,3,5,4]
pick_elems(a)
def find_min_max(arr):
if not arr: return None, None
if len(arr) == 1: return arr[0], arr[0]
sort_start = None
sort_end = None
rsort_start = None
rsort_end = None
for i in xrange(1, len(arr)):
if i == 1:
if arr[1] >= arr[0]:
sort_start = 0
else:
rsort_start = 0
else:
if sort_start is not None and a[i] < a[i - 1]:
sort_end = i-2
rsort_start = i -1
rsort_end = len(arr) - 1
break
if rsort_start is not None and a[i] > a[i - 1]:
rsort_end = i-2
sort_start = i -1
sort_end = len(arr) - 1
break
if sort_start is not None and sort_end is None:
return arr[sort_start], arr[-1]
if rsort_start is not None and rsort_end is None:
return arr[-1], arr[rsort_start]
return min(arr[sort_start], arr[rsort_end]), max(arr[rsort_start], arr[sort_end])
a = [5,4,-1, -10, 1,2,3,4,5,6]
print find_min_max(a)
from random import randint
def find_valid_number(a, i, j):
while True:
rand = randint(1, 4)
if j >= 2 and a[i][j-2] == a[i][j-1] \
and a[i][j-1] == rand:
continue
if i >= 2 and a[i-2][j] == a[i-1][j] \
and a[i-1][j] == rand:
continue
return rand
def generate_matrix(n):
a = []
for i in xrange(n):
for j in xrange(n):
if j == 0:
a.append([])
a[i].append(find_valid_number(a, i, j))
for row in a:
print " ".join(map(str, row))
generate_matrix(10)
def min_moves(parking, desired):
cars = dict()
free_spot = None
for i in xrange(len(parking)):
if parking[i] == -1:
free_spot = i
elif parking[i] is not desired[i]:
cars[parking[i]] = (i, None)
for i in xrange(len(parking)):
if desired[i] in cars:
cars[desired[i]] = (cars[desired[i]][0], i)
swaps = dict()
for car in cars:
swaps[cars[car][1]] = cars[car][0]
num_swaps = 0
while swaps:
if free_spot in swaps:
temp = free_spot
free_spot = swaps[free_spot]
del swaps[temp]
else:
first = swaps.items()[0]
swaps[first[0]] = free_spot
free_spot = first[1]
num_swaps += 1
return num_swaps
p = [1, 2, 3, -1, 4, 5]
d = [5, -1, 2, 3, 1, 4]
print min_moves(p, d)
def longest_phrase(a, n):
max_words = 0
start = 0
end = 1
while end < len(a):
sum_chars = sum(a[start:end])
print sum_chars, start, end
if sum_chars <= n:
end += 1
else:
max_words = max(max_words, end -1 - start)
start += 1
if sum(a[start:end]) <= n:
max_words = max(max_words, end - start)
else:
max_words = max(max_words, end -1 - start)
return max_words
a = [1,4,7]
print longest_phrase(a, 5)
from collections import defaultdict
class Graph(object):
def __init__(self, n):
self.nodes = range(1, n+1)
self.edges = defaultdict(list)
self.distances = dict()
for i in self.nodes:
for j in self.nodes:
self.edges[i].append(-j)
for i in self.nodes:
for j in self.nodes:
self.distances[(i,j)] = 2
def add_edge(self, u, v, dist):
self.edges[u][v-1] = -1*self.edges[u][v-1]
self.edges[v][u-1] = -1*self.edges[v][u-1]
self.distances[(u, v)] = dist
self.distances[(v, u)] = dist
def dijkstra(self, start, end):
unvisited = dict()
for node in self.nodes:
unvisited[node] = None
unvisited[-node] = None
visited = dict()
cur = start
dist = 0
unvisited[cur] = dist
while unvisited:
visited[cur] = unvisited[cur]
del unvisited[cur]
for nbor in self.edges[abs(cur)]:
if cur < 0:
if nbor < 0: continue
else: nbor = -nbor
if nbor in visited: continue
new_dist = dist + self.distances[(abs(cur), abs(nbor))]
if unvisited[nbor] == None \
or unvisited[nbor] > new_dist:
unvisited[nbor] = new_dist
if unvisited:
candidates = [node for node in unvisited.items() if node[1]]
candidates.sort(key=lambda k:k[1])
cur, dist = candidates[0]
return min(visited[end], visited[-end])
g = Graph(5)
g.add_edge(1, 2, 2)
g.add_edge(1, 4, 4)
g.add_edge(2, 3, 1)
g.add_edge(3, 4, 3)
g.add_edge(4, 5, 1)
print g.dijkstra(1, 4)
lamps = [(0,0), (2,3), (1,5)]
rows = set([i for i, j in lamps])
cols = set([j for i,j in lamps])
pos_diags = set([i + j for i,j in lamps])
neg_diags = set([i - j for i,j in lamps])
points = [(1,1), (8,1), (5,6), (8,9), (9,8)]
for i, j in points:
if i in rows: print True
elif j in cols: print True
elif i + j in pos_diags: print True
elif i - j in neg_diags: print True
else: print False
class Node(object):
def __init__(self, data):
self.data = data
self.child = []
def longest_seq(self):
seq = []
cnt = 1 + self.longest_seq_helper(-1) + self.longest_seq_helper(1)
seq.append(cnt)
for child in self.child:
seq.append(child.longest_seq())
return max(seq)
def longest_seq_helper(self, direction):
data = self.data
seq = [0]
for child in self.child:
cnt = 0
if child.data - data == direction:
cnt += 1
cnt += child.longest_seq_helper(direction)
seq.append(cnt)
return max(seq)
def format_string(s, k):
if k == 0:
return s
s = s.replace("-", "")
index = len(s)%k
if index == 0:
index = k
while index < len(s):
s = s[:index] + "-" + s[index:]
index += 1 + k
return s
s = "24-A0sjf-jdjf-293#j"
print format_string(s, 5)
from collections import defaultdict
dictionary = ["hello", "to", "the", "world"]
def unscramble(s, sorted_dictionary=None):
if not sorted_dictionary:
sorted_dictionary = defaultdict(list)
for word in dictionary:
sorted_dictionary["".join(sorted(word))].append(word)
words = []
for i in xrange(len(s)):
word = "".join(sorted(s[:i+1]))
if len(sorted_dictionary[word]):
word = sorted_dictionary[word][0]
other_words = unscramble(s[i+1:], sorted_dictionary)
if len(other_words) or i+1 == len(s):
words.append(word)
words.extend(other_words)
break
return words
s = "elhloothtedrowl"
words = unscramble(s)
print " ".join(words)
class Node(object):
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def all_root_to_leaf(self):
paths = []
data = str(self.data)
if not self.left and not self.right:
paths.append(data)
else:
child_paths = []
if self.left:
child_paths.extend(self.left.all_root_to_leaf())
if self.right:
child_paths.extend(self.right.all_root_to_leaf())
for path in child_paths:
paths.append(data + "->" + path)
return paths
from collections import deque, defaultdict
town = [
["#", "#", "#", "#", "#", "#", "#"],
["#", "", "", "A", "#", "", "#"],
["#", "", "", "", "", "", "#"],
["#", "", "", "", "", "", "#"],
["#", "", "B", "", "", "", "#"],
["#", "", "", "", "#", "C", "#"],
["#", "#", "#", "#", "#", "#", "#"]
]
def find_houses(town):
houses = []
for i in xrange(len(town)):
for j in xrange(len(town[0])):
if town[i][j] != "#" and town[i][j] != "":
houses.append(((i,j),town[i][j]))
return houses
def possible_moves(location, town):
moves = []
i = location[0]
j = location[1]
if i is not 0 and town[i-1][j] == "":
moves.append((i-1, j))
if i is not len(town) - 1 and town[i+1][j] == "":
moves.append((i+1, j))
if j is not 0 and town[i][j-1] == "":
moves.append((i, j-1))
if j is not len(town[0]) - 1 and town[i][j+1] == "":
moves.append((i, j+1))
return moves
def find_meeting_point(town):
houses = find_houses(town)
q = deque(houses)
points = defaultdict(set)
while q:
cur = q.popleft()
moves = possible_moves(cur[0], town)
for move in moves:
if cur[1] not in points[move]:
points[move].add(cur[1])
if len(points[move]) == len(houses):
return move
q.append((move, cur[1]))
print find_meeting_point(town)
def find_pivot(a):
sum_left = 0
sum_right = sum(a)
for pivot in xrange(len(a) + 1):
if pivot == 0:
sum_right -= a[pivot]
elif pivot == len(a):
sum_left += a[pivot - 1]
else:
sum_right -= a[pivot]
sum_left += a[pivot - 1]
if sum_right == sum_left:
print sum_right, sum_left
return pivot
return -1
arr = [-1,1,5]
print find_pivot(arr)
def find_gaps(a):
start = 0
end = 99
gaps = []
for x in a:
if x == start + 1:
gaps.append(str(start))
elif x is not start:
gaps.append(str(start) + "-" + str(x-1))
start = x + 1
if start == end:
gaps.append(str(start))
elif start < end:
gaps.append(str(start) + "-" + str(end))
return gaps
arr = [1,2, 3, 5, 10,11, 88, 98]
print find_gaps(arr)
from random import random
def random_permutation(n):
numbers = [i for i in xrange(1, n+1)]
print numbers
for i in xrange(n):
random_index = int(random()*n)
temp = numbers[i]
numbers[i] = numbers[random_index]
numbers[random_index] = temp
return numbers
print random_permutation(10)
from math import atan2, degrees
def max_viewing_angle(points, v):
angles = [degrees(atan2(y, x)) for x,y in points]
angles.sort()
start = 0
end = 0
max_points = None
while end < len(angles):
if max_points == None:
max_points = (end-start, angles[start])
diff = angles[end] - angles[start]
if diff <= v:
end += 1
else:
start += 1
points = end - start
if points > max_points[0]:
max_points = (points, angles[start])
return max_points[1] + v/2
points = [(1,1), (3,1), (2,1), (1,2), (-2,5), (-1,6), (1,3), (-1,3), (0,4)]
v = 45.0
print max_viewing_angle(points, v)
def possible_sums(coins, cache):
if len(coins) == 0:
return [0]
key = len(coins)
if key not in cache:
cache[key] = []
coin = coins[0]
for i in xrange(coin[0] + 1):
coin_sum = coin[1]*i
other_sums = possible_sums(coins[1:], cache)
for os in other_sums:
cache[key].append(os + coin_sum)
return cache[key]
coins = [(5, 10), (3, 50), (2, 100), (2, 500)]
print possible_sums(coins, dict())
def buy_cheap_str(str_needed, opponents, cache):
if str_needed <= 0:
return 0
key = str(str_needed) + ":" + str(len(opponents))
if key not in cache:
opp_1 = opponents[0]
if len(opponents) == 1:
if opp_1[0] < str_needed:
cache[key] = 99999999999
else:
cache[key] = opp_1[1]
else:
with_opp_1 = buy_cheap_str(str_needed - opp_1[0], opponents[1:], cache) + opp_1[1]
without_opp_1 = buy_cheap_str(str_needed, opponents[1:], cache)
cache[key] = min(with_opp_1, without_opp_1)
return cache[key]
def fight(person, opponents):
sum_str = sum([s for s, p in opponents ])
cur_str = person[0]
cur_money = person[1]
str_diff = sum_str - cur_str
str_needed = (str_diff + str_diff%2)/2
money_spent = buy_cheap_str(str_needed, opponents, dict())
return cur_money - money_spent
print fight((100,100), [(107,10),(107,15),(260,40),(52,20)])
s1 = [1,1,100,3]
s2 = [200,2,3,1]
s3 = [10,1,4]
def find_max_sum(s_arr, n):
if n == 0:
return 0
if len(s_arr) == 1:
return sum(s_arr[0][-n:])
# Assume no term is picked form the first stack
max_sum = find_max_sum(s_arr[1:], n)
first_stack = s_arr[0]
for i in range(1,n+1):
stack_sum = sum(first_stack[-i:])
rem_sum = find_max_sum(s_arr[1:], n-i)
if stack_sum + rem_sum > max_sum:
max_sum = stack_sum + rem_sum
return max_sum
print find_max_sum([s1,s2,s3], 3)
def find_ceo(company_struct):
except_ceo = set()
for manager in company_struct:
team = company_struct[manager]
except_ceo |= set(team)
for manager in company_struct:
if manager not in except_ceo:
return manager
def print_team(company_struct, manager=None, depth=0):
if not manager:
manager = find_ceo(company_struct)
print " "*depth + "-" + manager
if manager in company_struct:
for mates in company_struct[manager]:
print_team(company_struct, mates, depth + 1)
print_team(mgmt)
- Nitish Garg January 20, 2017