I'm trying to come up with a solution to this interview question:
You have a stream of RPC requests coming into a server which is being logged. Each log entry is of the form [id, timestamp, type ('Start' or 'End')]. Given a sequence of log entries and a timeout value, you need to figure out at the earliest possible time if an RPC call has timed out (e.g. print a message as soon as you detect such situation).
Example: Timeout = 3 id - time - type 0 - 0 - Start 1 - 1 - Start 0 - 2 - End 2 - 6 - Start # figured out id 1 had timed out at time 6 1 - 7 - End
I believe that my solution is O(NlogN)
, is there any way to improve it?
from sortedcontainers import SortedList
def process_log(log: list[list], timeout=3):
rpc_ids = {}
rpcs = SortedList()
for rpc_id, timestamp, action in log:
if action == 'Start':
rpcs.add([timestamp, rpc_id])
rpc_ids[rpc_id] = timestamp
else:
if rpc_id in rpc_ids:
entry = [rpc_ids[rpc_id], rpc_id]
if timestamp - rpc_ids[rpc_id] > timeout:
report_rpc(rpc_id, rpc_ids[rpc_id], timestamp)
del rpc_ids[rpc_id]
rpcs.remove(entry)
idx = rpcs.bisect_left([timestamp-timeout, float('inf')])
if idx > 0:
for i in range(idx):
start_time, rpc_id = rpcs[i]
report_rpc(rpc_id, start_time, timestamp)
del rpc_ids[rpc_id]
del rpcs[:idx]
def report_rpc(rpc_id, start_time, timestamp):
print(f'RPC #{rpc_id} started at {start_time} has timed out (@{timestamp})')
process_log([ # RPC #1 times out at timestamp 6
[0, 0, 'Start'],
[1, 1, 'Start'],
[0, 2, 'End'],
[2, 6, 'Start'],
[1, 7, 'End'],
])