The Coding Exercise:
Report on the Melbourne meeting in October 2004
|
One of the good things about ADUG meetings is that
we can do whatever we choose at them. Usually that involves
a couple of presentations. There is always discussion,
but most of the work is done by the presenters. However,
sometimes we do something more activity-based. This
time we did some PROGRAMMING! The exercise was inspired
by an article by Joel, The
guerrilla guide to interviewing, in which he outlined
his technique for selecting applicants for programmer
positions with his company. One of the elements he uses
is a programming question, which the candidate is to
answer by writing his code (in C) on a piece of paper,
during the interview. The question should be capable
of being answered in 5 lines or so.
The committee thought up some elementary (but not necessarily
easy!) problems suitable to attack with Delphi. There
were three problems, so the meeting split into three
groups. Pre pizzas they worked out their answer, on
butcher's paper, not that butcher's use it any more,
and post pizzas solutions and issues were presented
and discussed.
How did it work? We think it worked well, and we're
likely to do it again, probably with variations. For
example, we might get each group to do all problems,
so that we can compare different approaches.
One of the problems was more involved than the others,
and only pseudo code was offered in the meeting, but
subsequent work proved that it was much faster than
the Borland utility.
Anyhow, here are the problems,
here are some pics taken on the
night, and here are the results.
Problem 1: Monetary Rounding
Divide a monetary amount rAmt to n recipients. The
distributed amount, rSameAmt, must be rounded to the
nearest 5 cents, with the nth recipient receiving rRemAmt,
the potentially odd amount. ie, implement this procedure..
procedure DivAmt(
rAmt: real; n: integer; var rSameAmt, rRemAmt: real
);
Problem 2: Reverse a String in Place
A string is to be passed to a procedure which is to
reverse it in the same memory location. Local variables
may be used by the procedure.
procedure ReverseString(var
s: string);
Problem 3: Search and Replace in a String
Given string s and substrings sRepl and sWith, replace
all occurences of sRepl in s with sWith.
procedure ReplStr(sRepl,
sWith: string; var s: string);
|
The Teams
|
ReverseStringInPlace
Group
Ian Krigsman,
Lance Collins and ??? deliberate
|
The Rounding
Group
Clockwise
from bottom: Noel Lodge, Bryan Dayton, Ralph Knight,
Natalie Vincent, Jim Duff,Andrew Tuck, Anthony Michell,
Phil Sheppard
|
|
The String
Replace Group
John MacDonald,
Richard King, Alex Moss and ???
|
|
Richard presents...
|
Roger Connell
elucidates...
|
Natalie relates...
|
|
In conclusion..
at rear: Andrea Coffey, ???, Graham Pitson. The rest,
l to r: Noel Lodge,
Bryan Dayton, Natalie Vincent, Ralph Knight, Lance Collins,
Tim Casimir, ???,
Arjang Assandi, Roger.
|
Solutions
Problem 1: Monetary Rounding
This was of course not *the* monetary rounding issue, but
a particular problem, which the group coded up with no big
issues:
procedure DivAmt(rAmt: Real;
n: integer; var rSameAmt, rRemAmt: real; iRoundBy:integer);
var
i: integer;
begin
i := Trunc((rAmt * (100 / iRoundBy)) / n + 0.5);
rSameAmt := i / (100 / iRoundBy);
rRemAmt := rAmt - (rSameAmt * (n - 1));
end;
Note that the group's implementation allowed rounding to
a specified amount, not just to 5 cents.
Problem 2: Reverse a String in Place
procedure ReverseString(var
s: string);
This group spent quite some time discussing why you would
want to reverse a string in place, since in Delphi this may
have undesirable consequences if there is more than one user
of the string. Their implementation was as follows:
Procedure ReverseString(var
s:String);
var
ch:char;
leng,i:Integer;
begin
leng:=Length(s);
for i:=1 to leng div 2 do
begin
Ch:=s[i];
s[i]:=s[leng-i+1];
s[leng-i+1]:=Ch;
end;
end;
This implementation does reverse the string, but not
in place. Changing the value of the string, albeit a character
at a time, actually causes a new string to be allocated. To
achieve reversal in place it is necessary to treat the string
as a PChar, which is what it is 'under the hood'.
procedure ReverseString( const
s:String );
var
len: integer;
counter:integer;
begin
leng := Length(s);
for counter :=0 to (len div 2 - 1) do
begin
PChar(s)[len]:=PChar(s)[counter];
PChar(s)[counter]:=PChar(s)[leng - counter - 1];
PChar(s)[leng- counter -1]:= PChar(s)[len];
end;
PChar(s)[len] := #0;
end;
Just for fun this implementation uses the null terminator
as the character buffer!
Problem 3: Search and Replace in a String
Richard King explained that the intention of the group was
to minimise memory allocations (and Delphi's automatic copy-on-write
allocations) . The solution presented was pseudo code only,
but subsequently Richard completed the Delphi implementation,
which he reports is 2 - 3 times faster than the Borland StringReplace
utility. Here's the implementation..
uses
StrUtils;
procedure ReplStr(searchFor,
replaceWith: string; var s: string);
function SomethingExtra
: integer;
begin
// can make this as smart as you want
// will only be called if repalceWith is longer than searchFor
// eg assume one replacement
result := length(replaceWith) - length(searchFor);
end;
var
replaced : string; // working buffer
ps, pr, p, bsize,
charsToCopy : integer;
begin
ps := 1; // index into source string (s)
pr := 1; // index into replaced string
p := pos(searchFor, s);
if p = 0 then
exit; // ---> bail out, nothing to do
if length(replaceWith)
> length(searchFor) then
bSize := length(s) + SomethingExtra
else
bSize := length(s); // will truncate at end if necessary
SetLength(replaced, bSize); //
allocate buffer
while p <> 0 do
begin
// copy (p-ps) bytes from source to replacement
// and copy replaceWith
// and inc pointers
charsToCopy := p - ps ;
move(s[ps], replaced[pr], charsToCopy);
inc(pr, charsToCopy);
move(replaceWith[1], replaced[pr], length(replaceWith));
inc(pr, length(replaceWith));
inc(ps, charsToCopy + length(searchFor));
p := PosEx(searchFor, s, ps);
// check buffer is big enough
if bSize + ( length(replaceWith) - length(searchFor)
) > length(replaced) then begin
bSize := bSize + SomethingExtra;
SetLength(replaced, bSize);
end;
end; // while
// copy last of source string
move(s[ps], replaced[pr], length(s) - ps + 1);
SetLength(replaced, pr + length(s) - ps); // truncate if necessary
s := replaced;
end;
|
