Re:Interviewing programmers: coding test example explained
by RiderOfGiraffes on Thursday June 03, 2010 @04:01PM
(#1402347)
You should write that up as a proper tutorial - I'm pretty sure a few people here would find it interesting.
Basically the same as for a while loop, as given e.g. at http://en.wikipedia.org/wiki/Hoare_logic since (apart from the behaviour of continue)
and are equivalent. And if you do want to deal with continue (and presumably also break) the Hoare stuff gets awfully cumbersome; you're probably better off using informal correctness proofs and writing down a lot of loop invariants.Oh, all right, here's how you do it. Suppose you have the following three Hoare triples.
where Q0, Q1, Q2 are mutually exhaustive (but not necessarily mutually exclusive). And suppose you have Then you have That's if you adopt the convention that any precondition is valid for code that doesn't terminate. Otherwise, you need to do some stuff with loop variants. We can takeP0: str points to a zero-terminated string. P: so does rd, rd and str point to tails of the original string, rd >= str, and what's between original_str and str consists of an appropriately crunched version of what was originally between original_str and rd. Q0,Q1,Q2: true,false,false. R: not needed.
We deduce that at the end of the for loop, rd points to a tail of the original string (P), it also points to a zero character (!cond), hence it points to the end of the original string. Hence what's between original_str and str consists of an appropriately crunched version of the entire original string. Hence all we need do is put on the final zero character, and we're finished.