1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
Task 1: "Smallest Multiple:
Write a script to accept a positive number as command line argument and print the smallest multiple of the given number consists of digits 0 and 1.
For example:
For given number 55, the smallest multiple is 110 consisting of digits 0 and 1.
"
My notes: cute.
Task #2: "LRU Cache
Write a script to demonstrate LRU Cache feature. It should support
operations get and set. Accept the capacity of the LRU Cache as command
line argument.
Definition of LRU: An access to an item is defined as a get or a set
operation of the item. "Least recently used" item is the one with the
oldest access time.
For example:
capacity = 3
set(1, 3)
set(2, 5)
set(3, 7)
Cache at this point:
[Least recently used] 1,2,3 [most recently used]
get(2) # returns 5
Cache looks like now:
[Least recently used] 1,3,2 [most recently used]
get(1) # returns 3
Cache looks like now:
[Least recently used] 3,2,1 [most recently used]
get(4) # returns -1
Cache unchanged:
[Least recently used] 3,2,1 [most recently used]
set(4, 9)
Cache is full, so pushes out key = 3:
[Least recently used] 2,1,4 [most recently used]
get(3) # returns -1
"
My notes: ok, so an array of keys in most-recently-used
order, and a hash to store the (no more than $capacity)
key, value pairs.
|
