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
|
Task 1: "Compare Version
Compare two given version number strings v1 and v2 such that:
If v1 > v2 return 1
If v1 < v2 return -1
Otherwise, return 0
The version numbers are non-empty strings containing only digits, the dot
('.') and underscore ('_') characters. ('_' denotes an alpha/development
version, and has a lower precedence than a dot, '.'). Here are some examples:
v1 v2 Result
------ ------ ------
0.1 < 1.1 -1
2.0 > 1.2 1
1.2 < 1.2_5 -1
1.2.1 > 1.2_1 1
1.2.1 = 1.2.1 0
Version numbers may also contain leading zeros. You may handle these
how you wish, as long as it's consistent.
"
My notes: I hate it already:-) but it doesn't sound too hard.
Task 2: "Ordered Lineup
Write a script to arrange people in a lineup according to how many
taller people are in front of each person in line. You are given two
arrays. @H is a list of unique heights, in any order. @T is a list of
how many taller people are to be put in front of the corresponding
person in @H. The output is the final ordering of people's heights,
or an error if there is no solution.
Here is a small example:
@H = (2, 6, 4, 5, 1, 3) # Heights
@T = (1, 0, 2, 0, 1, 2) # Number of taller people wanted in front
The ordering of both arrays lines up, so H[i] and T[i] refer to the same
person. For example, there are 2 taller people in front of the person
with height 4, and there is 1 person in front of the person with height 1.
here is one possible solution that satisfies @H and @T:
(5, 1, 2, 6, 3, 4)
Note that the leftmost element is the 'front' of the array.)
"
My notes: an unfamiliar problem, sounds quite interesting. No algorithm
immediately comes to mind.. Generate-and-test was my first thought - i.e.
have a function to test "is-this-combination-a-valid-answer" and invoke it
for every possible answer. But the question also suggested that our
algorithm should be able to work at a scale of 1000 people, and the number
of combinations of 1000 people is insane (1000!). so scratch that.
After trying a few examples manually, I realised that the first person in
the queue must be someone who wants 0 people taller than them in front of
them, and quickly generalised this into what I think it a valid and efficient
algorithm. See function "solve".
However, it doesn't (yet) scale to the 64-person solution, much less the
1000-person one. I've tried some Perl profiling on an intermediate scale
problem, and managed to make it run 4 times faster, but it still can't
scale up to 64-person scale, would need a fundamentally faster algorithm,
which I just can't see.
|
