Writing

Feed Software, technology, sysadmin war stories, and more.

Saturday, March 19, 2022

Where the time went during a "laptop" coding interview

Have you ever wondered where the time goes during a "laptop" coding interview? This is one of those things where you bring in your own little laptop computer (or, they supply one, I guess) and you are expected to solve some problem on the spot. They give you maybe 60-90 minutes to do this, and they want to see it work, and have tests, and all of that good stuff.

The interviewer hands you a piece of paper and may or may not discuss it. Then they set you loose and disappear for a while. It's just you and your little machine, and maybe some music if you thought ahead.

Where does the time go? The last time I went through it, it went something like this in my head:

(looks at paper) huh, okay, so, what are they giving me here. I have to go get some text files from some Dropbox thing. Okay, get on their guest network, go scarf down their files. Two input files, two output files. I'm supposed to take the input and turn it into the output by running some algorithm they explain on rest of the sheet of paper.

The file is line-oriented, such that the first line is a number, and that says how many data lines will follow. Then they have that many more lines, each with two numbers split by a space. This didn't come from a DOS machine so it's not CRLF, at least. It didn't come from an old-school Mac so it's not a bare CR, either. It all ends with just a line feed, typical Unix stuff.

Right, so, I have to figure out some method to solve the actual problem they gave me, and then I have to write it. But, I also need all of the stuff required to actually inhale this file and get the data to run through that "engine" I end up writing. Joy.

So I guess I can just write something terrible to use fgets to read through this and give me a bunch of lines, then chop it up in some really terrible way, mash it through strtoul or something to make values out of them, and then probably call into my "engine" with the two arguments. Joy.

Right, so, let's get going on the base level stuff and hope the algorithm starts setting into place while I do this. I kinda-sorta have some idea for how to handle it but will need to try it and see how it goes, and I can't do that until I get something to actually throw numbers at it.

Let's get to it, then. Hum, well, I don't have any of my personal library stuff here, so I guess I get to code it all up the old-school way. Also, what are they going to be building this on? I have no idea where they are in terms of compilers. Let's assume C++98 just to be safe.

Okay, need to get the file, then read the file, so...

int main(int argc, char** argv) {
  if (argc != 2) {
    fprintf(stderr, "usage: %s <file>\n", argv[0]);
    exit(1);
  }

... and of course this means we need stdio.h for fprintf and stdlib.h for exit right there, so add those #includes at the top.

Keep going. Open the thing and yell if it's not there. I normally have my own LOG stuff but not here. Failing that I'd usually fprintf something to stderr, give it a message and a format string and then jam strerror(errno) into it, but time is short. perror is yucky but it's faster, so screw it, use that.

  FILE* f = fopen(argv[1], "r");
 
  if (!f) {
    perror("open");
    exit(1);
  }

And now we need errno.h, too. Go #include that.

Time to get that first line. Let's just read it and totally ignore the fact that it could EOF on this read and we might not get anything, because, again, pressed for time here. Crap, this is going to suck.

And, uh, crap, fgets leaves the newline on the end, so I have to tie that off. Again, I guess I'll just assume I got something more than an empty line here and assume I can subtract 1 from strlen without going into the weeds. This is exactly why I have all of this fancypants read-file-to-line stuff at home that was so painstakingly written!

  char buf[1024];
 
  fgets(buf, sizeof(buf), f);
  buf[strlen(buf) - 1] = '\0';

Dirty. So dirty. And now we need a number from that. strtoul would be the right sort of thing, then all of the error checking you're supposed to do, but that's a ton of work, and again, none of my home library set is here to save me (which already has that work done in it). Screw it, atoi, and hope nothing comes along which doesn't work with that.

  int input_lines = atoi(buf);

[ Time check: it's already taken me 17 minutes just *writing this post* to get this far down. I'm going based on my notes and the code from that day several years ago. Tick, tick, tick. ]

Better say what I got for debugging purposes. Use stderr so it doesn't corrupt the output.

  fprintf(stderr, "XXX input lines: %d\n", input_lines);

Now I guess it's time to start a loop that reads this crap and splits it up and stores it somewhere. So, uhm...

  map<int, int> input_jobs;  // key: start time, val: run time
 
  while (fgets(buf, sizeof(buf), f)) {
    if (strlen(buf) < 1) {
      continue;
    }
 
    buf[strlen(buf) - 1] = '\0';
 
    char* sp = strchr(buf, ' ');
 
    if (!sp) {
      fprintf(stderr, "bad line (no space): %s\n", buf);
      exit(1);
    }
 
    *sp = '\0';
    char* len_str = sp + 1;
 
    int start_at = atoi(buf);
    int run_for = atoi(len_str);
 
    input_jobs[start_at] = run_for;
  }
 
  fclose(f);

SO MUCH BADNESS HERE. Gotta go add stuff up top: #include <map> and using std::map. I really hope they don't give me a duplicate start time or I'll squish the previous one. (I think they said something like "this won't happen", but why would you ever trust that?)

Again with the blindly assuming we have usable data for atoi... and the bad line thing with no space thing, well, that's also not supposed to happen, but again, I don't trust them that much. I'm willing to barrel through some stupidity, but this would do terrible things when it gets a NULL back from strchr and then tries to dereference it later, so instead of writing yet another terrible '80s C pointer hole, let's just die.

Oh yeah, I guess I should make sure they gave me what they told me they'd give me, since I'm reading to EOF.

Go back in above the loop...

  int actual = 0;

... and in the loop ...

  ++actual;

... and after the loop:

  if (actual != input_lines) {
    fprintf(stderr, "expected %d got %d\n", input_lines, actual);
    exit(1);
  }

Right, so now I'll know if that's screwy for some reason at least.

[ Time check: 27 minutes elapsed in writing this post. ]

Now I guess I get to iterate through the data I read and do something useful with it. Oh yeah, by reading it in first and not "streaming" it, I've basically committed myself to an O(n) memory situation at best, and it'll probably end up worse than that. So this temporary "read into a map" thing will probably have to go at some point, and I'll call into the "add something I just parsed" from inside the for loop. Joy.

Anyway. Iterate. But, okay, C++98, so old-school iteration, none of that "for const auto" stuff.

  map<int, int>::const_iterator ii;
 
  int job_count = 0;
  for (ii = input_jobs.begin(); ii != input_jobs.end(); ++ii) {
    const int& start_time = ii->first;
    const int& run_time = ii->second;
    add_job(start, time, run_time, job_count++);
  }

And obviously now we need something up above main that'll do this add_job, so let's write a stub to get that started.

static void add_job(int start_time_raw, int run_time, int job_number) {
  fprintf(stderr, "XXX add_job %d | %d | %d\n\n",
          start_time_raw, run_time, job_number);
  // XXX write me
}

Okay. I'm going to stop there for now. Realize that what you're seeing is the *final form* of that code. There's a bunch of stuff that happened in-between. For example, see how it's called "start_time_raw" in the add_job function? That's because the start time value from the file turned out to be "HHMM". That is, 12:00 noon was in the file as "1200". 1:45 PM was in the file as "1345".

I had initially parsed it as something in the range 0-1439, because, well, given a system that lets you schedule stuff at a given time during the day with one-minute precision, personally, I'd be using the "number of minutes since midnight" as the base. They weren't. They were using human-readable time less the usual colon we put in the middle for readability!

How did I know 1439? I've written schedulers before, and a normal civil day that doesn't have any DST transitions in it is 1440 minutes long: 24 * 60. I also know from writing those same schedulers that a week of those same non-DST days is 10080 minutes long, because that's just 24 * 60 * 7, and you run into that number a lot. It gets baked into your head. Or at least, it got baked into *my* head. What can I say, I'm weird like that.

So, it's start_time_raw because it hasn't been split up and turned into a value that'll make sense inside an array. The first bits of code in the eventual add_job() ended up doing something terrible to change HHMM into "minutes since midnight" in the range 0-1439, like this:

  int start_hour = start_time_raw / 100;
  int start_minute = start_time_raw % 100;
 
  int start_time = start_hour * 60 + start_minute;

Awful, right? No sanity-checking. It just mods and divides and multiplies and adds and off it goes.

Now, at this point, I haven't done one damn thing towards actually working on the algorithm, and so I haven't even talked about it here because I wanted to point out how much time goes into just getting the foundation in place to let you actually do anything with the data.

Getting a filename, opening the file, reading the contents, turning them from text into numbers, putting them somewhere sensible and then starting to iterate through them takes some amount of time. If you know exactly what you need when you sit down and start typing, you can probably rip through it in, I don't know, maybe 15-20 minutes?

But, can you do it in an interview, away from your usual setup, on a laptop keyboard, with the laptop screen, in a funny chair, on a weird desk, with the clock ticking, and someone (in theory) keeping tabs on you? Also, you have the possibility of not getting the job riding on this. You probably need the job to make money to keep your house or apartment, feed you and your loved ones, and all of that good stuff.

But hey, no pressure.

I went through this, and I had nothing at stake. If I didn't get the job, big deal. I didn't need the job. I'm also significantly older than your average new grad and have been worn down into not putting too much of my self-worth into what these interviewers might think of me or my code.

Also, I've done this whole "argc, argv, fgets into buf, squash the newline, do it in a loop, chop it up on a space and deal with the results" in C probably over a hundred times in my life up to this point. I know all of the parts. I also know what parts can go wrong. I had to make a decision of what to skip and what to keep in terms of sanity-checking in the name of saving time. I didn't have to spend time trying to make that work. Someone who hasn't been down that road yet wouldn't have it so easy.

But... even so, I was still sweating like crazy, and felt like shit when it was over... even though, again, nothing was riding on this. If I didn't get the job then I wouldn't end up coworkers with some of my friends who wanted me there and had invited me to interview there. I'd just go back home and keep writing snarky tales about the industry, like this right here.

Now imagine you're 22, you need the job, and all of that stuff. You have actual things at stake. Imagine how you'd feel, and what that would do to your problem-solving skills in the moment with that level of stress.

Incidentally, when it came to this problem and I finally started working on the "engine" and the algorithm, I picked the wrong implementation. I wound up focusing on the wrong "axis" in terms of how I imagined the solution working, and caught myself in a dead-end corner. Ironically, my experience doing a scheduler (for people) previously had pointed me at trying to use that as the solution, and it didn't work for what they wanted here.

It wasn't after disconnecting from the problem and spending some time away from the computer that it came to me and I figured it out.

What's that? You don't have the time to disconnect and then come back to it, because you're being timed, and they're coming to check in on you soon? Too bad! Good luck figuring out where you went wrong.

That. That right there is where the time goes.

...

Pre-emptive sidebar: "she should have used Python". Just go away. You are *so* missing the point.