Queue

2 minute read

The Problem

Implement Logger:

interface Logger { 

	* When a process starts, it calls 'start' with processId and startTime.
	*/
	void start(String processId, long startTime);
	
	/**
	* When the same process ends, it calls 'end' with processId and endTime.
	*/
	void end(String processId, long endTime);

	/**
	* Prints the logs of this system sorted by the start time of processes in the below format
	* {processId} started at {startTime} and ended at {endTime}
	*/
	void print();
}

Example:

Logger log = new MyLogger();
log.start("1", 100);
log.start("2", 101);  
log.end("2", 102);
log.start("3", 103);
log.end("1", 104);
log.end("3", 105);
log.print();

Output: 
1 started at 100 and ended at 104
2 started at 101 and ended at 102
3 started at 103 and ended at 105

The Solution

It’s important to point out that a process ID will not be printed if the process with lower ID has not ended, for instance:

Logger log = new MyLogger();
log.start("1", 100);
log.start("2", 101);  
log.end("2", 102);
log.start("3", 103);
log.end("3", 105);
log.print();

Calling print() will not print anything since process ID 1 has not ended.

We made 2 observations:

  1. The start time of lower ID will occur first but the end time can be in any order.
  2. We still need to keep track of process ID that we have seen the end time.

For observation 2, we can use hash table or set as we have discuss in previous section to keep track of processes that we have seen, specifically we will store the end time since the end time tells us that about the processes that have ended.

When print() is called, we have to keep printing from the lowest available process Id untill the process that has not ended, and this needs to be printed in the order such that the process will start first will be displayed first. We see that this follow the sequence “start first, displayed first”, the sequence somehow similar to the pattern “first in, first out” which is a property of the queue data structure.

from collections import dequeue

class logger:
	def __init__(self):
		self.queue = deque()
		self.hash_table = {}

	def start (process_id, start_time):
		self.queue.appendleft((process_id,start_time))

	def end (process_id, end_time):
		self.hash_table[process_id] = end_time

	def print ():
		while self.queue[-1][process_id] in self.hash_table:
			process_id, start_time = self.queue.pop()
			end_time =  self.hash_table[process_id]
			print(process_id + "started at " + start_time + " and ended at " + end_time)

The Analysis

The solution looks short and simple to analyze, 1 operation for every start() and end() call, so both of them will be in O(1). For print function, the worst situation is when you print everything from the queue.

Usually a problem requires to use queue data structure is quite easy to code, the most difficult part is to recognize the usage of queue to solve the problem.

Updated:

Leave a comment