[Coding test] 10. Recursion

Recursion is hard like for managing nested dictionaries or lists. But there is a general template where once u get the results of ur recursion,

dic - update() the results returned or override it completely via dic[key] = returned_val
list - extend() the results returned or append()

Merging 2 nested dics

so we check if both values of dic1 and dic2 for the same key are dict. Then we both keep the old values in dic1 while overriding the values that exisit in dic2 for that specific key

def merge_dict(dic1,dic2):
    ans=dic1.copy()
    for key,val in dic2.items():
        if key in dic1 and isinstance(dic1[key],dict) and isinstance(val,dict):
            ans[key] = merge_dict(dic1[key],dic2[key])
        else:
            ans[key]=val
    return ans


val = merge_dict({'a': 1, 'b': {'x': 10, 'y': 20}}, {'b': {'y': 30, 'z': 40}, 'c': 3})
print(val)
val = {'a': 1, 'b': {'x': 10, 'y': 30, 'z': 40}, 'c': 3}

merging 2 nested lists

def merge_nested_lst(lst1,lst2):
    ans=[]
    for a,b in zip(lst1,lst2):
        if isinstance(a,list) and isinstance(b,list):
            ans.append(merge_nested_lst(a,b))
        else:
            ans.append(a)
            ans.append(b)
    n = min(len(lst1),len(lst2))
    if len(lst1)>n:
        ans.extend(lst1[n:])
    if len(lst2)>n:
        ans.extend(lst2[n:])
    return ans


# Example
l1 = [1, [2, [3]]]
l2 = [4, [5, [6, [7]]]]

merged = merge_nested_lists(l1, l2)
print(merged)
# Output: [1, 4, [2, 5, [3, 6, [7]]]]

sum of nested list

def sum_nested_lst(lst):
    ans=0
    for i in range(len(lst)):
        if isinstance(lst[i],list):
            ans+= sum_nested_lst(lst[i])
        else:
            ans+=lst[i]
    return ans
val = sum_nested_lst([1, [2, [3, 4], 5], 6])
print(val)

flatten nested dic

def flatten_dic(dic,parent_key=""):
    ans={}
    for key,val in dic.items():
        new_key = parent_key+"."+key if parent_key else key
        if isinstance(val,dict):
            ans.update(flatten_dic(val,new_key))
        else:
            ans[new_key]=val
    return ans

merged = flatten_dic({"a": 1, "b": {"c": 2, "d": {"e": 3}}})
print(merged)
# Output: {'a': 1, 'b.c': 2, 'b.d.e': 3}