fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. class Node
  6. {
  7. 	public:
  8. 	int data;
  9. 	Node * next;
  10. 	Node * prev;
  11. 	Node(int dataValue)
  12. 	{
  13. 		data = dataValue;
  14. 		next = NULL;
  15. 		prev = NULL;
  16.  
  17. 	}
  18. };
  19.  
  20. class DLL
  21. {
  22. 	public :
  23. 	Node * tail;
  24. 	Node * front;
  25. 	DLL()
  26. 	{
  27. 		tail=NULL;
  28. 		front = NULL;
  29. 	}
  30. 	Node * insertNode(int data)
  31. 	{
  32. 		Node* n = new Node(data);
  33. 		if(front==NULL)
  34. 		{
  35. 			front = tail = n;
  36. 		}
  37. 		else
  38. 		{
  39. 			Node * prevNode = tail;
  40. 			tail->next = n;
  41. 			tail = tail->next;
  42. 			tail->prev = prevNode;
  43. 		}
  44. 		return n;
  45. 	}
  46. 	void removeNode (Node * node)
  47. 	{
  48. 		if(node ==NULL)
  49. 		return;
  50. 		if(node->prev==NULL && node->next ==NULL)
  51. 		{
  52.  
  53. 			front = tail =NULL;
  54. 			delete(node);
  55. 		}
  56. 		else if(node->prev==NULL)
  57. 		{
  58. 			front = front->next;
  59. 			front-> prev = NULL;
  60. 			delete(node);
  61. 		}
  62. 		else if(node->next==NULL)
  63. 		{
  64. 			tail = node->prev;
  65. 			tail->next = NULL;
  66. 			delete(node);
  67. 		}
  68. 		else
  69. 		{
  70. 			Node * prevNode = node-> prev;
  71. 			Node * nextNode = node-> next;
  72. 			prevNode->next = nextNode;
  73. 			nextNode->prev =prevNode;
  74. 			delete(node);
  75. 		}
  76.  
  77. 	}
  78. };
  79.  
  80. class VisitorService
  81. {
  82. 	public :
  83. 	DLL list;
  84. 	unordered_map<int,Node *> nodeLocationOneTime;
  85. 	unordered_set<int> alreadyVisitedOnes;
  86.  
  87. 	void postVisitor(int x)
  88. 	{
  89. 		if(alreadyVisitedOnes.count(x))
  90. 		return;
  91. 		if(nodeLocationOneTime.count(x))
  92. 		{
  93. 			Node * nodeLoc = nodeLocationOneTime[x];
  94. 			list.removeNode(nodeLoc);
  95. 			nodeLocationOneTime.erase(x);
  96. 			alreadyVisitedOnes.insert(x);
  97. 		}
  98. 		else
  99. 		{
  100. 			Node * newNode = list.insertNode(x);
  101. 			nodeLocationOneTime[x]=newNode;
  102. 		}
  103. 	}
  104.  
  105. 	int firstTimeVisitor()
  106. 	{
  107. 		if(list.front!=NULL)
  108. 		{
  109. 			return list.front->data;
  110. 		}
  111. 		else
  112. 		return -1;
  113. 	}
  114.  
  115. };
  116.  
  117. int main() {
  118. 	// your code goes here
  119. 	VisitorService vs;
  120. 	vs.postVisitor(2);
  121. 	vs.postVisitor(3);
  122. 	vs.postVisitor(2);
  123. 	vs.postVisitor(5);
  124. 	vs.postVisitor(2);
  125. 	vs.postVisitor(3);
  126. 	vs.postVisitor(5);
  127. 	cout<<"First visitor is :"<<vs.firstTimeVisitor();
  128. 	return 0;
  129. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
First visitor is :-1
https://ideone.com/j9X0Y9
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!