0

Given two lists need to map keys and values respectively such that maximum keys should have equal number of values.

Example: Input :

['a', 'b', 'c', 'd']
[3,2,8,4,7,9,0,4,5,6,7]

Output:

{'a':[3,2,8], 'b':[4,7,9], c:[0,4,5], 'd':[6,7]}

What could to be a good algorithm for this problem ? I was not able to write any code hence not providing any. Any help is highly appreciated.

Mad Physicist
  • 107,652
  • 25
  • 181
  • 264
Ankur Shrivastava
  • 39
  • 5
  • Kris, thanks for editing it ! can you help ? – Ankur Shrivastava Dec 22 '21 at 15:03
  • Your desired output is not clear. If the value list had 9 entries instead of 11, you could split it into sublists of (3, 3, 3, 0), (0, 3, 3, 3), (2, 2, 2, 3), or (3, 2, 2, 2) elements. In all cases, three keys have the same number of list elements. So, which one should it be? – Mr. T Dec 22 '21 at 15:48
  • oh, i am sorry. Let us assume each key should have at least one value. This removes the 1st two choices. and whether it is (2,2,2,3) or (3,2,2,2) should not matter in case of a dictionary, i guess specially for this problem. – Ankur Shrivastava Dec 22 '21 at 16:16
  • There is a difference between `{'a':[3,2,8], 'b':[4,7], c:[9,0], 'd':[4,5]}` (3,2,2,2) and `{'a':[3,2], 'b':[8, 4], c:[7,9], 'd':[0,4,5]}` (2,2,2,3). It is still unclear whether you want a splitting such as A) `(n+1, n+1, ...., n+1, n, n, n,..., n)` for the largest possible `n` or B) `(n, n, n, ..., n, k)` for the largest `n` with `k≤n`. – Mr. T Dec 22 '21 at 16:44
  • As pointed by you above, I will assume that there can be more than one solution. I just want to understand how to come up with an algorithm which will split in any one of the above solutions. Or in general how can we distribute values across keys in similar kind of problems. – Ankur Shrivastava Dec 22 '21 at 17:18
  • 1
    Ah, this question is just about the general approach. There are numerous methods listed in [this duplicate](https://stackoverflow.com/questions/312443/how-do-you-split-a-list-into-evenly-sized-chunks). You just have to build a dictionary by combining the keys with the sublists. – Mr. T Dec 22 '21 at 17:22

1 Answers1

0
from typing import List, Dict

def solution(keys: List[int], values: List[int]) -> Dict:
    """
    returns the dict of key/values such that maximum keys have equal number of values
    """
    resulting_dict = {}
    average_value_counts = round(len(values) / len(keys))
    if len(values) / average_value_counts > len(keys):
        average_value_counts += 1
    for index, stepper in enumerate(range(0, len(values), average_value_counts)):
        ending_index = stepper + average_value_counts
        ending_index = ending_index if ending_index < len(values) else len(values)
        resulting_dict[keys[index]] = values[stepper: ending_index]
    return resulting_dict
Amit Khetan
  • 58
  • 7