diff options
author | William Carroll <wpcarro@gmail.com> | 2020-11-12T14·37+0000 |
---|---|---|
committer | William Carroll <wpcarro@gmail.com> | 2020-11-12T14·37+0000 |
commit | aa66d9b83d5793bdbb7fe28368e0642f7c3dceac (patch) | |
tree | a0e6ad240fe1cdfd2fcdba7266931beea9fbe0d6 /scratch/facebook/camping-knapsack.py | |
parent | d2d772e43e0d4fb1bfaaa58d7de0c9e2cc274a25 (diff) |
Add coding exercises for Facebook interviews
Add attempts at solving coding problems to Briefcase.
Diffstat (limited to 'scratch/facebook/camping-knapsack.py')
-rw-r--r-- | scratch/facebook/camping-knapsack.py | 46 |
1 files changed, 46 insertions, 0 deletions
diff --git a/scratch/facebook/camping-knapsack.py b/scratch/facebook/camping-knapsack.py new file mode 100644 index 000000000000..add59ed409cd --- /dev/null +++ b/scratch/facebook/camping-knapsack.py @@ -0,0 +1,46 @@ +from utils import get, init_table, print_table + +def max_haul(capacity, items, names): + table = init_table(rows=len(items), cols=capacity, default=0) + items_table = init_table(rows=len(items), cols=capacity, default=[]) + for row in range(len(table)): + for col in range(len(table[row])): + kg, value = items[row] + curr_capacity = col + 1 + + if kg > curr_capacity: + a = 0 + else: + a = value + get(table, row - 1, curr_capacity - kg - 1) + b = get(table, row - 1, col) + + if a > b: + rest = get(items_table, row - 1, curr_capacity - kg - 1) + knapsack = [names.get(items[row])] + if rest: + knapsack += rest + else: + knapsack = get(items_table, row - 1, col) + + table[row][col] = max([a, b]) + items_table[row][col] = knapsack + print_table(table) + return items_table[-1][-1] + +water = (3, 10) +book = (1, 3) +food = (2, 9) +jacket = (2, 5) +camera = (1, 6) +items = [water, book, food, jacket, camera] +result = max_haul(6, items, { + water: 'water', + book: 'book', + food: 'food', + jacket: 'jacket', + camera: 'camera', +}) +expected = ['camera', 'food', 'water'] +print(result, expected) +assert result == expected +print("Success!") |