Last active
March 10, 2020 15:06
-
-
Save bruceoutdoors/5466912ce684b1bb3cc94d13ad292f20 to your computer and use it in GitHub Desktop.
infinitilab algo question
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# python3 | |
from collections import deque | |
# Store combinations as a tree. The size of the tree directly | |
# corresponds to the running time of the algorithm - O(2^n) | |
# Worst runtime is when the sum of items is larger than the target | |
# and no combination exist. An intuitive optimization here is to | |
# prune combinations away when the sum has already exceeded the target | |
class Node: | |
def __init__(self, val, total): | |
self.parent = None | |
self.val = val | |
self.total = total | |
def branch(self, val, total): | |
nod = Node(val, total) | |
nod.parent = self | |
return nod | |
# return array of indices of elements that sum to total. Instead of an | |
# exhaustive search, the algorithm returns the first match it finds | |
def find_target_combination(items, target): | |
# Good to shortcut our efforts if possible: | |
s = sum(items) | |
if s == target: | |
return items | |
elif s < target: | |
return [] | |
q = deque() | |
n = len(items) | |
# Initial population of root nodes | |
for i in range(len(items)): | |
total = items[i] | |
if total == target: | |
return [i] | |
elif total < target: | |
q.append(Node(i, total)) | |
while True: | |
if len(q) == 0: | |
break | |
nod = q.popleft() | |
total = nod.total | |
last = nod.val | |
for i in range(last + 1, n): | |
s = total + items[i] | |
if s == target: | |
# Leaf -> root to find indices; it is guaranteed | |
# indices will be in desc order | |
idxs = [i] | |
while nod is not None: | |
idxs.append(nod.val) | |
nod = nod.parent | |
return idxs | |
elif s < target: | |
q.append(nod.branch(i, s)) | |
return [] | |
print(find_target_combination([10, 20, 10, 10, 5, 30, 70], 75)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment