新面筋，合并2个排序stream

给两个inputstream，已经排好序，合并相同的key，并且把values进行归并求和。具体题目如下，一般是按merge sort的方式写，这样是linear time和O（1）空间，但麻烦的重复的元素和尾部处理，调试了半天也没通过，希望大家指点一下

"""
There are two large files containing SORTED key value pairs, where keys are strings and values are integers. e.g.

File 1:

aaa: 1
bbb: 5
bbb: 3
ccc: 2

File 2:

bbb: 9
ccc: 10
ddd: 11

We want to merge the two files together to produce an output file where keys are still sorted. Consecutive pairs with the same key in the output are merged, by summing up their values. e.g. merging the files above produces the output:

aaa: 1
bbb: 17
ccc: 12
ddd: 11

"""


# API t

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

## test ########
data1 = (("aaa", 1), ("bbb", 5), ("bbb", 3), ("ccc", 2))
data2 = (("bbb", 9), ("ccc", 10), ("ddd", 11))
input1 = InputStream(data1)
input2 = InputStream(data2)
output = OutputStream()
merge_input_files(input1, input2, output)
print("-----")
print(output._data)

重复元素你可以不马上塞到output里。用一个key value pair暂时存着，直到input1和input2里挑出来的新的key value pair的key和暂时存的不同才把之前的pair塞进output里。如果是重复key，那就直接更新暂存的key value pair。
尾部没啥特别需要处理的吧，就是保证一个input结束之后另一个input还能继续。

1. def merge_input_files(input_1: InputStream, input_2: InputStream, output: OutputStream):
   
2.     cur, prev, cur_val, val = "", "", 0, 0
   
3.     while input_1.is_valid() or input_2.is_valid():
   
4.         data1 = input_1.read()
   
5.         data2 = input_2.read()
   
6. 
   
7.         if cur == prev:
   
8.             val += cur_val
   
9.             # print(f"val : {val} cur_val: {cur_val}")
   
10.         else:
    
11.             if prev:
    
12.                 output.write((prev, val))
    
13.             prev, val = cur, cur_val
    
14.         
    
15.         if not input_1.is_valid():
    
16.             cur, cur_val = data2
    
17.             input_2.next()
    
18.             continue
    
19.         
    
20.         if not input_2.is_valid():
    
21.             cur, cur_val = data1
    
22.             input_1.next()
    
23.             continue
    
24. 
    
25.         if data1[0] <= data2[0]:
    
26.             cur, cur_val = data1
    
27.             input_1.next()
    
28.         else:
    
29.             cur, cur_val = data2
    
30.             input_2.next()
    
31.    
    
32.     output.write((prev, val))

复制代码

我写的是这个代码，但结果也是有些问题，大家能指点么

请问楼主, 可以不用范例里的read模式吗? 可以的话用heap写会轻松很多.

qqzz 发表于 2022-1-25 16:21
重复元素你可以不马上塞到output里。用一个key value pair暂时存着，直到input1和input2里挑出来的新的key  ...

Is this for phone interview or VO?

@heyho666 硬度人在投面筋吧，所有回复都是英语

heyho666 发表于 2022-1-26 18:25
Is this for phone interview or VO?

I am not OP.

OP, is that for VO or phone screen?

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

heyho666 发表于 2022-1-26 15:25
Is this for phone interview or VO?

天竺老哥你咋还没面啊。。。