blob: c1fbac90da0da7f6df483cb3b16da528cdc53f38 (
plain)
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
|
# Challenge #1
Write a script that takes 2 or more strings as command line parameters
and print the longest common substring. For example, the longest
common substring of the strings “ABABC”, “BABCA” and “ABCBA” is string
“ABC” of length 3. Other common substrings are “A”, “AB”, “B”, “BA”,
“BC” and “C”.
## Solution
Substrings of the first argument are iterated by decreasing length.
The script finds the `$substring` that is common within the list of
parameters `@ARGV == grep(/$substring/,@ARGV)`.
# Challenge #2
Write a script to implement Priority Queue. It is like regular queue
except each element has a priority associated with it. In a priority
queue, an element with high priority is served before an element with
low priority. Please check this wiki page for more informations. It
should serve the following operations:
1. `is_empty`: check whether the queue has no elements.
2. `insert_with_priority`: add an element to the queue with an
associated priority.
3. `pull_highest_priority_element`: remove the element from the queue
that has the highest priority, and return it. If two elements have the
same priority, then return element added first.
## Solution
The solution is a hashmap of priority and anonymous arrays.
The anonymous array `[]` is accessed with a `$priority`.
`$queue` is the hashmap. `$queue->{$priority}` is an anonymous array.
`@{$queue->{$priority}}` wraps access to the prioritized queues as arrays.
`pull_highest_priority_element()` parses the `$queue` to find the
nonempty array with the largest priority, then returns the first entry.
|
