Tue Jul 5 05:52:06 UTC 2011

Programming Interview Questions

These are some questions that a major software company asked at a technical interview. First there were basic logic problems, then programming puzzles. Your only tool is a whiteboard.

Logic Portion

  • You have eight weights and a balance beam. Seven of the weights have the same mass and one is lighter. You can't tell by holding them or looking at them which is the light one. What's the minimum number of weighings required to find the lighter one?
  • Highlight for answer: Two. Compare the first three and the second three. If they're the same, compare the other two and find the lighter one. If they're different, compare any two from the lighter set. If they're the same, the other one is the light one.
  • A man is walking through a train tunnel, and he's one quarter of the way through. He hears a train coming from the end that is closer. If he turns back, he'll just make it. If he continues on through the other three-fourths of tunnel, he'll also just make it. How much faster is the train going than the man? Assume both the train and the man travel at a constant speed.
  • Highlight for answer: Twice as fast. Since the train will be at the mouth of the tunnel in the time it takes for him to travel one quarter of the way (back), we know he can make it exactly to the center of the tunnel if he travels forward. Since he can arrive at the exit of the tunnel at the same time as the train, the train will travel the entire length of the tunnel in the time it takes for the man to travel half the tunnel. Bonus question: how far away was the train at first?
  • You have three incandescent lightbulbs controlled by three light switches in another room. There is no obvious order to the light switches, but they are all currently switched off. You have an unlimited amount of time with the switches, but you can only enter the other room and inspect the bulbs once. How can you tell which switch goes to which bulb?
  • Highlight for answer: Turn the first switch on for a while, then turn it off. Turn the second switch on and enter the room. The bulb that is on goes with the second switch, the warm bulb goes with the first switch, and the cold bulb goes with the third.
  • Programming puzzles

    1. Write a class Complex that models complex numbers.
    2. What will the following code output? (Assume code is valid)
      class A
          void foo() { std::cout << "a\n"; };
      class B: public A
          void foo() { std::cout << "b\n"; };
      class C: public B
          void foo() { std::cout << "c\n"; };
      int main()
          C* c = new C;
          B* b = c;
          A* a = b;
          return 0;
    3. Now what if B::foo() is declared virtual?
    4. Write a Drawable base class with a print function, then write a Square class and a Circle class that inherits Drawable and implements their own print function.
    5. Write a function that determines if an unsigned integer is a power of two.
    6. A program keeps a number in integer array in which each element represents a digit. For example, 120 is {1,2,0}. Write a function that increments this number.


Posted by Luke | Permanent link | File under: interview, programming

Tue Jun 14 05:24:19 UTC 2011

Pac-man AI competition

I love these things. I believe I've said before how much fun I had in the Google AI challenge last November, even though the schedule unfortunately clashed with NaNoWriMo so I didn't get to finish my real bot (my test submission finished somewhere in the middle of the pack).

So now the University of Essex is putting on a Ms. Pac-man versus Ghost Team competition. Actually, it appears they have done this before, and they're opening the server back up on July 1st. Incidentally my NaNo novel needs to be finished a few days before that in order to get in on the CreateSpace deal for a free proof copy, so I'd golden!

Now, if they'd only provide different language interfaces I might be in business, but my Java skills are rather weak. I'm working on it for Android development, but a C++ or Python interface would make it quite a bit more accessible to me, and probably a lot of other people too.

Posted by Luke | Permanent link | File under: programming, competition

Wed Jun 1 17:56:16 UTC 2011

Second SSH Configuration Article Posted

I wrote a second SSH Configuration article to cover installation and configuration of DenyHosts. I just installed DenyHosts myself so I thought I'd share my experience. Nobody outside of my home network can SSH into my PogoPlug at the moment, so it's unnecessary for now, but this configuration won't last forever.

I also cleaned up Part 1, which had some redundant information. I'm working on some other projects at the moment, but rest assured I haven't forgotten about the other two parts.

Posted by Luke | Permanent link | File under: ssh, pogoplug

Sat May 21 17:25:43 UTC 2011

Android Hardware Debugging on Arch Linux

I've been tinkering with Android development again, and one of the things that took a little digging was figuring out how to let adb see my Android phone, so I wouldn't have to wait ages for the emulator every time I wanted to tweak something. Google offers instructions for Ubuntu, but they seem incomplete. Maybe Ubuntu does something automatically, but Arch requires a few extra steps.

First, prepare your phone. Go to Menu, Settings, Applications, and enable USB debugging.

Next, Arch will require a new udev rule. Presumably you are using udev on Arch, but if I recall correctly, it's not completely necessary. So if you aren't using it, of course you'll need to install it first. Then, add a rule that will tell udev how to use your phone. Create a file in /etc/udev/rules.d/51-android.rules and enter:

SUBSYSTEM=="usb", SYSFS{idVendor}=="0bb4", MODE="0666"
Note that idVendor "0bb4" is for HTC phones. Go here to find the appropriate vendor ID.

Now for the extra steps. We need to reload the udev rules, so udev actually knows what it's looking at:

sudo udevadm control --reload-rules

On top of that, assuming you've already got Eclipse open, you'll also need to restart the adb server:

sudo adb kill-server
sudo adb start-server

Should be all set! Go check:

adb devices
You shouldn't get a bunch of question marks this time. Now get coding!

Actually, if you're like me and tinkered with Android development a long time ago, Eclipse might show a problem with your project even though there doesn't appear to be anything wrong. Having virtually no familiarity with Eclipse (or any other IDE, for that matter), it took me a while to find out that the problem was something about an expired debug certificate. Apparently the Android SDK expires these a year after you start. Simply delete ~/.android/debug-keystore and restart Eclipse, which will generate a new one for you. NOW you can get coding!

Posted by Luke | Permanent link | File under: android, arch

Sat Apr 30 02:34:02 UTC 2011

New PogoPlug Article Posted - SSH Configuration

The PogoPlug SSH configuration article is finally posted! If you're just joining us, this series of articles documents my adventures setting up my PogoPlug with Debian Linux and running this website on it. I have two other PogoPlug articles planned, with one of them about halfway done.

Now, time to get started on Ludum Dare 20: It's Dangerous to Go Alone! Take This!

Posted by Luke | Permanent link | File under: ssh, pogoplug

Thu Apr 28 14:24:29 UTC 2011

Pyweek 12 results and Ludum Dare 20

Well Pyweek was a bust. I didn't get a whole lot done despite having some free time at the beginning, and then halfway through the week I lost all my free time so it was dead in the water. The theme was Nine Times, and I had planned a fairly simple war strategy game where the player would be able to fight the nine most important battles of western civilization. So as you can imagine, I may have spent way too much time trying to decide which battles I should use instead of coding. I did manage to finish a map for the Battle of Salamis, a menu, and a little bit of the logic. Not enough, unfortunately, to even play, let alone submit.

Anyway, Ludum Dare 20 is just around the corner now, so I've got a shot to redeem myself. Theme voting is underway, and this time I have no idea what's likely to win. Instead of Pyweek's five possible themes, Ludum Dare has over 100! That helps, I think, because you can't think too hard ahead of time until the final round of voting (which should start later today), where the top themes from the previous rounds are pitted against one another.

So that's what's up for the weekend. Don't wish me luck this time, because it didn't work last time!

Posted by Luke | Permanent link | File under: programming, competition, ludumdare

Sat Apr 2 05:08:11 UTC 2011

PyWeek 12

Ah, just barely caught it in time! PyWeek starts in 19 hours at the time of this writing, and it should be quite an interesting one. The theme is not chosen until the shotgun start, but here are the five choices:

  • Coughlin Brothers Mortuary
  • A Fry Cook on Venus
  • Warm and Soft
  • Sausage King
  • Nine Times

Now, sharp-eyed children of the 80's (or earlier) will recognize at least a couple of those from Ferris Bueller's Day Off. Some interesting possibilities here! Coughlin Brothers Mortuary immediately brings to mind zombies, which everyone seems to love...though I find them a tad overdone. A Fry Cook on Venus sounds fun for a space setting, but seems a bit limited. Sausage King has plenty of potential, but Warm and Soft and Nine Times are wide open for interpretation, so those earned my top two votes.

I'm woefully unprepared for this, unfortunately. I've tinkered with PyGame and Pyglet in the past, about the same amount. Of course this is not to mention that I've still only dabbled with Python, never writing a program more than a couple hundred lines long. I'll probably do a little refresher with PyGame. Hopefully I'll get to submit something simple and ugly just to produce something playable, as it's been some time since I've done that. Wish me luck!

Posted by Luke | Permanent link | File under: programming, competition

Wed Mar 2 05:56:58 UTC 2011

Programming Fonts

At some point in a programmer's life, whether it's driven by a colleague's suggestion, a particular occasion where their normal choice is either not available or not working for them, or just plain curiosity, there comes a time when they'll want to experiment with other monospace fonts. I had such an experience recently, specifically of the type where my normal choice just wasn't cutting it. I have a laptop and a netbook at home, and my wife had the laptop when I wanted to tinker with my PogoPlug. So I fired up the netbook, on which Ubuntu 10.10 is currently installed, and found that the reduced screen size was far too limiting for the default GNOME Terminal font. Combine that with the fact that my slobbery infant somehow disabled the touchpad so I couldn't scroll, and suddenly a new font was completely necessary.

Now there are pretty much two kinds of fonts: bitmap fonts and antialiased fonts (these include outline and stroke-based fonts). Historically bitmap fonts were the way to go. They are usually optimized for small sizes, which makes them perfect for the netbook. This is not to mention that my full-sized laptop, running Arch Linux and a custom OpenBox environment, uses the default "Fixed" bitmap font in xterm, which I quite enjoy. Unfortunately my wife was on Windows so I couldn't just SSH over and grab my xterm configuration, so I figured I might as well just make GNOME Terminal do what I want. But making GNOME applications aware of bitmap fonts proved to be a major pain. The usual step:

sudo dpkg-reconfigure fontconfig-config
wasn't doing anything for me. A bit of googling turned up the manual way, which worked:
cd /etc/fonts/conf.d
rm -f 70-no-bitmaps.conf
ln -s ../conf.avail/70-yes-bitmaps.conf
fc-cache -fv
Now I was in business! The Fixed font was now available for GNOME Terminal. But what about other fonts? Fixed looks good, but naturally I'd come across various posts and articles like this where programmers would extol the virtues of their favorite fonts. So why not try some of them on my own?. I'm in the process of finding one for myself, but this isn't an objective exercise. It doesn't make sense to make a list of the top ten best programming fonts. But it does make sense to list fonts to try. These particular fonts are all free of charge, since I don't believe it is necessary to pay to find your favorite font. However, once you dig into the world of fonts it's easy to appreciate the work that goes into these things! Most of these are probably Free as in Freedom as well, but I didn't check since we're just looking for something for personal use. Make sure to check the license if you want to distribute or use them in commercial projects.

Bitmap fonts:

  • Proggy fonts - Awesome group of fonts that I see recommended all over the place. I really, really wanted to try Tiny for my netbook, but for some reason pango couldn't handle it. I'm currently using Progsole, which is the same size, but I'm not completely happy with it. I prefer the slashed zero variants over the dotted zeros. Also note that Dina can be found here as well, which is another highly regarded font.
  • ProFont - also had trouble getting this to play nice in GNOME, sadly, as I really wanted to try this one.
  • MonteCarlo - contains optimized bold versions. Not quite a fan of the non-bold "soft" (traditionally called italic, though that usage seems to be falling off since italic usually means slanted letters) lowercase A, personally. If it must have a soft lowercase A I'd prefer the ProFont version, otherwise I like the upright (sometimes called double-storey) version.*

* Interesting aside: the Ubuntu font (which this website uses unless you've overridden it) uses the upright lowercase A normally, and the italic lowercase A in italics.

Antialiased fonts:

  • DejaVu Sans Mono - Note that this is the same as Bitstream Vera, just including more international support. This is my goto font on large displays, and is extremely convenient because it's available on pretty much any Linux installation out of the box.
  • Inconsolata - a highly-regarded Free font inspired by Microsoft's much-lauded Consolas font.
  • Anonymous Pro - another highly-regarded Free font. From the screenshots it looks great at large font sizes, and for smaller sizes it comes in bitmap versions. Currently trying this one on my full-sized laptop in size 9, and I am quite enjoying it!

Either way, a simple search for programmer fonts will yield far more than I can list here. Happy font hunting!

Posted by Luke | Permanent link | File under: fonts

Mon Feb 21 01:53:59 UTC 2011

Full Listing of Conky Colors

Okay, so maybe this was obvious to most Conky users, but I couldn't find a full list of the "shorthand" colors that you can use in a Conky set up. If you're like me, you copied somebody's .conkyrc that came with some colors like "hotpink" and "black," and some others in the usual hex triplet #RRGGBB format. If you're like me, you wanted to modify your setup but ended up going with hex triplets for colors because you couldn't find a reference.

Well, I downloaded the Conky source code to investigate. First I grepped for hotpink, since I figured it wouldn't show up anywhere but a listing of colors. No results. So in the src directory I found colours.h, pausing a moment to mentally poke fun at inferior British English spellings. Right there at the bottom we find:

long get_x11_color(const char *);
Ah ha! So there you have it: Conky accepts all X11 colors. The Graphviz project has a nice colorful table containing all of the colors here. Wikipedia also has the names and an explanation of the color variations (e.g. hotpink4) here

Posted by Luke | Permanent link | File under: conky

Fri Feb 18 05:59:06 UTC 2011

New Article Posted - Debian on the PogoPlug

If you wondered why I started this blog and promptly disappeared, well now you know! I was gathering and organizing my notes about my adventure with the PogoPlug, on which this site is running. Sipping just 8 W of electricity, I might add!

Anyway it's a bit on the lengthy side, partly due to my natural verbosity, but partly due to my desire to go slightly more in depth with the explanation. Despite the length, I only managed to cover the initial configuration. I plan to go more in depth on setting up SSH in the next article, and then another for setting up nginx and Nanoblogger. I had the SSH stuff in this one, but decided against including it to keep the size down.


Posted by Luke | Permanent link | File under: debian, pogoplug