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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
|
# Work sample for OSO
This is the work sample for my job application for a developer
position for OSO.
## Re-statement of problem
To clarify the problem for myself, I am re-stating it. This will also
work to make sure I've understood it in the intended way when we
discuss this.
The goal is to write a server, which communicates with a client using
messages over HTTP. The client has a list of integers, and the asks
the server to figure out what is the largest integer in the list. The
crux is that the client does not send the server the whole list, but
only small messages and the server needs to, effectively, ask the
client to do pairwise comparisons of integers.
The possible messages sent by the client and the server are listed
below, as examples. Communication is started by client by a "start
computation" message. Server responds with a suitable message, which
causes the client to make a new HTTP request with the response to the
server's message. This continues until the server sends a message
with result it has come up with.
## Client request: start computation
Client starts the protocol by asking the server to compute something
about a list of numbers the client holds. It tells the server what
computation is requested, and how long the list is.
The supported computations are, for now, `compute_max` (find index of
the largest integer) and `compute_min` (similar, but smallest
integer).
~~~json
{
"type": "compute_max",
"length": 2
}
~~~
## Server response: request computation
Server ask the client to report the result of a less-than comparison
operation between arbitrary list items.
~~~json
{
"type": "compare",
"left": 0,
"right": 1,
"request_id": 7
}
~~~
## Client request: computation result
The client reports the result of a comparison. The server should
respond by another comparison request, or the result of the
computation.
~~~json
{
"type": "comp_result",
"answer": true,
"request_id": 7
}
~~~
## Server response: result
~~~json
{
"type": "done",
"result": 2
}
~~~
# Example
In this example, assume the client has the following list:
> 5, 6, 7, 5
Note that the list is not in order and numbers aren't unique. The
sequence diagram below shows the messages the go between the client
and the server.
For simplicity, request ids are not shown.
~~~plantuml
@startuml
participant "client" as c
participant "server" as s
c -> s : compute_max, length=4
note left
client tells server there
are 4 integes and that the
server should figure out
the largest one
end note
c <- s : compare(0,1)
note right
server wants client to
compare integers at
indexes 0 and 1
end note
c -> s : comp_result, answer=true
note left
client reports that
the integer at index
0 is less than the one
at index 1
end note
c <- s : compare(1,2)
note right
max so far is at index 1;
server asks is list[1] < list[2]
end note
c -> s : comp_result, answer=true
note left
client reports yes
end note
c <- s : compare(2,3)
note right
max so far is at index 2;
server asks is list[2] < list[3]
end note
c -> s : comp_result, answer=false
note left
client reports no
end note
c <- s : done, answer=2
note right
server knows it has compared
all list items and that max is
at index 2
end note
@enduml
~~~
This is very simple computation. Given the server can't assume the
list is ordered, it has to compare all list elements to the largest
one it has found so far.
# Assumptions
* The server will abort if the client doesn't use the request id from
the latest server message. That is, the client and server do not
need to handle multiple outstanding comparison requests.
* The server does not need to handle the case of the client having an
empty list of integers, because there messages as given do no
indicate a way to signal a result of "no result".
# Acceptance criteria
## Find max of a list of one
This scenario verifies that the server finds the maximum integer in a
list of one.
~~~scenario
given server
when I run max-client.py 1
then answer is 1
~~~
## Find max of a list of two
These scenarios verify that the server finds the maximum integer in a
list of two. There is a separate scenario for every possible list of
two elements.
### List of two identical numbers
~~~scenario
given server
when I run max-client.py 5 5
then answer is 5
~~~
### List of two numbers in order
~~~scenario
given server
when I run max-client.py 5 6
then answer is 6
~~~
### List of two numbers in wrong order
~~~scenario
given server
when I run max-client.py 6 5
then answer is 6
~~~
---
title: "OSO work sample—MAX"
author: Lars Wirzenius
classes:
- json
template: python
bindings:
- oso.yaml
- lib/daemon.yaml
- lib/runcmd.yaml
functions:
- oso.py
- lib/daemon.py
- lib/runcmd.py
...
|
