great sayings – Benjamin Zander

Last night I had the pleasure (and good luck!) of attending  the concert portion of a fund raiser for the Boston Philharmonic. The director Benjamin Zander was a fascinating speaker and, I think, a fascinating person. He related two things that I really want to incorporate into my life.

First was a view point or if you will mind state: “BTFI” – Beyond The Fuck It!  It’s the point, I think, that you go behond caring what others think. You just reach for it, damn it. You reach the point in something when you say “fuck it” and move past/beyond some barrier.

The second is a very interesting reaction to failure. It completely changes your relationship with failure emphasizing learning from the situation. When you realize you made a mistake, raise you hands in the air, smile, and say “fascinating!” Failure isn’t bad! Failure isn’t something to beat yourself up about. Instead recognize it, smile, and make it a happy learning experience.

I’ve got to add Benjamin Zander to my list of “people I want to have dinner with”. I’m sure it would be enlightening and energizing evening.

sad but good

Seen outside the fire station in Inman square.

making choices

Tim showed me this entry during our once a week meeting:

http://sivers.org/scares-excites-do-it

How right it is. I can’t say I live up to this but I try.

Craig

haiku silliness

I got an email today from my BFF Jess:

From: Jess
Subject: I had to share a haiku
Haikus are easy.
But sometimes they don’t make sense.
Refridgerator.

My response? Of course in Haiku:

my bum is smelly
yes really stinky it’s true
despite that, love me?

thank you ladies and gentlemen a Craig spur of the moment original..

life poem & valentine’s day

I gotta post this before I forget. I wrote these back when I was working on my MS thesis and doing a lot of structured writing. I guess the muse, and the writing muscle, were in peak form. Anyway two poems:

To futures hid in shadows dark
on paths untrod, untouched, unsought.
Pulled toward without control,
spinning onward we do mold.

A path left, a door right
embers of choice die in the night
and high above dreams dart past
make cower us fools–thought they’d last.

No one path, no one opportune
judge ourselves completely fool.
Make what happiness we can take
for know each path regret we make.

—–

Now a poem about that hated holiday:

—–

Valentine’s day is here by golly,
spend not, save your money.
Buy no roses, no long stemmed.
Save your words–sheath your pen.

For Love is not bequeathed just one day,
but in deed and act every day.
Valentines were for profit wrought,
and never truly come from the heart.

So you want to learn Perl?

Read the first chapter of Damian Conway’s book:

Object Oriented Perl: A Comprehensive Guide to Concepts and Programming TechniquesThat chapter is a great detailed introduction to Perl for a person who already is familiar with several programming languages. I love the under-the-hood detail about symbol table objects.

cell phone test

So, you don’t a problem with people driving and using their cell phone?

OK here’s a test then:

If you feel uncomfortable as a passenger when the bus driver is talking on their cell phone, then you are against driving and using a cell phone at the same time.

non-perl interview question

This question I’ve asked a lot. Perhaps too much so this may be my way of retiring it–however how will a candidate know they are interviewing with me (insert manical laughter) ? Anyway, here’s the setup:

• I’m going to be intentionally vague and it’s up to the candidate to ask questions.
• You do not need to implement simple auxiliary functions like swap or random. Just prototype them.

Implement a function, in C, that will randomly permute the order of values in an integer array. In other words, consider the original array a deck of cards and write a function that will shuffle those cards. Note, any value in the array is legal. I usually write this at the top of a piece of paper to get them started:

f(    )

Note, again I’m being intentionally vague. The first question I would ask the interview is, “should this be in place or not?” Not once has anyone asked this question, which I believe to be an excellent question. I kick back and watch them solve the problem. The nice thing about this problem is it is a vague problem with many different solutions. Some of the solutions are good under certain conditions and some are not.

To setup the first of this entry I have to discuss the prototype method for this function. Usually the candidates don’t start with the prototype, going back later to update it as they flush out the algorithm but I have to mention it first so I can use variables. I’m not too concerned about the return value, what I’m concerned about is seeing the candidate making this mistake:

void f(int array[]) {
…
}

yuck. I usually let this go and let them find their mistake later. They often compound the problem by using the compile-time operator sizeof() to get the size of the array:

int n = sizeof(array);

No, this would return 4 on a 32 bit machine. The sizeof operator computes the number of bytes a particular object occupies and this is not a run-time computation on what array points to! You must pass in the size of the array to this function, therefore the prototype must include the size of the array:

void f(int array[], int n) {
…
}

Note that this is also fine:

void f(int * array, int n) {
…
}

Just a thought—I prefer: ‘int array[]‘ compared to ‘int *’ array because it’s unclear if the user is pointing to a single integer or an array of integers (which could have just 1 element). Similar to passing a string to a function, I want to know it’s an array of characters rather than a pointer to a single element. Yes, semantically they are equivalent but I like hints. Which do you prefer?

Back to the problem. A majority of candidates start examining this problem algorithmically first–so that’s where I’ll start. Unfortunately a vast majority of the candidates create a secondary array and then slowly copy elements from the first array to a malloc’ed secondary array. I’ve seen candidates create the secondary array by merely declaring it as a local variable. I do not believe this is dependable C. Some compilers will allow this, I know GCC allows it, but others I don’t think it’s standard to allow arrays of non-const size to be declared as local variables of a block. If someone knows about this, please throw it in the comments section. So there’s a secondary array but then I point out to the candidate, how do you avoid selecting the same element in the original array and copy it to the secondary array? To answer this a MAJORITY of candidates create ANOTHER array, perhaps of booleans, to mark positions in the original array that have been copied (the inverse of this: marking positions as taken in the destination array is the same problem). Uhh…warning! warning! This is not a good sign! So you started with an array of integers, size n, and then you create two more arrays with n elements each? There must be an easier way. I let the candidates write this code. As John Ousterhout said, “the biggest performance increase is from the non-working to working.” If the candidate gets the algorithm working and then through our ensuing discussion sees the error of his ways and handles himself in a professional manner, kudos!

There is an interesting scenario that occurs if the passed in array is large, say > 1,000,000 elements. The boolean array represents what elements have been chosen in the original array and placed in the secondary array:

int *copied = malloc(sizeof(int)*n); // I think better than: int copied[n];
int *secondarray = malloc(sizeof(int)*n);
int pos=0;
for(int i=0; i < n; i++) {
do {
pos = rand(0, n-i);
} while ( copied[pos] == 0 );
copied[pos] = 1;
secondarray[i] = array[pos];
}

Note: don’t forget to copy secondarray back on to array if this function is performing an in place shuffle. If not, change your prototype to return int * and return secondarray at the end of the function.

Here’s the kicker: what happens as i approaches n? More time is spent in the do-while loop searching for a free position. When i==(n-1) there’s a 1 in n chance that a free position is chosen. Note that your algorithm demands n*3 in terms of space. In embedded firmware this is *not* acceptable.

Some candidates jump right to it–walk down the array and randomly choose a position to swap with. Well, this is O(n) (nice!) and doesn’t require a second or third array! (nicex2!) This code snippet randomly chooses a position in the array and swaps it with the last element in the array. Then, it considers the subarray one smaller and repeats until it stops with an array of one element.

for(int i=0; i < n-1; i++) { // note: -1 because you can't randomize an array size 1

int pos = random(0, n-i); // returns random value between 0 and n-i-1, in other words not inclusive.
swap(&(array[pos]), &(array[n-i]));
}

There is a very subtle gotcha here–the algorithm must be probabilistically fair. In other words, you must allow for the possibility that a card will wind up in the same place in the array that it started. The second argument to random must have the chance to choose the same position that you are swapping to–note that the second argument to random is the same as the index in the second argument to swap: (n-i). Lets write out the full iterative code (which I’m sure is going to have errors, please let me know in the comments):

void f(int array[], int n) {
for(int i=0; i < n-1; i++) {
int pos = random(0, n-i);
swap(&(array[pos]), &(array[n-i]));
}
}

Is this probabilistically fair? I think so. Mathimaticans in the audience please let me know.

I like the recursive algorithms (see my previous posts on cribbage scoring algorithm):

void f(int array[], int n) {
if ( n == 0 ) {
return;
}
else {
int pos = random(0, n);
swap(&(array[0]), &(array[pos]));
f(array+1, n-1);
}
}

Ain’t pointer arithmetic cool?

Hands down the best, laziest, slimey-est solution I’ve seen for this comes from Robert Blazewicz:

void f(int array[], int n) {
qsort(array, n, sizeof(int), sortfunc);
}

int sortfunc(const void *a, const void *b) {
return (rand() % 3) - 1;
}

Genius! Brevity is the soul of whit!

new verb?

Main Entry:

po·ta·te

Pronunciation:

\pə-ˈtā-(ˌ)te

Function:

verb

meaning: to be in a comotose or veggitative state on one’s couch.

usage: I’m potating this evening in front of the TV with a pizza and beer.

Gerald Green & College

I’d like Gerald Green, former Celtic, former Timberwolf, former Rocket and now former NBA player, be given some sort of exception so he could go to college and get the basketball education he so desperately needs. He’s a talent–an athletic phenom that needs to develop his basketball brain as well as individual skills. That kind of patience is not going to occur in the NBA in my opinion.