Last active
April 9, 2020 23:01
-
-
Save OhMeadhbh/ebd501a815a42cbafd3baa187f51d451 to your computer and use it in GitHub Desktop.
Talking Through A Coding Task
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* interval.c | |
** | |
** From a coding interview I (OhMeadhbh@gmail.com) | |
** recently participated in: | |
** | |
** Write a function that finds the intersection of two | |
** intervals. So if you had the intervals 2 - 8 and 5 - | |
** 12, the intersection would be 5 - 8. */ | |
/* Let's start by defining the function that will | |
** calculate the interval. Something like: | |
** | |
** tInterval intersection( tInterval a, tInterval b); | |
** | |
** But we have to define the tInterval type first: */ | |
typedef struct { | |
int begin; | |
int end; | |
} tInterval; | |
/* But instead of using the function signature above, | |
** I'm going to do the following: */ | |
int intersection_test \ | |
( tInterval a, tInterval b, tInterval * n ); | |
/* I changed the intersection signature to take two | |
** tInterval's plus a pointer to a tInterval and return | |
** a status code as an int. Why do this? Old-skool C | |
** programmers would probably just pass three pointers: | |
** two for the inputs and one for the result. But modern | |
** C can reasonably efficiently copy structs to the | |
** stack and the structs we're copying aren't huge. But | |
** the benefits of returning a status int will be more | |
** obvious later on. | |
** | |
** The benefits of passing two structs on the stack are: | |
** a. It enforces the read-only nature of the inputs | |
** better than const can. (Badly written code can | |
** evade const restrictions, but the only struct | |
** the code knows about is the one that's copied | |
** to the stack when the function is called.) | |
** b. There are fewer pointers. After decades of | |
** denying the simple truth, I've come around to | |
** the realization that even smart programmers can | |
** do stupid things with pointers. If you don't | |
** need them, don't use them. | |
** | |
** But in this instance, there are a couple drawbacks to | |
** mixing structs with pointers to structs as | |
** parameters: | |
** a. You're mixing pointers with direct references. | |
** It *might* get confusing when some elements are | |
** accessed via dots and others by arrows. | |
** b. If we change the code and make tInterval some | |
** huge data structure, it could become inefficient | |
** to keep copying it to the stack. (But honestly, | |
** worrying about this sounds like a premature | |
** optimization.) */ | |
/* I'm going to define three different intersection | |
** routines here: one that does nothing and is used for | |
** testing, one that is a naive attempt and the last | |
** that is what you could have figured out if (like me) | |
** you didn't just rush into coding. */ | |
int intersection_naive \ | |
( tInterval a, tInterval b, tInterval * n ); | |
int intersection_better \ | |
( tInterval a, tInterval b, tInterval * n ); | |
/* To make it simple, we'll default to using the test | |
** implementation, but you can use a command line | |
** argument to select the naive or better | |
** implementations (like so): | |
** | |
** gcc -o interval -DNS_NAIVE interval.c | |
** or | |
** gcc -o interval -DNS_BETTER interval.c | |
** | |
** And here we test whether these macros are defined | |
** at compile time and define a macro to be used like | |
** a function in the main section of the code. */ | |
#if defined( NS_BETTER ) | |
#define intersection intersection_better | |
#elif defined( NS_NAIVE ) | |
#define intersection intersection_naive | |
#else | |
#define intersection intersection_test | |
#endif | |
/* So you remember we said we were returning a status | |
** value from the call to intersection_<whatever>() ? | |
** I'm going to define three status values: | |
** | |
** S_NOERR - no error occurred | |
** S_BADPARAM - you passed a null pointer | |
** S_NONTERS - the two inputs don't intersect | |
** | |
** Why do this? Mostly 'cause we didn't have a detailed | |
** discussion about whether or not the intervals were | |
** open or closed (includes or does not include the | |
** points at the beginning and end of the interval.) If | |
** they're closed, it means they include the boundary | |
** points. And if they're closed and you're given the | |
** interval [0,0] and [-1,1], then the proper response | |
** is [0,0], which is what I was going to initially use | |
** as the "no interval" response. Whoops. */ | |
#define S_NOERR (0) | |
#define S_BADPARAM (1) | |
#define S_NONTERS (2) | |
/* And at this point you may be asking yourself why | |
** we're using a pound-define instead of an enum. Thirty | |
** years ago there were C compilers that didn't quite | |
** handle enums properly. I heard one old C programmer | |
** say it looked too much like Pascal. Modern C | |
** compilers *should* handle enums at least as well as | |
** pound-defines for this use case. So the simple answer | |
** is: inertia. | |
** | |
** But if you wanted to use an enum for the return code, | |
** you could do something like this. Don't forget to | |
** change the intersection functions to return the enum | |
** instead of an int, though: | |
** | |
** typedef \ | |
** enum { S_NOERR, S_BADPARAM, S_NONTERS } \ | |
** tStatus; | |
** | |
** tStatus intersection_test \ | |
** ( tInterval a, tInterval b, tInterval * n ); | |
** tStatus intersection_naive \ | |
** ( tInterval a, tInterval b, tInterval * n ); | |
** tStatus intersection_better \ | |
** ( tInterval a, tInterval b, tInterval * n ); | |
** | |
** But... if you're going to use pound-defines, it's | |
** considered good practice to put parens around the | |
** constants to avoid problems if they're used | |
** unhygenically. */ | |
/* I don't know about you, but I'm a fan of Test-First | |
** development. So let's think about some test | |
** data. This should also get us to think about things | |
** like "are the intervals we're given really open or | |
** closed?" -- This is the magic of test first. The | |
** sooner you can write code (any code) the sooner you | |
** may find you have open questions about the | |
** requirements. And since we all live in an agile | |
** coding utopia, the cost of redesign is low. (The joke | |
** here is that's not always the case, so if you can | |
** detect design flaws *BEFORE* you start coding large | |
** parts of your program, you don't have to go back to | |
** to recode them.) | |
** | |
** But let's define some test data. First, here's a | |
** typedef for the test fixtures: two input intervals, | |
** an expected status return code and the resulting | |
** intersection. */ | |
typedef struct { | |
tInterval a; | |
tInterval b; | |
int expected_status; | |
tInterval n; | |
} tFixture; | |
/* And here's the test data: */ | |
tFixture fixtures [] = { | |
/* Test for the simple identity test case */ | |
{ { 0, 0 }, { 0, 0 }, S_NOERR, { 0, 0 } }, | |
/* Test that the interval is closed */ | |
{ { 0, 5 }, { 5, 10 }, S_NOERR, { 5, 5 } }, | |
/* Same thing, but flip the parameters*/ | |
{ { 5, 10 },{ 5, 5}, S_NOERR, { 5, 5 } }, | |
/* What if one interval is just a point? */ | |
{ { 5, 10 }, { 5, 5 }, S_NOERR, { 5, 5 } }, | |
{ { 5, 5 }, { 5, 10 }, S_NOERR, { 5, 5 } }, | |
/* Here's a simple interval */ | |
{ { 0, 5 }, { 2, 7 }, S_NOERR, { 2, 5 } }, | |
{ { 2, 7 }, { 0, 5 }, S_NOERR, { 2, 5 } }, | |
/* What if there's no intersection? */ | |
{ { 0, 4 }, { 5, 10 }, S_NONTERS, { 0, 0 } }, | |
{ { 5, 10 }, { 0, 4 }, S_NONTERS, { 0, 0 } }, | |
/* S_NONTERS creates meaningless results */ | |
{ { 0, 4 }, { 5, 10 }, S_NONTERS, { 1, 1 } }, | |
{ { 5, 10 }, { 0, 4 }, S_NONTERS, { 1, 1 } }, | |
/* What if one interval encloses the other? */ | |
{ { 0, 9 }, { 3, 7 }, S_NOERR, { 3, 7 } }, | |
{ { 3, 7 }, { 0, 9 }, S_NOERR, { 3, 7 } }, | |
/* What if the start is greater than the end ?*/ | |
{ { 9, 0 }, { 3, 7 }, S_BADPARAM, { 0, 0 } }, | |
{ { 0, 9 }, { 7, 3 }, S_BADPARAM, { 1, 1 } }, | |
{ { 9, 0 }, { 7, 3 }, S_BADPARAM, { 2, 2 } } | |
}; | |
/* Don't forget to update this if you add or remove | |
** test fixtures. */ | |
#define FIXTURES_COUNT 16 | |
/* A couple things I realized about the requirements | |
** when coming up with the test fixtures: | |
** a. I'm definitely assuming we're dealing with | |
** closed intervals. | |
** b. The returned interval is meaningless unless the | |
** the return value is S_NOERR. */ | |
/* I guess we can create a main() routine that acts as | |
** a test driver. */ | |
#include <stdio.h> | |
int main() { | |
int i; | |
int success = 0, fail = 0, total = 0; | |
int status; | |
tInterval result; | |
/* First, let's check that giving a null pointer to | |
** the intersection() function results in a | |
** S_BADPARAM */ | |
status = intersection( | |
fixtures[ 0 ].a, | |
fixtures[ 0 ].b, | |
( tInterval * ) NULL ); | |
if( S_BADPARAM == status ) { | |
printf( "TEST 1 (NULL PTR): success\n" ); | |
success++; | |
} else { | |
printf( "TEST 1 (NULL PTR): failed\n" ); | |
fail++; | |
} | |
total++; | |
for( i = 0; i < FIXTURES_COUNT; i++ ) { | |
result.begin = 32767; | |
result.end = 16384; | |
status = intersection( | |
fixtures[ i ].a, | |
fixtures[ i ].b, | |
& result ); | |
total++; | |
/* If the expected status isn't the returned status | |
** then it's a fail. */ | |
if( fixtures[ i ].expected_status != status ) { | |
printf( "TEST %d: failed\n", i + 2 ); | |
fail++; | |
} else { | |
/* If the returned status (which is equal to the | |
** expected status at this point) isn't S_NOERR, | |
** we MUST NOT check the returned values */ | |
if( S_NOERR != status ) { | |
printf( "TEST %d: success\n", i + 2 ); | |
success++; | |
} else { | |
/* Now we just test that the beginning and end | |
** of the returned interval are the same as | |
** the expected values in the test fixture */ | |
if( ( fixtures[ i ].n.begin == result.begin ) && | |
( fixtures[ i ].n.end == result.end ) ) { | |
printf( "TEST %d: success\n", i + 2); | |
success++; | |
} else { | |
printf( "TEST %d: failed\n", i + 2); | |
fail++; | |
} | |
} | |
} | |
} | |
printf( "Results: %d total, %d fail, %d success\n", | |
total, fail, success ); | |
return( 0 ); | |
} | |
/* And here's a testing mock-up of the intersection | |
** function. I define things like this frequently so | |
** I can get a compiled, running program as fast as | |
** possible. In the modern era, a simple way to disprove | |
** your assertions that the test fixtures are correct | |
** is to try to compile the program at this point. If it | |
** doesn't compile, it may be because you goofed on | |
** designing the fixtures. Learning this early has | |
** saved my bacon several times in the past. So yes, it | |
** will take a little bit more time to do it this way, | |
** but in the long run it'll pay for itself when you | |
** don't have to redesign your fixtures and re-code your | |
** test driver. | |
** | |
** And if it compiles, it doesn't mean it's correct (of | |
** course.) YMMV. Also, I trust you're an adult. If you | |
** think it's easier to rush forward with implementing | |
** things, that's fine too. If you're wrong, I'm not | |
** going to be there to tease you about it. If you're | |
** wrong, try to think about why you thought it was a | |
** good idea to do what you did. Maybe you were right | |
** to think it was a good idea generally and you were | |
** just wrong this one time. You do you. | |
** | |
** Anyway, here's the simplest implementation of the | |
** test function that will let the program compile. */ | |
#if !defined( NS_BETTER ) && !defined( NS_NAIVE ) | |
int intersection_test \ | |
( tInterval a, tInterval b, tInterval * n ) { | |
return S_NOERR; | |
} | |
#endif | |
/* Now let's do a naive implementation of the interface | |
** we defined and proved compiles. Compile with the | |
** -DNS_NAIVE command line option to use this function. | |
** Or if you have make installed, | |
** | |
** CFLAGS=-DNS_NAIVE make interval | |
** | |
** will probably work. | |
*/ | |
#if defined( NS_NAIVE ) | |
int intersection_naive \ | |
( tInterval a, tInterval b, tInterval * n ) { | |
/* Start by checking if we're passed a null pointer */ | |
if( ( tInterval * ) NULL == n ) { | |
return S_BADPARAM; | |
} | |
/* Interval begin values should be less than or equal | |
** to interval end values. */ | |
if( ( a.end < a.begin ) || ( b.end < b.begin ) ) { | |
return S_BADPARAM; | |
} | |
/* Do the two intervals not intersect? */ | |
if( ( a.end < b.begin ) || ( b.end < a.begin ) ) { | |
return S_NONTERS; | |
} | |
/* Now, let's calculate the result */ | |
/* does b start before a? */ | |
if( b.begin <= a.begin ) { | |
n->begin = a.begin; | |
} else { | |
n->begin = b.begin; | |
} | |
/* does b end before a? */ | |
if( a.end <= b.end ) { | |
n->end = a.end; | |
} else { | |
n->end = b.end; | |
} | |
return S_NOERR; | |
} | |
#endif | |
/* And here is an implementation that's a bit better. | |
** It turns out that the intersection of two overlapping | |
** intervals is [MAX(begin), MIN(end)]. This avoids all | |
** the if clauses in the naive implementation and makes | |
** a slightly easier to read function. | |
** | |
** Use these command to build and test it: | |
** | |
** touch interval.c | |
** CFLAGS=-DNS_BETTER make interval && ./interval | |
*/ | |
#if defined( NS_BETTER ) | |
int intersection_better \ | |
( tInterval a, tInterval b, tInterval * n ) { | |
/* Start by checking if we're passed a null pointer */ | |
if( ( tInterval * ) NULL == n ) { | |
return S_BADPARAM; | |
} | |
/* Interval begin values should be less than or equal | |
** to interval end values. */ | |
if( ( a.end < a.begin ) || ( b.end < b.begin ) ) { | |
return S_BADPARAM; | |
} | |
/* Do the two intervals intersect? */ | |
if( ( a.end < b.begin ) || ( b.end < a.begin ) ) { | |
return S_NONTERS; | |
} | |
/* Now, let's calculate the result */ | |
n->begin = a.begin < b.begin ? b.begin : a.begin; | |
n->end = a.end < b.end ? a.end : b.end; | |
return S_NOERR; | |
} | |
#endif | |
/* So what did we learn here? When I was stepping | |
** through this intersection, I had to be reminded that | |
** the intersection of two intervals was [MAX(begin), | |
** MIN(end)]. I went straight for a mostly correct, but | |
** difficult to read solution. | |
** | |
** Hopefully I convinced you it's not hard to do | |
** "test first," and showed one way you could set up a | |
** C program to conditionally compile various different | |
** implementations of a function interface. Advanced | |
** students might suspect it's just as easy to avoid | |
** using the macro to define the intersection() function | |
** and just conditionally compile one of three different | |
** versions of intersection(). Something like this: | |
** | |
** #if defined( NS_BETTER ) | |
** tStatus intersection( ... ) { | |
** ..Better version goes here .. | |
** } | |
** #elif defined( NS_NAIVE ) | |
** tStatus intersection( ... ) { | |
** .. Naive version goes here .. | |
** } | |
** #else | |
** tStatus intersection( ... ) { | |
** .. Test version goes here .. | |
** } | |
** #endif | |
** | |
** This is the typical way people do this, but I think | |
** explicitly naming different versions of the | |
** implementation makes the code slightly easier to read | |
** (and more importantly, easier to debug.) | |
** | |
** I think I *could* have broken down things into | |
** functions a bit more. On reviewing the code, it seems | |
** the bits in the test driver would definitely be | |
** easier to read if I hid some of the details behind | |
** functions. I've started coding in windows that are | |
** 64 columns wide by 36 columns high (this is the same | |
** aspect ratio of a paperback book.) A decent rule of | |
** thumb is to build functions that fill no more than | |
** one page. But it's a recommendation, not a hard and | |
** fast rule and YMMV. | |
** | |
** And hopefully I've convinced you that writing | |
** comments in code can be a literary experience. | |
** | |
** -Cheers! | |
** -M | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment