Interviewing for a Microsoft Internship. Part deux.

I got the job!

All in all it was an amazing experience. Even if they hadn't hired me I still would have been pretty happy. I said the same thing to the recruiter before they gave me the offer. I got the chance to have dinner and talk about programming with extremely bright people. I met really nice and smart people from my own country and now we are going to be working at the same company; most likely not on the same team/group, but still...

I went to Vallarta for three days. My dad, a businessman, made a "business meeting" in Vallarta so that he could accompany me.

The hotel didn't give me room right away so I stayed at my dad's studying and smoking. I was pretty paranoid so I was making sure that I knew the stuff I put on my CV as deeply as possible. When I was taking a smoke-break next to the window, I saw other interviewees chilling out. Having some drinks and spending time at the pool. In retrospect, that is how I should have spent the day. Nothing I studied during those hours directly helped during the interview, but it possibly helped my confidence

We were invited to have dinner with the interviewers the night before. We were told it wasn't an assessment. Someone earlier explained to me in business-speak what an assessment is. It is a meet in which the candidate feels comfortable in a non-interview like context, while the interviewers are taking notes on his behavior. Anyway, according to them they weren't doing that. There were three tables set up and I chose the one John Guin was sitting at. Both because the prettiest girl was sitting there and because John was hilarious. Turns out my choice of table was pretty good since Mike Fortin came to our table and sat next to me.

For the next couple of hours I had a great time talking to Mike and John about what's it like to work at MS, about their backgrounds, we even spent time talking about the version control system they use at Microsoft. Mike introduced himself as the guy you can blame Windows Vista on. He is in charge of the team that is responsible for Windows being fast. Hardcore stuff. I took the risk and told them that MS Paint sucks. Fortunately they agreed. Paint sucks. Not only was the dinner delicious and the conversations interesting, but I made a good impression on Mike which helped me when he ended up interviewing me, praise Zeus.

I returned to my hotel so excited that instead of sleeping I spent a couple of hours at the bar with a bunch of drunken Canadians, my dad and his friend.

My interview was supposed to be at noon, but they moved it to 7:30 am a couple of days prior. I only slept about 4 hours but the adrenaline of the next day was enough to compensate. The Microsoft guys were nice enough to get us breakfast at their hotel since ours didn't serve until later. The interview began at 7:30 sharp.

We were taken to a room within the conference center. There were cookies and soda. Within a minute or two a small army of interviewers came into the room calling people by name. Slowly, pale students and recent graduates were standing up.

I had four interviews. All of them consisted of around ten minutes of talking about my interests and around 40 minutes solving a coding problem. There were no whiteboards in the conference center's rooms so the small point markers I bought were pointless (no pun intended). We wrote code on paper. I always kept in mind all the tips I read from the Internet.

Donna, my first interviewer told me that Manav, the guy who interviewed me in Mexico City had put in a good word for me during dinner. That was a tremendous boost of confidence. She made me write an algorithm involving linked list. It was pretty easy but I chose C so I could show her that I knew how pointers work. She gave me some tips and we wrapped it up.

My second interviewer was named Bambo, and he started off telling me that with my math background maybe I could find an formula to the solution of an algorithmic problem involving consecutive letters in a string. I spent a couple of minutes thinking and I found a solution only to realize that I hadn't understood the problem correctly. He posed to me another problem and I went on to try to find a formula for the solution. I realized too late that this time what he wanted was code. I told him "damn... I'm not doing well"; he just laughed and told me that the point of the interview was to find out how I think. I shrugged it off and told him that he had gotten me into math-mode; so he changed directions and asked me how I would test a dialog box. Then he asked me how I would test Notepad. He complemented me on not giving up on a problem and he finished the interview. My confidence dropped after the interview but I found out that Mike was interviewing me next so I got pretty excited.

Mike started of saying that I asked some good questions the night before. He asked me if I wanted to go right ahead to the coding but I was a bit tired so I told him to ask me some questions first. He asked me what was my favorite program that I have written. I told him about an Internet proxy I wrote to substitute all images in websites for a picture of myself on my mom's computer. He laughed and then asked me what was my most difficult program. I told him about the shadowing in pycave. The problem I had to code was to determine if a matrix has a copy of a smaller matrix within it. After I finished, he told me if I had any questions and I asked just the right question to get him to ramble for 10 minutes about some awesome stuff his team is working on.

When I returned to the main room, there were only two guys left. Most of us only had 3 interviews and as far as I know they hired three of us that morning.

My fourth interview was with a guy named Nar. He works on device driver architecture for Windows. He asked me about Haskell and then he asked me to find an algorithm to find the largest palindrome within a string. After staring at a piece of paper for a couple of minutes he told me that I could find a solution in O(n^3), O(n^2), but he didn't expect me to find the linear solution. I found a quadratic solution but it took too long to write and we didn't have time to test it or for me to ask him questions.

When I was waiting in the room for the last time, I was drinking coke and smoking my fifth cigarette. Suddenly I heard my name and nervously walked to the aisle. There was my recruiter and my four interviewers waiting for me. I didn't realize what was going on until Mike told me congratulations. The rest of my memory is a bit of a blank. Happiness and rainbows.

Tips for the interview.

This is subjective but I believe this is what helped me:

Be methodical. Understand the problem. Plan the solution and *then* code. I did this in all but the second interview and got complemented on it.

Show passion: I made a good impression by having projects of my own and by getting excited when talking about programming.

That's pretty much it. I asked them during dinner what is it that they're looking for in candidates. Mike told me: Intellectual horsepower and passion.

I will have to leave school a month early for my internship. I'll see how I deal with that. I'm excited and I can't wait to leave. It's going to be a great summer!

I will blog as much as I legally can about my experience the next summer =).

Interviewing for a Microsoft Internship (Part one)

I haven't posted anything in quite a while now; I figured this is a good time to start writing again. It was not an uneventful year, but I didn't feel like writing.

A couple of months ago I got an email sent to the CS students at UNAM about Microsoft recruiters coming to interview people who wanted to do an internship. The day before I spat out a résumé and decided to go. They did a presentation and asked some coding questions to the audience. Some guy got a Zune for answering something. I got a frisbee for participating...

A mexican Microsoft employee talked with me for about 30 seconds and then asked me to write code on a piece of paper to recognize a very simple regular expression. When I finished, he told me that I shouldn't have used pseudocode. That if I made it to the next interview, it could kill me.

I didn't feel very confident; wasn't sure if I'd make it to the next step.

I got an email a couple of weeks later asking me to go to the Microsoft Mexico offices to be interviewed by someone called Manav. The interview, during which I had to write an algorithm to check if two rectangles collide, lasted around 25 minutes. Since I like making games, I have written that thing a thousand times; still, I got nervous and screwed up one of the cases. He told me and I had to correct it.
The interviewer was really nice. I told him that I recognized him; that I had googled him (In retrospect, maybe it would have been better to say I binged him =P). He asked me if I had any questions and all I could think to ask was "How did I do?"

It took them a while (more than a month) to send me an email. An hour ago I got one inviting me to Puerto Vallarta to be interviewed once again next week. I wasn't sure about it, since I told him that I was a graphics geek and then had trouble writing in the whiteboard one of the most common things to write in graphics. Still, I landed the interview and I am feeling confident that I can do well.

It is the last week of my school term, so this means that starting today my time will be mostly spent practicing Topcoder problems, and not so much studying and doing homework. I may have to speak to a teacher to take the exam/turn in the homework after the interview.

I really hope to get hired. It would be an amazing experience.

Original Futurama cast is comming back!!

About a month ago, I sent this email to the casting company that was calling for new voice actors for futurama:

Please, do tell those suit-wearing cheap monkeys at Fox to use the original cast.

Sincerely, the Internet.

About 20 minutes ago, I got this response:

Dear Futurama Fan,


Thank you for voicing your strong support for Futurama and the original voice cast. We appreciate the time you took to fire off a thoughtful and/or concerned and/or homicidal e-mail message to our casting director, Scott Muller. (Rest assured, not a single one of these e-mails reached the actual decision-makers at 20th Century Fox Television. For future reference, please note that Scott Muller is in fact one of Futurama's biggest fans, and was instrumental in bringing about the return of the cast. Please hoist a bottle of Olde Fortran for Scott!)


Speaking of the cast returning... good news, everyone! The cast is returning! All of our series regulars are back in action for Season 6. Billy West, Katey Sagal, John DiMaggio, Maurice LaMarche, Tress MacNeille, Lauren Tom, Phil LaMarr, and David Herman are all on board and have already begun delivering their customary virtuoso performances. The all-new Futurama episodes are slated to air on Comedy Central beginning in June, 2010.


We are extremely grateful for the outpouring of support for the series. Your loyalty over the years has kept the show going through its original four seasons on FOX, its subsequent reincarnations on Adult Swim and DVD, and now its Bendiferous return to life on Comedy Central. See you in the (near) future!


Sincerely,

David X. Cohen & Matt Groening

Good news indeed!

Clojure optimization of constants

(I actually read about this trick on the clojure user group, but I can't remember where.)

This is a neat trick that eliminates boxing/unboxing overhead when you are using Integer and all you need is int.
(This of course works for the other java primitives)

Let's do something stupid like summing up two Integers ten million times.

(def times 10000000)

(def w 640)
(def h 480)

(time (dotimes [i times]
       (+ w h)))

This little test took around 950ms on my machine.
The w,h values are unboxed from and boxed into Integer classes in order to be used.

Now consider this:

(defmacro w [] `(int 640))
(defmacro h [] `(int 480))

(time (dotimes [i times]
       (+ (w) (h))))

This is a very smart macro trick that I read on the Clojure user group. What it does is it substitutes (w) with a java primitive at compile time.
On my machine, the benchmark took around 430ms.
The problem is that it is ugly, but that can be fixed easily.

(defmacro const-int [name val]
 `(defmacro ~name [] (list 'int ~val)))

(const-int w 640)
(const-int h 480)

(time (dotimes [i times]
       (+ (w) (h))))

Still around 430ms. There is no performace cost because of the way macros are evaluated.
const-int is a macro that creates a macro so our definition looks prettier. The only caveat is you still have to use (w) instead of w.

pyCave: Porting to mac.

So for the past couple of days I have been porting pyCave to my mac. Yesterday was the day I thought the work was pretty much finished (It's not).

I did it by starting with a GL demo written from scratch, and I went up from there adding features until I had a working copy of pyCave. Obviously, there was a lot of copy-pasting, but the overall writing involved a lot of redesign that ended up touching the whole program. The diff file was huge.

This wasn't the original plan. The 'project' was called 'glui'. It was only a module to build GL user interfaces. It eventually morphed into a new version of pycave =). There was only a single commit. Bad idea. But the code is the product of an intense non-stop coding session.

One of the first changes was adding an opengl extension checking mechanism. I found a nifty thing that pyOpenGL had. Every extension module has a member called EXTENSION_NAME. I used that to check for extensions in a very concise manner.
Little did I know that the nifty feature is actually only featured in the latest releases of pyOpenGL 3 (ubuntu beta releases don 't have it).

So i'm thinking that I'll include a subset of the latest pyOpenGL (3.0.0) so that I won't get emails from ubuntu users with Nvidia cards saying that the game doesn't run.

The game runs almost perfectly on my Macbook with Python2.6. I was going to write about the hell I went through compiling pygame for Python2.6 on a mac (it's practically impossible), but it's a long story. I had to do it because I had screwed up the default Leopard python instalation thanks to a very stupid bash command.
Today I fixed my pretty apple-provided Python and tried to run pyCave (practically all my users will do the same).

It actually crashes.

The 2.5 and 2.6 versions have the same PyOpengl (release candidate 1). It is a very strange bug and I think my frankenstein python2.5 instalation is to blame. I am not sure.
A friend of mine just got a brand new Macbook (lower-end) and I would love for him to let me borrow it for a half hour to do some testing.

I am very optimistic that my 6 year old laptop will be able to run the game. It already does, but there is an odd bug in which all the edges are highlighted. It looks awesome with the proceduraly generated tunnel =) It also has the extension-checking bug, which should be fixed by adding the OpenGL module inside the pyCave distribution.

pyGame beta

I have had this little game brewing for too long. It's a small program. Around 2,000 lines of python.
I tried to keep it as "from scratch" as possible. I didn't have a dependency on pygame until I had to add music. I wouldn't hesitate to remove the pygame dependency if I found a lighter cross-platfrom sound library that was as simple to use as pycave.mixer.

I am not using shaders. Shadows were implemented after reading lots of papers with a depth map using OpenGL's fixed functionality. I want to write a more sophisticated shadowing algorithm but it would be too painful without using shaders. I may add the functionality to pyCave but it may be out of the scope of the project, and it would introduce too much pain (see below on porting).

A few weeks ago I released a first beta to generally good reviews. Some people find it too difficult, while others (myself included) find it easy until they reach hardcore mode.
I have learned a few things about pyCave. First, dealing with video card drivers is a pain. Most laptops with intel integrated cards won't work. They just render a black screen instead of showing the menu. I think it's because they don't support multi-texturing without using an opengl extension. I will prove it soon enough with the new interface code that I'm writing.
There was a very strange bug caused by trying to clear the stencil buffer. On my macbook it caused a bus error (mac-speak for segmentation fault). A friend running linux on a lap also had a segfault. I guess it was the same bug. I just removed the line since I am not using the stencil buffer =) It was just a left-over from when I was implementing shadow volumes.

Right now I'm working on making it more cross-platform. I wrote a little python module to check for available extensions. I am changing some abstractions in order to make the menu code less horrible. I will be happy when pyCave runs on my Macbook and another dying 5 year-old laptop.

For now, If you are on a desktop computer with an Nvidia graphics card, you can get pycave from

http://pycave.sourceforge.net/index.php
(svn version is better ;)

Performance tips for Clojure

[This has been edited since I was wrong about some things]

Clojure is very fast.
It is also extremely easy to write slow Clojure code.

So here are 5 tips that will help you optimize Clojure code if you are suffering from performance problems.
I'm not going to add this as a point, since it has been written all over the Internet, but it is nonetheless the most important thing to keep in mind.
Make it work, then make it right, then make it fast.
Premature optimization is the root of all evil.
Any other famous frase?

Improving the algorithm is almost always better. No matter how well you micro-optimize an algorithm that runs in exponential time, performance is still going to suck. Some of the tips presented here however, deal with algorithmic properties of some Clojure functions and structures.

To measure speed bottlenecks, you need a profiler. A very good profiler is the Yourkit Java Profiler. Unfortunately it is closed-source and not cheap. They release free early-access versions of the software that you can download. As of the time of this writing, a new version just came out and there is no early-access program.

The profiler that I have been using is JVisualVM. It comes with recent JVM's. I don't like it quite as much as Yourkit, but it's very nice and more than enough.

Follow the following steps only if you have exhausted all possible algorithmic improvements.

1. Profile. Edit one thing. Profile again.

Profile your code with your chosen profiler. Identify the bottleneck. Formulate a theory of what is to blame, fix it, and test it. Don't try two things at once. Try one improvement at a time. This is a general optimization strategy that will serve you well if you don't know it already.

2. Beware of reflection

Use (set! *warn-on-reflection* true) so that Clojure warns you about reflection.

Look at the following function:

(defn str-split [s regex]
      (vec (. s split regex)))

Clojure doesn't know if 's' is a string, so it will do an actual search to find a matching method which name is "split" on whatever class 's' belongs to. This will be horribly slow.
It is easily fixed this way:

(defn str-split [#^String s regex]
      (vec (. s split regex)))

This new version tells Clojure that str-split expects 's' to be a string.

3. Understand the Clojure data structures' performance characteristics.
[Turns out I didn't understand them. I'll add something later]

4. Iterating is tricky.

When you are writing functions with side-effects, you will often resort to the good-old 'for' loop. The closest equivalent in Clojure is:

(dotimes [i 100])

This is macro-expanded to something like this

(let* [limit (clojure.core/int 100)]
      (loop [i (int 0)]           
           (when (< i limit)
        (recur (Unchecked-inc i)))))    

..which will be as fast as Java.

If you need a more powerful 'for' loop, it is a very simple macro to write =).

5. Use java primitives.

If you need to do fast arithmetic operations, using encapsulated Integers, Doubles, etc.. is not good enough. You need Java primitives like int,double, etc..

Integer operators do overflow checking to convert Integers and Longs to BigIntegers. You can get around this check by using unchecked operators: unchecked-add, unchecked-dec... etcetera

The usual operators +,*,inc,/, etc.. do not do checking for floats and doubles, and as long as you use primitives they will be fast.

6. When all else fails...
... use Java classes. A Java array will be faster than a Clojure vector. A Java map will be faster than a Clojure map. Use this as a last resort. Clojure's data structures are very fast and should almost always be enough.

This are my tips so far. I may edit this post in the future to add more points if I come up with something or if people that read this suggest something else. I am pretty ignorant with regard to the performance of STM. Maybe someone can add a point about it.