So you say that programming language choice does not matter …

One popular interview question that never dies : write some code to reverse a singly linked-list.
Now understanding the problem for interviewees is one thing but getting it right in an imperative language seems to be quite a feat based on my experience as an interviewer. Most take 15-20 minutes to get this completely correct and sometimes even longer.

Here’s a quick solution that took me 10 minutes (in C) :

#define LIST_SIZE 10000000
#define SHOW_SIZE 5


typedef struct node {
  struct node* next;
  int   val;
} node; 


int main(int argc, char* argv[]) 
{
  int i;
  long start, end;
  node* head = malloc(sizeof(node));
  node* cur = head; node* cur2 = head;
  node* prev = NULL; node* next = NULL;

  // init linked list
  printf("         linked list : ");
  for (i=1; i <= LIST_SIZE; i++)
  {
    cur->val = i;
    if (i < SHOW_SIZE) printf("%d -> ", cur->val);
    if (i != LIST_SIZE) cur->next = malloc(sizeof(node));
    cur = cur->next;
  }
  cur = NULL;
  printf(" ... (%d more)n", LIST_SIZE - SHOW_SIZE);

  // reverse linked list
  start = clock();
  while (cur2 != NULL)
  {
    next = cur2->next;
    cur2->next = prev;
    prev = cur2;
    cur2 = next;
  }
  node* head2 = prev;
  end = clock();

  printf("reversed linked list : ");
  for (i=1; i <= LIST_SIZE; i++)
  {
    if (i < SHOW_SIZE) printf("%d -> ", head2->val);
    head2 = head2->next;
  }
  printf(" ... (%d more)n", LIST_SIZE - SHOW_SIZE);

  printf("Elapsed time: %.3lf msecsn", (double)(end - start));
}

The code is fairly straight-forward for anyone familiar with C. Think about it though, when someone is under pressure to answer this question and they are coding this up on paper for the interviewer there are about 50 lines of code in which the interviewee can go wrong.
This is the imperative paradigm that most programmers live with on a daily basis and which they need to prove they can deal with in many interviews every day around the world. To make it worse this is also the only paradigm that most interviewers really know.

Now the equivalent in a functional language is a one-liner (in Clojure) :

(let [nums (range 1 1e6)] 
     (time (take 5 (reduce (fn [rlst item] (cons item rlst)) '() nums))))

So at the low-level of a developer’s daily life experience with imperative languages, how many programming bugs happen as a result ? What about lost time and the individual productivity ?
Moving up a level : what does this do to the team’s productivity ? What is the ‘new feature vs. fire drill’ ratio for this team that is forced to worship at the altar of imperative languages by academia and industry ?
Now on the macro level translate all this into costs in time and lost revenue for a company. What is the estimated percentage of lost revenue and profit due to being stuck with this paradigm ?
Middle-management’s sales-pitchy MBA approach to software developer fungibility and hence their love of lowest common denominator languages costs companies untold losses in the millions. They have also been much of the cause for a generation of below-average programmers.
(The cancer that is the MBA club in the world of software development is a topic for another essay).

Language matters at all levels.

Leave a Reply

Your email address will not be published. Required fields are marked *