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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
Solutions to weekly challenge 71 by Bob Lied.
This week I would like to incorporate Test::More TDD into the problem, creating
some tests before even starting to program the answer.
* TASK #1 > Peak Element
** Initial thoughts
The first interesting problem is creating an array of unique random elements.
For test purposes, we are going to give manually created lists, but command
line arguments should be validated.
Finding the peak looks like it will mean linear search, comparing the value
before and the value after. Watch out for boundaries. Maybe an easy trick
is to put 0 on the front of the list and 51 on the end.
** Post Solution Thoughts
Setting up the test cases first was helpful to think about those edge cases.
Not sure why the given example solution 1 lists 48 as the first element;
perhaps it was doing edges first.
Putting extra 0 elements (not 51) before and after the list did indeed make
the problem easier.
Creating the random array: make a set of numbers from 1..50, move random
element from this pool to the input array. Look up perl documentationn for
random values and splice (sigh, again; some kind of brain defect prevents me
from remembering its arguments). Googling for a module to do it led me to
an answer on Perl Monks that's almost a one-liner.
** Problem Statement
You are given positive integer $N (>1).
Write a script to create an array of size $N with random unique elements between 1 and 50.
In the end it should print peak elements in the array, if found.
An array element is called peak if it is bigger than it’s neighbour.
Example 1
Array: [ 18, 45, 38, 25, 10, 7, 21, 6, 28, 48 ]
Peak: [ 48, 45, 21 ]
Example 2
Array: [ 47, 11, 32, 8, 1, 9, 39, 14, 36, 23 ]
Peak: [ 47, 32, 39, 36 ]
* TASK #2 > Trim Linked List
** Initial Thoughts
We can reuse the linked list from a couple of weeks ago (simple Moo class).
Walking backwards from the end of a linked list is a good reason not to use
a linked list. It would help to know the size of the list so we don't have
to walk the whole thing to get the length, and then walk again to the
deletion point.
** Post Solution Thoughts
Wanting to keep the size of the list, I decided to make a class for a
singly-linked list that would store the size as an attribute and do all the
list operations as methods. Debatable whether this gained much over the
simpler use of Node alone and passing N around, but it was kind of fun.
Making a more complicated object motivated learning some things about Moo
constructors and member attributes.
As always, the edge cases take the longest to get right, but setting up the
test cases made sure they got covered.
Implementing a singly-linked list feels a lot like programming C in Perl.
Array access is just too easy; I don't think I'd ever realistically use a
linked list in Perl.
** Problem Statement
You are given a singly linked list and a positive integer $N (>0).
Write a script to remove the $Nth node from the end of the linked list and print the linked list.
If $N is greater than the size of the linked list then remove the first node of the list.
NOTE: Please use pure linked list implementation.
Example
Given Linked List: 1 -> 2 -> 3 -> 4 -> 5
when $N = 1
Output: 1 -> 2 -> 3 -> 4
when $N = 2
Output: 1 -> 2 -> 3 -> 5
when $N = 3
Output: 1 -> 2 -> 4 -> 5
when $N = 4
Output: 1 -> 3 -> 4 -> 5
when $N = 5
Output: 2 -> 3 -> 4 -> 5
when $N = 6
Output: 2 -> 3 -> 4 -> 5
|
