fork download
copy 
  1. # // Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
  2.  
  3. # // Implement the LRUCache class:
  4.  
  5. # // LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  6. # // int get(int key) Return the value of the key if the key exists, otherwise return -1.
  7. # // void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
  8. # // The functions get and put must each run in O(1) average time complexity.
  9.  
  10.  
  11.  
  12. # // Example 1:
  13.  
  14. # // Input
  15. # // ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
  16. # // [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
  17. # // Output
  18. # // [null, null, null, 1, null, -1, null, -1, 3, 4]
  19.  
  20. # // Explanation
  21. # // LRUCache lRUCache = new LRUCache(2);
  22. # // lRUCache.put(1, 1); // cache is {1=1}
  23. # // lRUCache.put(2, 2); // cache is {1=1, 2=2}
  24. # // lRUCache.get(1);    // return 1
  25. # // lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
  26. # // lRUCache.get(2);    // returns -1 (not found)
  27. # // lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
  28. # // lRUCache.get(1);    // return -1 (not found)
  29. # // lRUCache.get(3);    // return 3
  30. # // lRUCache.get(4);    // return 4
  31.  
  32.  
  33. # // Constraints:
  34.  
  35. # // 1 <= capacity <= 3000
  36. # // 0 <= key <= 104
  37. # // 0 <= value <= 105
  38. # // At most 2 * 105 calls will be made to get and put.
  39.  
  40.  
  41. # [1, 2] <- 3
  42. # [2,3]
  43. # [3,2]
  44. # [1, 3, 4 , 2] 
  45.  
  46. class LinkedListNode:
  47.     def __init__(self, key, val):
  48.         self.key = key
  49.         self.val = val
  50.         self.prev = None
  51.         self.next = None
  52.  
  53.     def updateValue(self, val):
  54.         self.val = val
  55.  
  56. class LinkedList:
  57.     def __init__(self):
  58.         self.llHead = LinkedListNode(-1, -1)
  59.         self.llTail = LinkedListNode(-1, -1)
  60.         self.llHead.next = self.llTail
  61.         self.llTail.prev = self.llHead
  62.  
  63.  
  64.     def getHead(self):
  65.         return self.llHead.next if self.llHead.next != self.llTail else None
  66.  
  67.     def addValue(self, key, val):
  68.         node = LinkedListNode(key, val)
  69.         self.addNodeToEnd(node)
  70.  
  71.     def addNodeToEnd(self, node):
  72.         currentTail = self.llTail.prev
  73.         # handle next
  74.         self.llTail.prev = node
  75.         node.next = self.llTail
  76.         # handle prev
  77.         currentTail.next = node
  78.         node.prev = currentTail
  79.  
  80.  
  81.     def moveNodeToEnd(self, node):
  82.         self.deleteNodeFromList(node)
  83.         self.addNodeToEnd(node)
  84.  
  85.  
  86.     def deleteNodeFromList(self, node):
  87.         nodePrev = node.prev
  88.         nodeNext = node.next
  89.         nodePrev.next = nodeNext
  90.         nodeNext.prev = nodePrev
  91.         node.prev = None
  92.         node.next = None
  93.  
  94.  
  95.  
  96. class LRU:
  97.     def __init__(self, capacity):
  98.         self.capacity = capacity
  99.         self.linkedList = LinkedList()
  100.         self.nodesMap = dict()
  101.  
  102.     def put(self, key, value):
  103.         if key in self.nodesMap:
  104.             node = self.nodesMap.get(key)
  105.             node.updateValue(value)
  106.             self.linkedList.moveNodeToEnd(node)
  107.         else:
  108.             if len(self.nodesMap) == self.capacity:
  109.                 lrNode = self.linkedList.getHead()
  110.                 self.linkedList.deleteNodeFromList(lrNode)
  111.                 self.nodesMap.pop(lrNode.key)
  112.             newNode = LinkedListNode(key, value)
  113.             self.nodesMap[key] = newNode
  114.             self.linkedList.addNodeToEnd(newNode)
  115.  
  116.  
  117.     def get(self, key):
  118.         if key not in self.nodesMap:
  119.             return -1
  120.         node = self.nodesMap[key]
  121.         self.linkedList.moveNodeToEnd(node)
  122.         return node.val
  123.  
  124. # # ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
  125. # # // [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
  126. # if __name__ == '__main__':
  127. #     cache = LRU(2)
  128. #     cache.put(1, 1)
  129. #     cache.put(2, 2)
  130. #     print(cache.get(1))
  131. #     cache.put(3,3)
  132. #     print(cache.get(2))
  133. #     cache.put(4, 4)
  134. #     print(cache.get(1))
  135. #     print(cache.get(3))
  136. #     print(cache.get(4))
  137.  
  138.  
  139. # There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
  140.  
  141. # For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
  142. # Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
  143.  
  144.  
  145.  
  146. # Example 1:
  147.  
  148. # Input: numCourses = 2, prerequisites = [[1,0]]
  149. # Output: [0,1]
  150. # Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
  151. # Example 2:
  152.  
  153. # Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
  154. # Output: [0,2,1,3]
  155. # Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
  156. # So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
  157. # Example 3:
  158.  
  159. # Input: numCourses = 1, prerequisites = []
  160. # Output: [0]
  161.  
  162.  
  163. # Constraints:
  164.  
  165. # 1 <= numCourses <= 2000
  166. # 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  167. # prerequisites[i].length == 2
  168. # 0 <= ai, bi < numCourses
  169. # ai != bi
  170. # All the pairs [ai, bi] are distinct.
  171.  
  172. # [0, 1]
  173. # 0<-1
  174.  
  175. # class GraphNode:
  176. #     def __init__(self, val):
  177. #         self.val = val
  178.  
  179. # space  - O(max(courses, relationships))
  180. # time - O(courses + relationships)
  181. def getCoursesOrder(courses, courseRelationship):
  182.     independentCourse = [] # O(courses)
  183.     dependencyCounter = dict() # O(courses)
  184.     depMap = dict() # O(relationships)
  185.  
  186.     for dep in courseRelationship: # O(relationships)
  187.         c1, c2 = dep
  188.         if c1 not in dependencyCounter:
  189.             dependencyCounter[c1] = 0
  190.         dependencyCounter[c1] += 1
  191.         if c2 not in depMap:
  192.             depMap[c2] = []
  193.         depMap[c2].append(c1)
  194.  
  195.  
  196.     for i in range(courses): # O(courses)
  197.         if dependencyCounter.get(i, 0) == 0:
  198.             independentCourse.append(i)
  199.     cp = 0
  200.     result = [] # O(courses)
  201.  
  202.     while cp < len(independentCourse):
  203.         currentCourse = independentCourse[cp]
  204.         result.append(currentCourse)
  205.         dependentCourses = depMap.get(currentCourse, [])
  206.         for course in dependentCourses: # O(relationships)
  207.             dependencyCounter[course] -= 1
  208.             if dependencyCounter[course] == 0:
  209.                 independentCourse.append(course)
  210.         cp += 1
  211.     return result
  212.  
  213. if __name__ == '__main__':
  214.     result = getCoursesOrder(4, [[0,1],[2,0],[3,1],[3,2]])
  215.     print(result)
  216.  
  217. # [[1,0],[2,0],[3,1],[3,2]]
  218. # [0] 
  219. # {1:0, 2:0, 3:0}
  220. # {0:[1, 2], 1:[3], 2:[3]}
  221.  
  222. # [0, 1, 2, 3]
  223. # result [0, 1, 2, 3]
  224.  
  225.  
  226.  
  227.  
  228.  
  229.  
  230.  
  231.  
  232.  
  233.  
  234.  
Success #stdin #stdout 0.13s 14076KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[1, 0, 2, 3]
https://ideone.com/yyCjy8
language:
Python 3 (python  3.12)
created:
3 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!