Hattori is very much inspired by the way GMAIL works. He decides to build his own simple version of GMAIL. He divides the mails into 3 categories ,namely : UNREAD , READ and TRASH.
UNREAD:the messages that haven't been read.
READ:The messages that is read by the user.
TRASH: The messages deleted by the user.
Now, At any point of time, The user can READ an UNREAD message , Move an UNREAD message to TRASH , Move a READ message to TRASH or restore a deleted message back to READ category.Now , Hattori requires your help in determining the messages left in all the categories aligned in the order of their arrival in that category.
Formally: You are given N messages , with ID from 1 to N. Initially all the messages are in the UNREAD section of the mail.Now, Q queries are given in the form as shown below:
1 X : Move the message with ID X from UNREAD to READ.
2 X : Move the message with ID X from READ to TRASH.
3 X : Move the message with ID X from UNREAD to TRASH.
4 X : Move the message with ID X from TRASH to READ.
Given that all the queries are valid, Help Hattori in Determining the messages in all the 3 sections. There are N mails initially having id's from 1 to N. Then there are total Q querieseach in the form mentioned in the question. The queries are mentioned in a list query where ith query is represented by (2*i)thand (2*i+1)th value of the list.Example 1:Input: N = 10, Q = 7query = {1, 2, 1, 5, 1, 7, 1, 9,         2, 5, 2, 7, 4, 5}Output: UNREAD - 1 3 4 6 8 10READ - 2 9 5TRASH - 7Explaination: Initial:UNREAD section: 1 2 3 4 5 6 7 8 9 10READ section : EMPTYTRASH section : EmptyQuery 1 : 1 2UNREAD section: 1 3 4 5 6 7 8 9 10READ section : 2TRASH section : EmptyQuery 2 : 1 5UNREAD section: 1 3 4 6 7 8 9 10READ section : 2 5TRASH section : EmptyQuery 3 : 1 7UNREAD section: 1 3 4 6 8 9 10READ section : 2 5 7TRASH section : EmptyQuery 4 : 1 9UNREAD section: 1 3 4 6 8 10READ section : 2 5 7 9TRASH section : EmptyQuery 5 : 2 5UNREAD section: 1 3 4 6 8 10READ section : 2 7 9TRASH section : 5Query 6 : 2 7UNREAD section: 1 3 4 6 8 10READ section : 2 9TRASH section : 5 7Query 7 : 4 5UNREAD section: 1 3 4 6 8 10READ section : 2 9 5TRASH section : 7Your Task:
You do not need to read input or print anyting. Your task is to complete the function mailDesign() which takes N, Q and query as input parameters and returns a list containing the starting pointer of the three linked lists unread, read and trash. If any linked list is empty pass a null pointer as the head of that list.Expected Time Complexity: O(Q*N)
Expected Auxiliary Space: O(N)Constraints:
1 < N, Q < 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3
# Given below is the structure of Node class
# list moves from left to right
# class node:
#     def __init__(self):
#         self.data = None
#         self.left = None
#         self.right = None

class Solution:
    def mailDesign(self, N, Q, query):
        # code here

Solutions:
class Solution:

	def mailDesign(self, N, Q, query):
		unread = [i + 1 for i in range(N)]
		cu = -1
		read = []
		cr = -1
		ct = -1
		trash = []

		def createll(l):
			start = None
			curr = None
			while l:
				if start == None:
					start = node()
					start.data = l.pop(0)
					curr = start
				else:
					c = node()
					c.data = l.pop(0)
					curr.right = c
					c.left = curr
					curr = c
			if start == None:
				start = node()
				start.data = 'EMPTY'
			return start
		for i in range(0, 2 * Q, 2):
			if query[i] == 1:
				c = query[i + 1]
				unread.remove(c)
				read.append(c)
			elif query[i] == 2:
				c = query[i + 1]
				read.remove(c)
				trash.append(c)
			elif query[i] == 3:
				c = query[i + 1]
				unread.remove(c)
				trash.append(c)
			elif query[i] == 4:
				c = query[i + 1]
				trash.remove(c)
				read.append(c)
		unr = createll(unread)
		rd = createll(read)
		tr = createll(trash)
		return [unr, rd, tr]


class Solution:

	def mailDesign(self, N, Q, query):
		marked = [0] * (N + 1)
		access = [0] * (N + 1)
		time = 1
		for i in range(Q):
			curr = query[2 * i + 1]
			access[curr] = time
			time += 1
			ops = query[2 * i]
			if ops == 1:
				marked[curr] = 1
			elif ops == 2:
				marked[curr] = 2
			elif ops == 3:
				marked[curr] = 2
			elif ops == 4:
				marked[curr] = 1
		sort = [[], [], []]
		for i in range(1, N + 1):
			sort[marked[i]].append((access[i], i))
		prev = [None, None, None]
		ans = [None, None, None]
		for i in range(3):
			sort[i].sort()
			for a in sort[i]:
				curr = node()
				curr.data = a[1]
				if not ans[i]:
					ans[i] = curr
				else:
					prev.right = curr
					curr.left = prev
				prev = curr
			if not ans[i]:
				ans[i] = node()
				ans[i].data = 'EMPTY'
		return ans


from collections import OrderedDict

class Solution:

	def mailDesign(self, N, Q, query):
		unread = OrderedDict()
		read = OrderedDict()
		trash = OrderedDict()
		for i in range(1, N + 1):
			unread[i] = 1
		for i in range(0, 2 * Q, 2):
			if query[i] == 1:
				del unread[query[i + 1]]
				read[query[i + 1]] = 1
			elif query[i] == 2:
				del read[query[i + 1]]
				trash[query[i + 1]] = 1
			elif query[i] == 3:
				del unread[query[i + 1]]
				trash[query[i + 1]] = 1
			elif query[i] == 4:
				del trash[query[i + 1]]
				read[query[i + 1]] = 1
		unread_start = node()
		head = unread_start
		for item in unread.keys():
			head.right = node()
			head = head.right
			head.data = item
		read_start = node()
		head = read_start
		for item in read.keys():
			head.right = node()
			head = head.right
			head.data = item
		trash_start = node()
		head = trash_start
		for item in trash.keys():
			head.right = node()
			head = head.right
			head.data = item
		empty = node()
		empty.data = 'EMPTY'
		if unread_start.right == None:
			unread_start.right = empty
		if read_start.right == None:
			read_start.right = empty
		if trash_start.right == None:
			trash_start.right = empty
		return [unread_start.right, read_start.right, trash_start.right]


class Solution:

	def insertToLinkList(self, List):
		LL = None
		tail = None
		head = None
		for item in List:
			n = node()
			n.data = item
			if LL == None:
				head = n
				LL = True
				tail = head
			else:
				tail.right = n
				tail = tail.right
		if head:
			LL = head
		else:
			n = node()
			n.data = 'EMPTY'
			LL = n
		return LL

	def mailDesign(self, N, Q, query):
		Read = list()
		Unread = [i for i in range(1, N + 1)]
		Trash = list()
		for i in range(0, len(query) - 1, 2):
			ID = query[i + 1]
			command = query[i]
			if command == 1:
				Read.append(ID)
				Unread.remove(ID)
			elif command == 2:
				Trash.append(ID)
				Read.remove(ID)
			elif command == 3:
				Trash.append(ID)
				Unread.remove(ID)
			elif command == 4:
				Read.append(ID)
				Trash.remove(ID)
			else:
				pass
		return list(map(self.insertToLinkList, [Unread, Read, Trash]))


def makeList(a):
	l = len(a)
	if l == 0:
		head = node()
		head.data = 'EMPTY'
		return head
	head = node()
	head.data = a[0]
	head.left = None
	p = head
	for i in range(1, l):
		p.right = node()
		p.right.data = a[i]
		p.right.left = p
		p = p.right
	return head

class Solution:

	def mailDesign(self, N, Q, query):
		if N == 1:
			unread = [1]
		else:
			unread = [i for i in range(1, N + 1)]
		read = []
		trash = []
		for i in range(0, Q * 2, 2):
			m = query[i]
			x = query[i + 1]
			if m == 1:
				unread.remove(x)
				read.append(x)
			elif m == 2:
				read.remove(x)
				trash.append(x)
			elif m == 3:
				unread.remove(x)
				trash.append(x)
			else:
				trash.remove(x)
				read.append(x)
		x = makeList(unread)
		y = makeList(read)
		z = makeList(trash)
		return [x, y, z]


class Solution:

	def delete_linked_list_node(self, nodee):
		prev = nodee.left
		next = nodee.right
		if prev is None:
			if next is None:
				return
			next.left = None
			return
		prev.right = next
		if next is None:
			return
		next.left = prev

	def mailDesign(self, N, Q, queries):
		unread = None
		current_unread = None
		read = None
		current_read = None
		trash = None
		current_trash = None
		unread = node()
		unread.data = 1
		current_unread = unread
		for i in range(2, N + 1):
			current_unread.right = node()
			current_unread.right.data = i
			current_unread.right.left = current_unread
			current_unread = current_unread.right
		for q in range(Q):
			query = queries[2 * q]
			value = queries[2 * q + 1]
			if query == 1:
				current_unread = unread
				while current_unread is not None:
					if current_unread.data == value:
						break
					else:
						current_unread = current_unread.right
				if current_unread == unread:
					unread = unread.right
				f = self.delete_linked_list_node(current_unread)
				if read is None:
					read = node()
					read.data = value
					current_read = read
				else:
					current_read = read
					while current_read.right is not None:
						current_read = current_read.right
					current_read.right = node()
					current_read.right.data = value
					current_read.right.left = current_read
					current_read = current_read.right
			elif query == 2:
				current_read = read
				while current_read is not None:
					if current_read.data == value:
						break
					else:
						current_read = current_read.right
				if current_read == read:
					read = read.right
				f = self.delete_linked_list_node(current_read)
				if trash is None:
					trash = node()
					trash.data = value
					current_trash = trash
				else:
					current_trash = trash
					while current_trash.right is not None:
						current_trash = current_trash.right
					current_trash.right = node()
					current_trash.right.data = value
					current_trash.right.left = current_trash
					current_trash = current_trash.right
			elif query == 3:
				current_unread = unread
				while current_unread is not None:
					if current_unread.data == value:
						break
					else:
						current_unread = current_unread.right
				if current_unread == unread:
					unread = unread.right
				f = self.delete_linked_list_node(current_unread)
				if trash is None:
					trash = node()
					trash.data = value
					current_trash = trash
				else:
					current_trash = trash
					while current_trash.right is not None:
						current_trash = current_trash.right
					current_trash.right = node()
					current_trash.right.data = value
					current_trash.right.left = current_trash
					current_trash = current_trash.right
			elif query == 4:
				current_trash = trash
				while current_trash is not None:
					if current_trash.data == value:
						break
					else:
						current_trash = current_trash.right
				if current_trash == trash:
					trash = trash.right
				f = self.delete_linked_list_node(current_trash)
				if read is None:
					read = node()
					read.data = value
					current_read = read
				else:
					current_read = read
					while current_read.right is not None:
						current_read = current_read.right
					current_read.right = node()
					current_read.right.data = value
					current_read.right.left = current_read
					current_read = current_read.right
		if unread is None:
			unread = node()
			unread.data = 'EMPTY'
		if read is None:
			read = node()
			read.data = 'EMPTY'
		if trash is None:
			trash = node()
			trash.data = 'EMPTY'
		return [unread, read, trash]


class Solution:

	def mailDesign(self, N, Q, query):
		self.unread_head = None
		self.read_head = None
		self.trash_head = None
		for i in range(1, N + 1):
			nodec = node()
			nodec.data = i
			if self.unread_head is None:
				self.unread_head = nodec
			else:
				last = self.unread_head
				while last.right != None:
					last = last.right
				last.right = nodec
				nodec.left = last
		for ele in range(0, len(query), 2):
			if query[ele] == 1:
				nodec = node()
				nodec.data = query[ele + 1]
				if self.read_head is None or self.read_head.data == 'EMPTY':
					self.read_head = nodec
				else:
					last = self.read_head
					while last.right != None:
						last = last.right
					last.right = nodec
					nodec.left = last
				temp = self.unread_head
				if temp.data == query[ele + 1]:
					if temp.right is not None:
						self.unread_head = temp.right
						self.unread_head.left = None
					else:
						self.unread_head = node()
						self.unread_head.data = 'EMPTY'
					continue
				while temp.right != None:
					temp1 = temp.right
					if temp1.data == query[ele + 1]:
						break
					temp = temp.right
				right_node = temp.right
				if right_node.right == None:
					temp.right = None
				else:
					right_node = right_node.right
					temp.right = right_node
					right_node.left = temp
			if query[ele] == 2:
				nodec = node()
				nodec.data = query[ele + 1]
				if self.trash_head is None or self.trash_head.data == 'EMPTY':
					self.trash_head = nodec
				else:
					last = self.trash_head
					while last.right != None:
						last = last.right
					last.right = nodec
					nodec.left = last
				temp = self.read_head
				if temp.data == query[ele + 1]:
					if temp.right is not None:
						self.read_head = temp.right
						self.read_head.left = None
					else:
						self.read_head = node()
						self.read_head.data = 'EMPTY'
					continue
				while temp.right != None:
					temp1 = temp.right
					if temp1.data == query[ele + 1]:
						break
					temp = temp.right
				right_node = temp.right
				if right_node.right == None:
					temp.right = None
				else:
					right_node = right_node.right
					temp.right = right_node
					right_node.left = temp
			if query[ele] == 3:
				nodec = node()
				nodec.data = query[ele + 1]
				if self.trash_head is None or self.trash_head.data == 'EMPTY':
					self.trash_head = nodec
				else:
					last = self.trash_head
					while last.right != None:
						last = last.right
					last.right = nodec
					nodec.left = last
				temp = self.unread_head
				if temp.data == query[ele + 1]:
					if temp.right is not None:
						self.unread_head = temp.right
						self.unread_head.left = None
					else:
						self.unread_head = node()
						self.unread_head.data = 'EMPTY'
					continue
				while temp.right != None:
					temp1 = temp.right
					if temp1.data == query[ele + 1]:
						break
					temp = temp.right
				right_node = temp.right
				if right_node.right == None:
					temp.right = None
				else:
					right_node = right_node.right
					temp.right = right_node
					right_node.left = temp
			if query[ele] == 4:
				nodec = node()
				nodec.data = query[ele + 1]
				if self.read_head is None or self.read_head.data == 'EMPTY':
					self.read_head = nodec
				else:
					last = self.read_head
					while last.right != None:
						last = last.right
					last.right = nodec
					nodec.left = last
				temp = self.trash_head
				if temp.data == query[ele + 1]:
					if temp.right is not None:
						self.trash_head = temp.right
						self.trash_head.left = None
					else:
						self.trash_head = node()
						self.trash_head.data = 'EMPTY'
					continue
				while temp.right != None:
					temp1 = temp.right
					if temp1.data == query[ele + 1]:
						break
					temp = temp.right
				right_node = temp.right
				if right_node is not None:
					if right_node.right == None:
						temp.right = None
					else:
						right_node = right_node.right
						temp.right = right_node
						right_node.left = temp
		return [self.unread_head, self.read_head, self.trash_head]

	def move_unread_to_read(self, element: int, unread_head, read_head):
		nodec = node()
		nodec.data = element
		if read_head is None:
			read_head = nodec
		else:
			last = read_head
			while last.right != None:
				last = last.right
			last.right = nodec
			nodec.left = last
		printlist(read_head)
		temp = unread_head
		while temp.right.data != element:
			temp = temp.right
		right_node = temp.right.right
		temp.right.right = right_node
		right_node.left = temp

	def move_read_to_trash(self, element: int, read_head, trash_head):
		pass

	def move_unread_to_trash(self, element: int, unread_head, trash_head):
		pass

	def move_trash_to_read(self, element: int, trash_head, read_head):
		pass


from collections import defaultdict, deque

class Solution:

	def mailDesign(self, N, Q, query):
		result = list()
		result.append(None)
		result.append(None)
		result.append(None)
		Read = list()
		Unread = [i for i in range(1, N + 1)]
		Trash = list()
		output = defaultdict(list)
		for i in range(0, len(query) - 1, 2):
			output[query[i + 1]].append(query[i])
			ID = query[i + 1]
			command = query[i]
			if command == 1:
				Read.append(ID)
				Unread.remove(ID)
			elif command == 2:
				Trash.append(ID)
				Read.remove(ID)
			elif command == 3:
				Trash.append(ID)
				Unread.remove(ID)
			elif command == 4:
				Read.append(ID)
				Trash.remove(ID)
			else:
				pass
		tail = None
		head = None
		for item in Unread:
			n = node()
			n.data = item
			if result[0] == None:
				head = n
				result[0] = True
				tail = head
			else:
				tail.right = n
				tail = tail.right
		if head:
			result[0] = head
		else:
			n = node()
			n.data = 'EMPTY'
			result[0] = n
		tail = None
		head = None
		for item in Read:
			n = node()
			n.data = item
			if result[1] == None:
				head = n
				tail = n
				result[1] = True
			else:
				tail.right = n
				tail = tail.right
		if head:
			result[1] = head
		else:
			n = node()
			n.data = 'EMPTY'
			result[1] = n
		tail = None
		head = None
		for item in Trash:
			n = node()
			n.data = item
			if result[2] == None:
				head = n
				tail = n
				result[2] = True
			else:
				tail.right = n
				tail = tail.right
		if head:
			result[2] = head
		else:
			n = node()
			n.data = 'EMPTY'
			result[2] = n
		return result