Ask Dr Aybabtu: Interview Question Stumps VB Programmer

Dear Dr Aybabtu,

I recently had an interview with a company that was very strange. They asked me to write a function to reverse a string. I told them that there was a function called StrReverse in VB. Then they asked me to write it in VB 5, which doesn't have StrReverse, and that didn't make any sense to me. They thanked me for coming in and that was that. I haven't heard anything back from them. What do you think happened?

VBWiz


Dear VBWiz,

Dr Aybabtu doubts that you'll be hearing from that company any time soon, but Dr Aybabtu might be wrong. In the mean time, you might want to download Cygwin and learn how to do stupid things on purpose with C. C makes it very easy to do stupid things, so the operative concept is stupid on purpose. What do I mean? Let's take a variation on your problem. Let's interpret a string as a stream of bytes. How might we write a function that reverses bytes read in on an input stream? The UNIX program tac does just this. Here's a stupid way to write it:

#include <stdio.h>

int
main() {
  int b = getchar();
  if (EOF != b) {
    main();
    putchar(b);
  }
  return 0;
}

Writing stupid functions can be great fun! Let's reverse some bytes held in a char array:

#include <stdio.h>

int
main(int c, char *v[]) {
  (*v[1] ? ({
    char c = *v[1]++;
    main(0, v);
    return putchar(c);
  }) : ({
    return 0;
  }));
}

This is especially nice, because it will segfault if you don't give it something to chew on. That's OK, because we're being stupid on purpose. Let's gussy that code up a bit with some macros:

#include <stdio.h>

#define IF(x) ((x) ? ({
#define ELSE }) : ({
#define ENDIF }))

int
main() {
  int b = getchar();
  IF (EOF != b)
    main();
    return putchar(b);
  ELSE
    return 0;
  ENDIF;
}

Pretty sexy stuff. The extra parens in the IF and ENDIF definitions are there to let me do even more stupid stuff, but we'll leave that for some other time. Now for some spectacularly stupid stuff that will actually consume a string and produce a string in the traditional char* sense:

#include <stdio.h>
#include <stdlib.h> // malloc and friends
#include <string.h> // memmove

typedef struct {
  void* car; 
  void* cdr; 
} Pair;

#define CAR(p) (((Pair*)p)->car)
#define CDR(p) (((Pair*)p)->cdr)

Pair*
cons(void* car, void* cdr) {
  Pair* p = (Pair*)malloc(sizeof(Pair));
  p->car = car;
  p->cdr = cdr;
  return p;
}

char
PTOC(void* p) {
  return (int)p;
}

void*
ITOP(int i) {
  return (void*)i;
}

typedef struct {
  char *s;
  size_t len;
  size_t alloc;
} String;

#define STR(x)  (((String*)x)->s)
#define LEN(s) (((String*)s)->len)
#define ALLOC(s) (((String*)s)->alloc)

String*
new_string(size_t alloc) {
  String* s = malloc(sizeof(String));
  STR(s) = malloc(alloc * sizeof(char));
  ALLOC(s) = alloc;
  LEN(s) = 0;
  return s;
}

void
alloc_check(String* s) {
  if ((LEN(s)+1) == ALLOC(s)) {
    ALLOC(s) *= 2;
    realloc(STR(s), (size_t)ALLOC(s));
  }
}

#define STRCHK(s)       if (NULL == s) {          s = new_string(256);  }

String*
appendchar(char c, String* s) {
  STRCHK(s);
  alloc_check(s);
  STR(s)[LEN(s)++] = c;
  STR(s)[LEN(s)] = '\0';
  return s;
}

String*
list_to_string(Pair* p, String* s) {
  if (NULL == p)
    return s;
  else
    return list_to_string(CDR(p), appendchar(PTOC(CAR(p)), s));
}

char*
rev(const char* s, Pair* p) {
  if (0 == *s)
    return STR(list_to_string(p, NULL));
  else
    return rev(s+1, cons(ITOP(*s), p));
}

int
main() {
  puts(rev("abcdefg", NULL));
  return 0;
}

Not stupid enough? How's this:

String*
pushchar(char c, String* s) {
  STRCHK(s);
  alloc_check(s);
  memmove(STR(s)+1, STR(s), sizeof(char)*LEN(s));
  LEN(s)++;
  STR(s)[0] = c;
  return s;
}

char*
rev2(const char* r, String* s) {
  if (0 == *r)
    return STR(s);
  else
    return rev2(r+1, pushchar(*r, s));
}

All of that stuff compiles without error or warning with gcc and CFLAGS = -Wall -pedantic -std=c99, except the ?: tomfoolery. The more stupid things you can do the better, as long as you know you're being stupid and you're being stupid on purpose. Plus, you'll gain an appreciation for high-level languages and Greenpun's Tenth Rule that's been cultivated bottom-up.

HTH,

Dr Aybabtu