In operating systems that use paging for memory management, page replacement algorithm is needed to decide which page needs to be replaced when the new page comes in. Whenever a new page is referred and is not present in memory, the page fault occurs and Operating System replaces one of the existing pages with a newly needed page. 
Given a sequence of pages in an array pages[] of length N and memory capacity C, find the number of page faults using Least Recently Used (LRU) Algorithm. 
Note:- Before solving this example revising the OS LRU cache mechanism is recommended.
Example 1:
Input: N = 9, C = 4
pages = {5, 0, 1, 3, 2, 4, 1, 0, 5}
Output: 8
Explaination: memory allocated with 4 pages 5, 0, 1, 
3: page fault = 4
page number 2 is required, replaces LRU 5: 
page fault = 4+1 = 5
page number 4 is required, replaces LRU 0: 
page fault = 5 + 1 = 6
page number 1 is required which is already present: 
page fault = 6 + 0 = 6
page number 0 is required which replaces LRU 3: 
page fault = 6 + 1 = 7
page number 5 is required which replaces LRU 2: 
page fault = 7 + 1  = 8.
Your Task:
You do not need to read input or print anything. Your task is to complete the function pageFaults() which takes N, C and pages[] as input parameters and returns the number of page faults.
Expected Time Complexity: O(N*C)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 1000
1 ≤ C ≤ 100
1 ≤ pages[i] ≤ 1000

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms
Expected Time Complexity: O(N*C)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

    def pageFaults(self, N, C, pages):

        # code here

Solutions:
class Solution:

	def pageFaults(self, N, C, pages):
		lru = []
		fault = 0
		for x in pages:
			if x not in lru:
				if len(lru) < C:
					lru.append(x)
				else:
					lru.pop(0)
					lru.append(x)
				fault += 1
			else:
				lru.remove(x)
				lru.append(x)
		return fault


class Solution:

	def pageFaults(self, N, C, pages):
		q = []
		faults = 0
		for page in pages:
			if page not in q:
				faults += 1
				if len(q) == C:
					q.pop(0)
				q.append(page)
			else:
				q.remove(page)
				q.append(page)
		return faults


from collections import deque

class Solution:

	def pageFaults(self, N, C, pages):
		faults = 0
		que = deque()
		counter = 0
		for ind in range(len(pages)):
			if pages[ind] not in que:
				faults += 1
				if counter == C:
					que.popleft()
					counter -= 1
				que.append(pages[ind])
				counter += 1
			else:
				que.remove(pages[ind])
				que.append(pages[ind])
		return faults


class Solution:

	def pageFaults(self, N, C, pages):
		LRU = []
		fault = 0
		for i in pages:
			if i not in LRU:
				if len(LRU) < C:
					LRU.append(i)
				else:
					LRU.pop(0)
					LRU.append(i)
				fault += 1
			else:
				LRU.remove(i)
				LRU.append(i)
		return fault


class Solution:

	def pageFaults(self, N, C, pages):
		count = 0
		v = []
		for i in range(N):
			if pages[i] not in v:
				if len(v) == C:
					v.pop(0)
				v.append(pages[i])
				count += 1
			else:
				v.remove(pages[i])
				v.append(pages[i])
		return count


class Solution:

	def pageFaults(self, n, c, pages):
		count = 0
		v = []
		for i in range(n):
			if pages[i] not in v:
				if len(v) == c:
					v.pop(0)
				v.append(pages[i])
				count += 1
			else:
				v.remove(pages[i])
				v.append(pages[i])
		return count


class Solution:

	def pageFaults(self, n, c, pages):
		q = []
		f = 0
		for x in range(n):
			if pages[x] in q:
				q.remove(pages[x])
				q.append(pages[x])
			if len(q) < c and pages[x] not in q:
				q.append(pages[x])
			elif pages[x] not in q:
				f += 1
				q.pop(0)
				q.append(pages[x])
		start = min(len(q), c)
		return start + f


class Solution:

	def pageFaults(self, N, C, pages):
		ans = 1
		Carr = []
		Carr.append(pages[0])
		lenc = 1
		for i in range(1, N):
			pagefault = True
			if pages[i] in Carr:
				Carr.remove(pages[i])
				Carr.append(pages[i])
				pagefault = False
			if pagefault == False:
				continue
			ans += 1
			if lenc < C:
				Carr.append(pages[i])
				lenc += 1
				continue
			Carr.pop(0)
			Carr.append(pages[i])
		return ans


def page_faults(n, c, pages):
	lru_map = {}
	lru_queue = []
	lru_size = 0
	fault = 0
	for i in range(0, n):
		page = pages[i]
		if page not in lru_map:
			fault = fault + 1
			if lru_size < c:
				lru_queue.append(page)
				lru_size = lru_size + 1
				lru_map[page] = lru_size - 1
			else:
				front = lru_queue.pop(0)
				lru_size = lru_size - 1
				del lru_map[front]
				lru_queue.append(page)
				lru_size = lru_size + 1
				lru_map[page] = lru_size - 1
				for j in range(0, len(lru_queue)):
					lru_map[lru_queue[j]] = j
		else:
			index = lru_map[page]
			lru_queue = lru_queue[0:index] + lru_queue[index + 1:]
			lru_queue.append(page)
			lru_map[page] = lru_size - 1
			for j in range(0, len(lru_queue)):
				lru_map[lru_queue[j]] = j
	return fault

class Solution:

	def pageFaults(self, N, C, pages):
		return page_faults(N, C, pages)


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None
		self.prev = None

class Solution:

	def pageFaults(self, n, c, pages):
		faults = 0
		mp = dict()
		head = None
		tail = None
		size = 0
		for i in range(n):
			if pages[i] not in mp:
				faults += 1
				if size == c:
					mp.pop(head.data)
					head = head.next
					size -= 1
				newNode = Node(pages[i])
				if head == None:
					head = newNode
					tail = head
				tail.next = newNode
				newNode.prev = tail
				tail = tail.next
				size += 1
				mp[pages[i]] = newNode
			else:
				node = mp[pages[i]]
				if node.data == head.data:
					head = head.next
					node.prev = tail
					tail.next = node
					tail = tail.next
				elif tail.data != node.data:
					node.prev.next = node.next
					node.next.prev = node.prev
					node.prev = tail
					tail.next = node
					tail = tail.next
				mp[pages[i]] = tail
		return faults


class Solution:

	def pageFaults(self, N, C, pages):
		frame = []
		ans = 0
		for i in range(N):
			if pages[i] not in frame:
				if len(frame) < C:
					frame.append(pages[i])
				elif len(frame) == C:
					frame.pop(0)
					frame.append(pages[i])
				ans += 1
			else:
				frame.remove(pages[i])
				frame.append(pages[i])
		return ans


class Node:

	def __init__(self, data, next=None, prev=None):
		self.data = data
		self.next = None
		self.prev = None

class lruDLL:

	def __init__(self, capacity):
		self.capacity = capacity
		self.head = Node(-1)
		self.tail = Node(-1, None, self.head)
		self.head.next = self.tail
		self.length = 0
		self.record = set()

	def add(self, page):
		if page in self.record:
			temp = self.head
			while temp.data != page:
				temp = temp.next
			temp.prev.next = temp.next
			temp.next.prev = temp.prev
			nxt = self.head.next
			self.head.next = temp
			temp.prev = self.head
			temp.next = nxt
			nxt.prev = temp
			return 0
		else:
			self.record.add(page)
			new = Node(page)
			if self.length == self.capacity:
				last = self.tail.prev
				self.record.remove(last.data)
				last.prev.next = self.tail
				self.tail.prev = last.prev
				nxt = self.head.next
				self.head.next = new
				new.prev = self.head
				new.next = nxt
				nxt.prev = new
			else:
				nxt = self.head.next
				self.head.next = new
				new.prev = self.head
				new.next = nxt
				nxt.prev = new
				self.length += 1
			return 1

class Solution:

	def pageFaults(self, N, C, pages):
		O = lruDLL(C)
		ans = 0
		for i in range(N):
			ans += O.add(pages[i])
		return ans


class Node:

	def __init__(self, val):
		self.val = val
		self.next = None
		self.prev = None

class LRU:

	def __init__(self, capacity):
		self.lookup = dict()
		self.capacity = capacity
		self.head = Node(-1)
		self.tail = Node(-1)
		self.head.next = self.tail
		self.tail.prev = self.head

	def __add(self, node):
		last = self.tail.prev
		last.next = node
		node.prev = last
		node.next = self.tail
		self.tail.prev = node

	def __remove(self, node):
		prev = node.prev
		nxt = node.next
		prev.next = nxt
		nxt.prev = prev
		node.prev = None
		node.next = None

	def get(self, val):
		if val not in self.lookup:
			return False
		node = self.lookup[val]
		self.__remove(node)
		self.__add(node)
		return True

	def insert(self, val):
		if val in self.lookup:
			return False
		node = Node(val)
		if len(self.lookup) == self.capacity:
			first = self.head.next
			del self.lookup[first.val]
			self.__remove(first)
		self.__add(node)
		self.lookup[val] = node
		return True

class Solution:

	def pageFaults(self, N, C, pages):
		lru = LRU(C)
		count = 0
		for p in pages:
			if lru.get(p):
				continue
			count += 1
			lru.insert(p)
		return count


class Solution:

	def pageFaults(self, N, C, pages):
		l = []
		pf = 0
		for x in pages:
			if x not in l and len(l) < C:
				l.append(x)
				pf += 1
			elif x in l:
				l.remove(x)
				l.append(x)
			else:
				l.remove(l[0])
				l.append(x)
				pf += 1
		return pf


class Solution:

	def pageFaults(self, N, C, pages):
		window = []
		fault = 0
		for i in range(len(pages)):
			if len(window) <= C and pages[i] not in window:
				fault += 1
				if len(window) >= C:
					window.pop(0)
				window.append(pages[i])
			else:
				window.remove(pages[i])
				window.append(pages[i])
		return fault


class Solution:

	def pageFaults(self, N, C, pages):
		ans = 0
		l = []
		for x in pages:
			if x in l:
				l.remove(x)
				l.append(x)
			else:
				if len(l) < C:
					l.append(x)
				else:
					l.remove(l[0])
					l.append(x)
				ans += 1
		return ans


from collections import deque

class Solution:

	def pageFaults(self, N, C, pages):
		q = deque()
		fault = 0
		for page in pages:
			if page in q:
				q.remove(page)
				q.append(page)
			elif len(q) < C:
				q.append(page)
				fault += 1
			elif len(q) == C:
				q.popleft()
				q.append(page)
				fault += 1
		return fault


class Solution:

	def pageFaults(self, N, C, pages):
		cache = []
		count = 0
		for i in range(N):
			if pages[i] not in cache:
				count += 1
				if len(cache) >= C:
					cache.pop(0)
				cache.append(pages[i])
			else:
				cache.pop(cache.index(pages[i]))
				cache.append(pages[i])
		return count


class Solution:

	def pageFaults(self, N, C, pages):
		q = []
		count = 0
		for i in range(N):
			if pages[i] not in q:
				if len(q) == C:
					q.pop(0)
				q.append(pages[i])
				count += 1
			elif pages[i] in q:
				q.remove(pages[i])
				q.append(pages[i])
		return count


from collections import OrderedDict

class Solution:

	def pageFaults(self, N, c, pages):
		d = OrderedDict()
		count = 0
		for i in range(N):
			if len(d) == c:
				if d.get(pages[i]) != None:
					del d[pages[i]]
					d[pages[i]] = True
				if d.get(pages[i]) == None:
					for j in d.keys():
						l = j
						break
					del d[l]
					d[pages[i]] = True
					count = count + 1
			if d.get(pages[i]) != None:
				del d[pages[i]]
				d[pages[i]] = True
			if d.get(pages[i]) == None:
				d[pages[i]] = True
				count = count + 1
		return count


class Solution:

	def pageFaults(self, N, C, pages):
		page_faults = 0
		memory = {}
		queue = []
		for page in pages:
			if page in memory:
				queue.remove(page)
				queue.append(page)
			else:
				page_faults += 1
				if len(memory) == C:
					lru_page = queue.pop(0)
					del memory[lru_page]
				memory[page] = True
				queue.append(page)
		return page_faults


class Solution:

	def pageFaults(self, N, C, pages):
		s = []
		processList = pages
		capacity = C
		pageFaults = 0
		for i in processList:
			if i not in s:
				if len(s) == capacity:
					s.remove(s[0])
					s.append(i)
				else:
					s.append(i)
				pageFaults += 1
			else:
				s.remove(i)
				s.append(i)
		return pageFaults


from collections import deque

class Solution:

	def pageFaults(self, N, C, pages):
		memory = deque()
		pgfault = 0
		for i in range(0, N):
			if pages[i] not in memory:
				if len(memory) == C:
					memory.popleft()
				pgfault += 1
				memory.append(pages[i])
			else:
				memory.remove(pages[i])
				memory.append(pages[i])
		return pgfault


class Solution:

	def pageFaults(self, N, C, pages):
		memory = []
		pgfault = 0
		for i in range(0, N):
			if pages[i] not in memory:
				if len(memory) == C:
					memory.pop(0)
				pgfault += 1
				memory.append(pages[i])
			else:
				memory.remove(pages[i])
				memory.append(pages[i])
		return pgfault


from collections import deque

class Solution:

	def pageFaults(self, N, C, pages):
		q = deque()
		count = 0
		capacity = 0
		for i in pages:
			if i not in q:
				if capacity < C:
					q.append(i)
					capacity += 1
				else:
					q.popleft()
					q.append(i)
				count += 1
			else:
				q.remove(i)
				q.append(i)
		return count


class Solution:

	def pageFaults(self, N, C, pages):
		Ans = 0
		cache = []
		for i in range(N):
			if len(cache) == C:
				if pages[i] in cache:
					cache.append(cache.pop(cache.index(pages[i])))
				else:
					Ans += 1
					cache.pop(0)
					cache.append(pages[i])
			elif pages[i] in cache:
				cache.append(cache.pop(cache.index(pages[i])))
			else:
				cache.append(pages[i])
				Ans += 1
		return Ans


class DoublyLinkedList:

	def __init__(self, key, val):
		self.key = key
		self.val = val
		self.prev = None
		self.next = None

class LRUCache:

	def __init__(self, capacity: int):
		self.capacity = capacity
		self.hashmap = dict()
		self.head = DoublyLinkedList(0, 0)
		self.tail = DoublyLinkedList(0, 0)
		self.head.next = self.tail
		self.tail.prev = self.head

	def get(self, key: int) -> int:
		if key in self.hashmap:
			node = self.hashmap[key]
			self.removeNode(node)
			self.add_node_at_the_end(node)
			return node.val
		return -1

	def put(self, key: int, value: int) -> None:
		if key in self.hashmap:
			self.removeNode(self.hashmap[key])
		node = DoublyLinkedList(key, value)
		self.add_node_at_the_end(node)
		self.hashmap[key] = node
		if len(self.hashmap) > self.capacity:
			removeNode = self.head.next
			self.removeNode(removeNode)
			del self.hashmap[removeNode.key]

	def removeNode(self, node):
		prev = node.prev
		nexti = node.next
		prev.next = nexti
		nexti.prev = prev

	def add_node_at_the_end(self, node):
		prev = self.tail.prev
		prev.next = node
		self.tail.prev = node
		node.next = self.tail
		node.prev = prev

class Solution:

	def pageFaults(self, N, C, pages):
		lru_cache = LRUCache(C)
		faults = 0
		for i in range(N):
			if lru_cache.get(pages[i]) != -1:
				continue
			faults += 1
			lru_cache.put(pages[i], pages[i])
		return faults


class Solution:

	def pageFaults(self, N, C, pages):
		q = []
		c = 0
		for i in range(N):
			if pages[i] not in q:
				if len(q) == C:
					q.pop(0)
				c += 1
				q.append(pages[i])
			else:
				q.remove(pages[i])
				q.append(pages[i])
		return c


from collections import deque

class Solution:

	def pageFaults(self, N, c, l):
		d = deque()
		x = 0
		h = 0
		for i in range(len(l)):
			if l[i] not in d and len(d) < c:
				d.append(l[i])
				x += 1
			elif l[i] not in d and len(d) == c:
				d.append(l[i])
				d.popleft()
				x += 1
			elif l[i] in d and len(d) < c:
				d.remove(l[i])
				d.append(l[i])
			elif l[i] in d and len(d) == c:
				d.remove(l[i])
				d.append(l[i])
		return x


from collections import OrderedDict

class Solution:

	def pageFaults(self, N, C, pages):
		l = OrderedDict()
		pagefaults = 0
		for i in pages:
			if i not in l:
				if C == 0:
					l.popitem(last=False)
					C = 1
				l[i] = 1
				pagefaults += 1
				C -= 1
			else:
				del l[i]
				l[i] = 1
		return pagefaults


class Solution:

	def pageFaults(self, n, c, a):
		cache = []
		f = 0
		for i in a:
			found = -1
			for j in range(len(cache)):
				if cache[j] == i:
					found = j
					break
			if found == -1:
				f += 1
				if len(cache) == c:
					cache.pop(0)
				cache.append(i)
			else:
				cache.pop(j)
				cache.append(i)
		return f


from collections import OrderedDict

class Solution:

	def pageFaults(self, N, C, pages):
		cache = OrderedDict()
		count = 0
		for item in pages:
			if item in cache:
				cache.move_to_end(item)
			else:
				count += 1
				cache[item] = 1
			if len(cache) > C:
				cache.popitem(last=False)
		return count


class Solution:

	def pageFaults(self, N, C, pages):
		stack = []
		cnt = 0
		for i in range(N):
			if pages[i] not in stack:
				if len(stack) == C:
					stack.pop(0)
				cnt += 1
			else:
				stack.remove(pages[i])
			stack.append(pages[i])
		return cnt


class Solution:

	def pageFaults(self, N, C, pages):
		arr = []
		map_ = {}
		count = 0
		for page in pages:
			if page not in arr:
				if len(arr) == C:
					p = arr.pop(0)
					del map_[p]
				arr.append(page)
				map_[page] = len(arr) - 1
				count += 1
			else:
				for (i, ele) in enumerate(arr):
					if ele == page:
						break
				arr.pop(i)
				arr.append(page)
				map_[page] = len(arr) - 1
		return count


class Solution:

	def pageFaults(self, N, C, pages):
		return f(pages, C)
from collections import deque

def f(arr, c):
	counter = 0
	d = set()
	dll = deque()
	for item in arr:
		try:
			d.remove(item)
			dll.remove(item)
		except KeyError:
			counter += 1
		d.add(item)
		dll.append(item)
		if len(dll) > c:
			item = dll.popleft()
			d.remove(item)
	return counter


class Solution:

	def pageFaults(self, N, C, pages):
		p = []
		pf = 0
		for i in pages:
			if i not in p:
				if len(p) == C:
					p.pop(0)
					p.append(i)
				else:
					p.append(i)
				pf += 1
			else:
				p.remove(i)
				p.append(i)
		return pf


class Solution:

	def pageFaults(self, N, C, pages):
		cache = []
		size = 0
		ans = 0
		for i in pages:
			if i in cache:
				cache.remove(i)
				cache.append(i)
			else:
				ans += 1
				if size >= C:
					cache.pop(0)
				cache.append(i)
				size += 1
		return ans


class Solution:

	def pageFaults(self, N, C, pages):
		arr = []
		fault = 0
		for i in pages:
			if i not in arr:
				if len(arr) == C:
					arr.pop(0)
				arr.append(i)
				fault += 1
			elif i in arr:
				arr.remove(i)
				arr.append(i)
		return fault


class Solution:

	def pageFaults(self, n, cap, pages):
		dic = {}
		cache = []
		count = 0
		for page in pages:
			if cap:
				if dic.get(page, False):
					cache.remove(page)
					cache.append(page)
				else:
					count += 1
					cap -= 1
					cache.append(page)
					dic[page] = True
			elif dic.get(page, False):
				cache.remove(page)
				cache.append(page)
			else:
				count += 1
				ele = cache.pop(0)
				del dic[ele]
				cache.append(page)
				dic[page] = True
		return count


class Solution:

	def pageFaults(self, N, C, pages):
		faults = 0
		arr = []
		for i in range(0, N):
			if pages[i] not in arr:
				if len(arr) == C:
					arr.pop(0)
				faults += 1
			else:
				arr.remove(pages[i])
			arr.append(pages[i])
		return faults


class Solution:

	def pageFaults(self, N, C, pages):
		resar = []
		res = 0
		for i in pages:
			if i not in resar:
				if len(resar) == C:
					resar.pop(0)
				resar.append(i)
				res += 1
			elif i in resar:
				resar.remove(i)
				resar.append(i)
		return res


class Solution:

	def pageFaults(self, N, C, pages):
		fault = 0
		d = {}
		lru = []
		for i in range(len(pages)):
			if pages[i] in lru:
				lru.remove(pages[i])
			else:
				if len(lru) >= C:
					lru.pop(0)
				fault += 1
			lru += [pages[i]]
		return fault


class Solution:

	def pageFaults(self, n, c, pg):
		ls = []
		pf = 0
		for i in pg:
			if i not in ls:
				pf += 1
				if len(ls) == c:
					ls.pop(0)
					ls.append(i)
				else:
					ls.append(i)
			else:
				ls.remove(i)
				ls.append(i)
		return pf


class Solution:

	def pageFaults(self, n, c, pages):
		s = []
		pagefaults = 0
		for i in pages:
			if i not in s:
				if len(s) == c:
					s.remove(s[0])
					s.append(i)
				else:
					s.append(i)
				pagefaults += 1
			else:
				s.remove(i)
				s.append(i)
		return pagefaults


from collections import deque

class Solution:

	def pageFaults(self, N, C, pages):
		ans = 0
		arr = []
		for i in pages:
			if i not in arr:
				if len(arr) < C:
					arr.append(i)
				else:
					arr.pop(0)
					arr.append(i)
				ans += 1
			else:
				arr.remove(i)
				arr.append(i)
		return ans


INT_MAX = (1 << 63) - 1

class Solution:

	def pageFaults(self, N, C, pages):
		memory = set()
		mp = {}
		pg_fault = 0
		for i in range(N):
			if len(memory) < C:
				if pages[i] not in memory:
					pg_fault += 1
					memory.add(pages[i])
			elif pages[i] not in memory:
				pg_fault += 1
				lru = INT_MAX
				old_page = -1
				for page in memory:
					if mp[page] < lru:
						lru = mp[page]
						old_page = page
				memory.remove(old_page)
				memory.add(pages[i])
			mp[pages[i]] = i
		return pg_fault


class Solution:

	def pageFaults(self, N, C, pages):
		string = pages
		frame_ = []
		size = C
		(hits, faults) = (0, 0)
		for idx in range(len(string)):
			if string[idx] in frame_:
				hits += 1
			else:
				faults += 1
				if len(frame_) == size:
					storage = []
					for i in string[:idx][::-1]:
						if len(storage) == size - 1:
							break
						elif i not in storage:
							storage.append(i)
					frame_.remove([i for i in frame_ if i not in storage][0])
				frame_.append(string[idx])
		return faults


from collections import deque

class Solution:

	def pageFaults(self, N, C, pages):
		mem = set()
		q = deque()
		faults = 0
		i = 0
		for p in pages:
			if p not in mem:
				if len(q) < C:
					q.append(p)
					mem.add(p)
				else:
					lru = q.popleft()
					mem.remove(lru)
					q.append(p)
					mem.add(p)
				faults += 1
			else:
				q.remove(p)
				q.append(p)
		return faults


import sys

class Solution:

	def pageFaults(self, N, C, pages):
		ind = {}
		s = set()
		fault = 0
		for i in range(N):
			if len(s) < C:
				if pages[i] not in s:
					fault += 1
					s.add(pages[i])
				ind[pages[i]] = i
			else:
				if pages[i] not in s:
					mini = 1001
					val = 1001
					for j in s:
						if ind[j] < mini:
							mini = ind[j]
							val = j
					s.discard(val)
					s.add(pages[i])
					fault += 1
				ind[pages[i]] = i
		return fault


class Solution:

	def pageFaults(self, n, C, pages):
		c = {}
		maxi = 0
		count = 0
		for i in range(n):
			if pages[i] not in c:
				count += 1
				c[pages[i]] = maxi
				maxi += 1
			elif pages[i] in c:
				c[pages[i]] = maxi
				maxi += 1
			if len(c) > C:
				lru = min(c, key=c.get)
				del c[lru]
		return count


class CacheNode:

	def __init__(self):
		self.prev = None
		self.next = None
		self.value = None
		self.end = None
		self.key = 0
		self.valid = False

class CacheList:

	def __init__(self, no_print=True):
		self.end = None
		self.head = None
		self.nodes = None
		self.no_print = no_print

	def show_list(self, head):
		if self.no_print:
			return
		cur = head
		i = 0
		while cur:
			print('[%d]: key=%d, Value=%d' % (i, cur.key, cur.value))
			cur = cur.next
			i += 1

	def remove(self, node):
		if self.head == node:
			self.head = node.next
		if self.end == node:
			self.end = node.prev
		if node.next:
			node.next.prev = node.prev
		if node.prev:
			node.prev.next = node.next

	def append(self, node):
		node.next = None
		node.prev = None
		node.valid = True
		if self.end:
			self.end.next = node
			node.prev = self.end
			self.end = node
		else:
			self.end = node
			self.head = node
		self.show_list(self.head)

	def alloc(self):
		node = None
		if self.nodes:
			node = self.nodes
			self.nodes = node.next
		else:
			node = self.head
			self.remove(node)
		return node

	def add(self, node):
		if self.nodes:
			node.next = self.nodes
			self.nodes.prev = node
			self.nodes = node
		else:
			self.nodes = node

class LRUClassHash:

	def __init__(self, cap):
		self.cap = cap
		self.clist = CacheList()
		self.map = {}
		for i in range(cap):
			node = CacheNode()
			node.value = 0
			node.key = -i
			self.clist.add(node)
		self.clist.show_list(self.clist.nodes)

	def get(self, key):
		if key in self.map:
			self.clist.remove(self.map[key])
			self.clist.append(self.map[key])
			return self.map[key].value
		return -1

	def set(self, key, value):
		node = None
		if key in self.map:
			node = self.map[key]
			i = 0
			for (k, n) in self.map.items():
				i += 1
			self.clist.remove(node)
		else:
			node = self.clist.alloc()
		if node:
			if node.valid and node.key in self.map:
				self.map.pop(node.key)
			node.key = key
			node.value = value
			node.valid = True
			self.map[key] = node
			self.clist.append(node)

class Solution:

	def pageFaults(self, N, C, pages):
		lru = LRUClassHash(C)
		pf_cnt = 0
		for i in range(N):
			if lru.get(pages[i]) < 0:
				pf_cnt += 1
				lru.set(pages[i], i)
		return pf_cnt


from collections import OrderedDict

class Solution:

	def pageFaults(self, N, C, pages):
		d = OrderedDict()
		pagefaults = 0
		for i in range(len(pages)):
			if pages[i] in d:
				d.move_to_end(pages[i])
			else:
				d[pages[i]] = i
				pagefaults += 1
				if len(d) > C:
					d.popitem(last=False)
		return pagefaults


class Solution:

	def pageFaults(self, n, c, pages):
		arr = []
		ans = 0
		for page in pages:
			try:
				arr.remove(page)
			except:
				ans += 1
				if len(arr) == c:
					arr.pop(0)
			finally:
				arr.append(page)
		return ans


class Solution:

	def pageFaults(self, n, c, a):
		(l, d) = ([], {})
		f = 0
		for i in range(n):
			if c:
				if not d.get(a[i], False):
					f += 1
					l.append(a[i])
					d[a[i]] = True
					c -= 1
				else:
					l.remove(a[i])
					l.append(a[i])
			elif not d.get(a[i], False):
				f += 1
				del d[l.pop(0)]
				l.append(a[i])
				d[a[i]] = True
			else:
				l.remove(a[i])
				l.append(a[i])
		return f


class Solution:

	def pageFaults(self, N, C, pages):
		count = 0
		LRU = []
		min_index = 0
		page_fault = 0
		for page in pages:
			min_count = float('inf')
			flag = False
			for (i, ele) in enumerate(LRU):
				if ele[0] == page:
					LRU[i] = [page, count]
					count += 1
					flag = True
					break
				if ele[1] < min_count:
					min_count = ele[1]
					min_index = i
			if not flag:
				if len(LRU) < C:
					LRU.append([page, count])
				else:
					LRU[min_index] = [page, count]
				count += 1
				page_fault += 1
		return page_fault


from collections import OrderedDict

class Solution:

	def pageFaults(self, N, C, pages):
		m = OrderedDict()
		c = 0
		for i in pages:
			if i not in m:
				c += 1
				m[i] = 1
			else:
				m.move_to_end(i)
			if len(m) > C:
				m.popitem(last=False)
		return c


class Solution:

	def pageFaults(self, N, C, pages):
		count = 0
		mem = []
		for ele in pages:
			if ele not in mem:
				if len(mem) == C:
					mem.pop(0)
				mem.append(ele)
				count += 1
			else:
				mem.remove(ele)
				mem.append(ele)
		return count