0/1 Knapsack and Merge Sort | Dataford Interview Questions

Joveo needs to select campaign opportunities within a fixed budget and sort candidate scores for downstream ranking. Implement both tasks in one function: solve the 0/1 knapsack problem and sort an integer array using merge sort.

Each opportunity can be selected at most once. The knapsack result is the maximum total value whose total weight does not exceed the capacity. The sorting result must be in nondecreasing order and must not use Python's built-in sorting functions.

Formal Specification

Implement solve_knapsack_and_merge_sort(weights, values, capacity, nums).

weights and values are lists of integers with equal length.
weights[i] is the cost of opportunity i, and values[i] is its value.
capacity is the maximum total cost.
nums is a list of integers to sort.
Return a dictionary with keys max_value and sorted_nums.
max_value must be an integer, and sorted_nums must be a new sorted list.

Constraints

1 <= len(weights) = len(values) <= 500
0 <= capacity <= 10^4
1 <= weights[i] <= capacity when capacity > 0
0 <= values[i] <= 10^6
0 <= len(nums) <= 10^5
Do not call sorted() or .sort()

Function Signature

def solve_knapsack_and_merge_sort(weights, values, capacity, nums):

Your question is 0/1 Knapsack and Merge Sort. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem