· 6 years ago · Sep 12, 2019, 03:26 PM
1## Question 2
2Design and implement a data structure for cache.
3
4get(key) - Get the value of the key if the key exists in the cache, otherwise return -1
5
6put(key, value, weight) - Set or insert the value, when the cache reaches its capacity, it should invalidate the least
7scored key. The scored is calculate as weight / ln(current_time - last_access_time)
8
9Your data structure should be optimized for the computational complexity of get(key) i.e. Average case for
10computational complexity of get(key) could be O(1).
11
12In your (pesudo-)code, you can assume common data structure such as array, different type of list, hash table are
13available.
14
15Please explain the computational complexity of get(key) and put(...) in Big-O notation.
16
17## Answer (swift program)
18```swift
19import Foundation
20
21// Data Structure for cache
22class Cache {
23 // Use dictionary/hash map,
24 // key is String
25 // value is tuple of type (Int, Int, Int)
26 var dict = Dictionary<String,(Int, Int, Int)>()
27 let capacity: Int
28 var currentTime = 0 // Timer: a Int variable to keep track of time
29
30 init(withCapacity: Int) {
31 capacity = withCapacity
32 }
33
34 // Get the element from the cache if present
35 func get(key: String) -> Int {
36 print("Currenttime: \(currentTime)")
37 print("get(key: \(key))")
38
39 // Check if element already exist, if yes then update the LASTACCESSTIME and return the element's value
40 if let tuple = dict[key] {
41 let updatedTuple = (tuple.0, tuple.1, currentTime)
42 dict[key] = updatedTuple
43 return tuple.0
44 } else { // If fault occurs return -1
45 return -1
46 }
47 }
48
49 // Insert new element in Cache
50 func put(key: String, value: Int, weight: Int) {
51 print("Currenttime: \(currentTime)")
52 print("put(key: \(key), value: \(value), weight: \(weight))")
53
54 if dict.keys.contains(key) || dict.keys.count < capacity {
55 // If cache contains the key already then just update the value
56 // If cache capacity is not full then insert the new element
57 let tuple = (value, weight, currentTime)
58 dict[key] = tuple
59 } else if dict.keys.count > 0 { // Cache capacity is full
60 // If cache capacity is full, traverse the cache and find the element with minimum score
61 var keyWithMinScore = dict.keys.first
62 var score = -1
63
64 for key in dict.keys {
65 if score == -1, let tuple = dict[key] {
66 score = calculateScore(tuple: tuple)
67 keyWithMinScore = key
68 } else if let tuple = dict[key] {
69 let newScore = calculateScore(tuple: tuple)
70 if newScore < score {
71 score = newScore
72 keyWithMinScore = key
73 }
74 }
75 }
76
77 // Remove the element with minimum score and insert new element
78 if let keyToRemove = keyWithMinScore {
79 dict.removeValue(forKey: keyToRemove)
80
81 let newTuple = (value, weight, currentTime)
82 dict[key] = newTuple
83 }
84 }
85 }
86
87 // Function to calculate the score using formulae "weight/(currentTime - lastAccessTime)"
88 func calculateScore(tuple: (Int, Int, Int)) -> Int {
89 let lastAccessTime = tuple.2
90 let weight = tuple.1
91
92 let difference = currentTime - lastAccessTime
93
94 if weight >= difference {
95 return weight / difference
96 } else {
97 return 0
98 }
99 }
100
101 func incrementTimer() {
102 currentTime += 1
103 }
104
105 // Formatted printing of cache data
106 func printCache() {
107 print("\n\nCurrenttime: \(currentTime)\nKEY\t\tVALUE\t WEIGHT\tLASTACCESSTIME\tSCORE")
108 for key in dict.keys.sorted() {
109 if let tuple = dict[key] {
110 print(String(format: "%-10@ %10d %10d %10d %10d", key, tuple.0, tuple.1, tuple.2, calculateScore(tuple: tuple)))
111 }
112 }
113 print("\n")
114 }
115}
116
117// Create cache data structure and try different operations
118let cache = Cache(withCapacity: 4)
119
120cache.incrementTimer()
121cache.put(key: "A", value: 500, weight: 15)
122
123cache.incrementTimer()
124cache.put(key: "B", value: 200, weight: 30)
125
126cache.incrementTimer()
127cache.put(key: "C", value: 300, weight: 21)
128
129cache.incrementTimer()
130cache.put(key: "D", value: 600, weight: 11)
131
132cache.incrementTimer()
133cache.printCache()
134
135cache.put(key: "E", value: 800, weight: 16)
136
137cache.incrementTimer()
138cache.printCache()
139
140print(cache.get(key: "D"))
141
142cache.incrementTimer()
143cache.printCache()
144
145print(cache.get(key: "E"))
146
147cache.incrementTimer()
148cache.printCache()
149
150cache.put(key: "B", value: 800, weight: 20)
151
152cache.incrementTimer()
153cache.printCache()
154
155print(cache.get(key: "A"))
156
157cache.incrementTimer()
158cache.printCache()
159```
160## Output
161```swift
162Currenttime: 1
163put(key: A, value: 500, weight: 15)
164Currenttime: 2
165put(key: B, value: 200, weight: 30)
166Currenttime: 3
167put(key: C, value: 300, weight: 21)
168Currenttime: 4
169put(key: D, value: 600, weight: 11)
170
171
172Currenttime: 5
173KEY VALUE WEIGHT LASTACCESSTIME SCORE
174A 500 15 1 3
175B 200 30 2 10
176C 300 21 3 10
177D 600 11 4 11
178
179
180Currenttime: 5
181put(key: E, value: 800, weight: 16)
182
183
184Currenttime: 6
185KEY VALUE WEIGHT LASTACCESSTIME SCORE
186B 200 30 2 7
187C 300 21 3 7
188D 600 11 4 5
189E 800 16 5 16
190
191
192Currenttime: 6
193get(key: D)
194600
195
196
197Currenttime: 7
198KEY VALUE WEIGHT LASTACCESSTIME SCORE
199B 200 30 2 6
200C 300 21 3 5
201D 600 11 6 11
202E 800 16 5 8
203
204
205Currenttime: 7
206get(key: E)
207800
208
209
210Currenttime: 8
211KEY VALUE WEIGHT LASTACCESSTIME SCORE
212B 200 30 2 5
213C 300 21 3 4
214D 600 11 6 5
215E 800 16 7 16
216
217
218Currenttime: 8
219put(key: B, value: 800, weight: 20)
220
221
222Currenttime: 9
223KEY VALUE WEIGHT LASTACCESSTIME SCORE
224B 800 20 8 20
225C 300 21 3 3
226D 600 11 6 3
227E 800 16 7 8
228
229Currenttime: 9
230get(key: A)
231-1
232
233Currenttime: 10
234KEY VALUE WEIGHT LASTACCESSTIME SCORE
235B 800 20 8 10
236C 300 21 3 3
237D 600 11 6 2
238E 800 16 7 5
239
240```
241
242## Time complexity
243Best case and average case time complexity of get(key) function is O(1) as we are using the dictionary as our data structure and it has O(1) of access time
244
245Worst case time complexity of of put(key, value, weight) function is O(n) because we have to traverse throught entire cache
246to find the element with minmum score