Wednesday, December 10, 2008

Short-Answer Interview Questions

1. What's the difference between passing by value and passing by reference?

2. Describe the singleton pattern.

3. What's the difference between a static method and a static variable?

4. What's the difference between subclasses and interfaces?

5. What are generics?

6. What is the fastest sort? List some O(n log(n)) sorts. What is the pivot in QuickSort? How does the choice of pivot affect QuickSort's runtime?

7. What is the hashcode() / equals() contract in Java?

8. A user enters a URL in his browser, let's say "google.com/index.html". He presses enter, and a little whle later the page renders. Describe what happens in the background.

9. What is AJAX?

Answers coming soon.

Technical Interview Coding Question

Q: We have a very large array A containing positive and negative integers. We want to find a slice (any slice) of this array (i.e. a sub-array of consecutive elements) with at least two elements, such that the sum of the elements in this slice is equal to 0. Bonus: find the largest such slice.

A: We have to beat the brute force solution: checking every possible subarray length & sum.
  bruteForce:
for _length=1..n
for _start=0..n-length
sum elements from _start to _start+_length
if sum = 0
return _start, _start+_length
return false
The time complexity is O(n^2), and the space is constant. We can sacrifice some space to decrease the time; importantly, we can use the silver bullet of all algorithms questions, the hash table. To do this, first find all the partial sums of subarrays that start at index 0. Assuming none of those sum to 0, we notice that if we subtract one partial sum from another, we get 0's. This subtraction represents finding a zero-summing subarray that doesn't start at index 0. So, technially, we could find a subarray by subtracting the partial sums from each other. This doesn't decrease complexity at all, but let's explore the idea. Note that partial sums that can be subtracted from each other to get 0 have to be identical. Ding! We've just redefined the problem: how do we efficiently find two matching elements in an array? At this point, it should be clear that hashing each element and looking for collisions will yield the answer in O(n) time. Returning the indexes of the subarray is trivial: we just attach metadata to the partial sums to represent the end index of the partial sum. Adding the hash table and storing partial sums adds only O(n) space, which is still reasonable.

For the bonus, we can find the longest such subarray by iterating all the way through the partial-sum array, keeping track of the longest subarray so far (by subtracting _end from _start). Code for the non-bonus version below:
  hashMagic: input=array a
define array b, b[0] = a[0]
for i=1..n
b[i] = b[i-1]+a[i]

for j=1..n
hash key = b[j], value = j
if there is a collision
_start = lookup(key = b[j])
_end = j
return _start, _end

return false

Tuesday, September 30, 2008

Interview Time Again!

Wow, first of all - I had this idle hope that people would come across my posts in the future, and would be able to use my experiences to help them prepare for their own interviews. Then I kind of forgot about it, but today, lo and behold, comments! I was going to post a brief thing about preparing for my Hulu interview tomorrow, but I'm newly motivated to actually finish up the Bridgewater story - so here goes!

First, to those who are looking at Bridgewater Associates: please take a moment to review your internet presence, and I don't just mean your facebook or your Google search results! You'll see why in a few minutes.


So, as scheduled, I had the second phone interview with Bridgewater Associates on March 13th, with Ted Yang (instead of Rob Bruce, who was originally scheduled to do it). It was definitely in a class of its own. First off, there were no technical questions. While that's not that unusual for companies not used to recruiting MIT students (see Intuit, Vistaprint, Charles River Analytics) who seem to assume technical knowledge, Bridgewater isn't one of those. All in all, I only really had one technical question, the algorithm from my first phone screen.

In the second interview, all of the questions really centered around one issue: why I wanted to work at Bridgewater. I was asked this at the previous interview and was able to answer it with a generic, "correct" answer based on what I had read on their website. Bridgewater's founder's philosophy is all about an equal sharing of ideas - a conscious step away from the hierarchical model. And so on. Roughly what I gathered from the reading was that there is an emphasis on equality, listening to the little guy, etc. Whether that is actually true, I don't know - but it sure sounds nice. And it's a convincing enough reason for a little engineer to want to work there.

Or so I thought. Ted immediately called me out on my answer, and proceeded to grill me about why I actually want to work there. Here I started sweating; after a bit of discussion, I decided that honesty is the best policy (or rather, when under pressure, I'm not a good bullshitter), and we ended up talking about what was most important to me in choosing where to have an internship. The compensation came out as a very large factor (which Ted readily agreed with), as did the interestingness of the projects I would get to be involved in (this one took some explaining).

At that point Ted let me know he was in a position to offer me a job right then and there. He outlined the program and the housing and compensation packages. Without going into too much detail, the compensation for the 10-week internship he proposed was very good. It even has a sort of "signing bonus." Potential hires take note: it is hard to walk away when you hear this kind of information. I stuck to my original statement that the content of my internship would be very important, though, and convinced Ted that I could not accept the offer until I had a better idea of what the job would entail.

At the very end, before we signed off, Ted mentioned that one of the people I interviewed with was Irish, not Indian, but that he found the mistake amusing. Knowing that the only place I had ever mentioned the accent thing was in this blog, I asked him (with no small level of nervousness) how he found the information. Even though my name isn't actually mentioned on this blog, he had searched Blogger to see what people are saying about Bridgwater, and had come across the post and recognized me. Though he said that nothing I had written was bad (clearly, since I had the offer), let me reiterate my original warning: check your internet presence when job hunting!

Anyway, the story ends there; I got an offer letter (and T-shirt, in my size, though nobody at Bridgewater had physically seen me before) the next day. In the end, I took the Microsoft job, and I don't regret it, though the money wasn't quite as good (the project I managed was great).

Wednesday, June 18, 2008

A Redmond Morning

Well, here I am in the middle of week 3 at my internship at Microsoft. It's still a good time; as a program manager in Office Live (project code name: Albany) working on version 2 of a project that doesn't even come out until July, I (theoretically) have a lot of say in what I do. I get to be creative and work with people throughout the company. The work is actually quite interesting. The other interns here, all 800 of them, include some very cool people too. There are a ton of activities going on every weekend, and, weather permitting, I should be able to get a lot of hiking in. I'm still very excited about how this summer is going to turn out!

On a random note - I've decided (once again) to start a regular running routine, a decision influenced partly by my own fattitude, partly by my recent prehypertensive measurements, and mostly by the fact that my friends back in Cambridge apparently do this every morning at 6:30am. If they can do it, so can I! And,
surprise, I didn't die today despite running on an empty stomach, though admittedly I ran only 2.5 miles (okay, I ran for something closer to 2.0, but whatever). The route is below. Note my deliberate avoidance of the route going east of my apartment; you can't see it here, but there is an immediate ~300ft drop there as the elevation approaches sea level at the local lake. It's tons of fun to run down, and sheer agony trying to make it back up.


Thursday, May 22, 2008

Wednesday, March 12, 2008

Delayed Introduction

Well, enough about that. Now back to the real stuff. For now, I plan to keep this blog about things that are relevant to me (keeping personal rants to the minimum necessary) but could also be useful for people in similar situations. Interviews, as I have them, will pop up here, as will any NLP work that I do in the future as I move toward my M.Eng. Other topics you might see here are:
Linguistics (especially any new observations)
Hiking
Biking / Cycling
Diet / Fitness
Music (especially new or obscure artists or albums)
Books / Music / TV (again, only obscure things; don't have time for much else)
Linux / Web Development (assuming I ever get going on that website of mine)
General interesting news that I might follow (hint: you won't see politics here)
Baby steps to investing and finance
Boston
MIT
And more?

In any case, over the last few weeks/months I've had a lot of interviews, mostly to prepare for the important interviews, but also because I wanted to keep my options open this year. Last year, I only applied to a handful of companies, so every rejection hurt a lot; in addition, I was a sophomore, so there were a number of opportunities that I didn't even get simply because I had no work experience (and presumably not enough class experience). This year, as a junior, the companies seem to want me a lot more. It's really satisfying.

What I want to do here is document them; my experiences should be useful both to me next year and to anyone else who ends up reading these posts. The companies I have interviewed with so far,this year:
Apple (1st round)
Basis Technology (only round)
Bridgewater Associates (1st round)
Click Harmonics (1st & 2nd round)
Google (1st 1st round)
Google (2nd 1st round)
Highbridge Associates (1st round)
Microsoft (1st round)
Microsoft (2nd round)
Morgan Stanley (1st round)
Novantas (1st round)
Vistaprint (1st round)

Posts on these interviews coming soon (though sporadically).

Friday, March 07, 2008

Bridgewater Associates Interview

Woohoo! On Thursday I had a phone interview with Bridgewater Associates, and the next day I got a request for a follow-up with a "senior technologist." That might be a chance for me to fail spectacularly, but at least I get to tell you about the first-round screener.

The Bridgewater interview was definitely fast-paced but not incredibly hard. The phone call had been scheduled for 2:30 on Thursday some weeks earlier; at 2:35 I got the call from "Thomas", and, after a brief disclaimer that I would be recorded and the realization that I was on speakerphone, the questions began. Thomas and the other interviewer (nameless Indian guy, I'm not sure he was ever introduced) right away wanted to know about my work at Charles River Analytics last summer. I told them briefly what the project was and my involvement in it. They wanted more details; this was a pattern throughout the interview - I would explain something, and the would want to know more. "Tell me more about that" or "can you explain that" or (my favorite) "why?" So I went through pretty much every aspect of my coding responsibilities, the team dynamics, and conflict with Eric (a full-timer there) and how I resolved it. It's a good thing I've had so many interviews before, so I had a chance to hone my answers to these CRA questions.

The technical question was the same one that N. had when he applied for a full time position. It is not unlikely that they reuse this one a lot. The question was about taxicab numbers: numbers that can be written as the sum of two distinct pairs of cubes. The problem was to find all taxicab numbers between 1 (1^3) and a million (100^3). My answer was not ideal; I started with the incredibly dumb answer and was walked through the different parts of the solution later. N. had to do detailed run-time analysis, but I did not. I think my interviewers were very interested in my CRA experience (both technical and personal), which did not leave us as much time for the technical question. In any case, there was a hash table involved at the end (remember to use hash tables always!!).

The final question was kind of from left field, though thanks to N. I was expecting something like it. They wanted me to tell them about something interesting that I do or did or have done in the past. I told them about the trip to Patagonia over IAP (January inter-activities period) and how it made me realize I really like hiking. I had not prepared for this question, so I stumbled a bit as they drilled farther and farther into my answer ("why?"), but I think I did okay. The final part was asking them any questions that I had. I asked them about previous intern projects, which took a good couple minutes. Then we were done.

I'll follow this post up with the second-round phone interview; I'm not sure if I'll go out for an on-site even if I do qualify, since I am really leaning towards Microsoft and the PM job right now (oh yeah, I got the offer from them last week). We'll have to see.

Thursday, March 06, 2008

Questions for Interviewers

At the end of an interview, there is almost always at least a little bit it time when the interviewer asks you if you have any questions for him (or, rarely, her). Clearly, since you are already trying your hardest to impress the interviewer with your dazzling brilliance and cutting insight, you'd like to squeeze all you can out of this opportunity. Personally, I have not found a magic bullet question that would turn a bad interview around (if you have, please let me know!). But I have found a few ideas that work pretty well.

1. What is your favorite thing about (working at) [company]?
(Caveat: there are times when this question seems inappropriate, as with highly efficient, question-drilling types like Morgan Stanley or Bridgewater Associates.) Of course, it's one of the standards, so I'm not saying anything new here. But taking a page from Dale Carnegie, what this question is really doing is letting the interviewer talk about him/herself. I mean, your interviewer has sometimes spent the entire day listening to people just like you talk on and on about themselves. He might be thinking, "oh, you little punk, you think you're soooo much better than anybody else, don't you?" Or not - that might be an exaggeration! In any case, your interviewer is narcissistic, maybe a little bored and lonely; I have actually seen interviewers' faces light up when they got to talk about themselves. And if your interviewer feels happy immediately after your interview, I think you might just have boosted your chances.

2. What kinds of projects do the interns at [company] work on?
If you still have time after the last question, this is often a good filler. (Caveat: I have had this fail in situations when the recruiter doesn't ever actually work with or see interns.) This seems to work well whenever you aren't super-familiar with the intern program at a company, especially if you kind of skirted around the "why do you want to work here" question in the first place. This is a good time to insert intelligent questions and look genuinely interested and excited about the projects they describe.

3. What do you hate about (working at) [company]?
This one is really all for you. I've been told that this question can elicit some of the most candid responses and can help you decide whether [company] is a place you really want to work at or not. Personally, I prefer to see the offer before I have to make that decision and go off my intuition and reading up on the internet, but it's another good question to ask.

Monday, February 25, 2008

Microsoft PM Interview

Today I joined the many who have interviewed for a Program Manager Intern position at Microsoft. Apparently, I seemed like a good fit for the Office Live project, and only that project, because that is the only group I interviewed with. So since I've been meaning to start up the blog again, and I feel obliged to add to the information already out there on the process, I'll describe my interview here. In hopes of making this readable, I've divided this post up into sections, wikipedia-style.

1. Welcome (Raquel Garcia) - 9:15am
2. Oli Messenger - 10:00am
3. Sarnath Pai - 12:00pm
4. Tara Brown - 2:00pm
5. Brian - 3:15pm
6. Wrap-up and thoughts (tips!)

Welcome - HR
After arriving at building 19 (the HR center) at 9am, I waited around in a candidate holding room for about 45 minutes. The place was swarming with people, both interns and full-timers. A lot of people were dressed up in suits, in stark contrast to the HR people, who were usually women, who looked like some of my little sister's friends. Or sorority girls. Seriously, there was one blonde, straight-haired woman in a jean skirt and Uggs. They really seemed to want to show what a fun place Microsoft is... there was a Microsoft Surface (which I got to play with for a moment, when it wasn't surrounded by older, awkward-looking guys) and an XBox with Rockband playing, as well as an espresso bar.

Anyway, at 9:45, Raquel Welch finally came out to get me and a full-time applicant and let us know where we were going to go. She let me know that I would be interviewing with the Office Live group. Most people seem to interview with 2 groups, but I guess maybe I am only a good fit for this one. So I hopped on a shuttle (the shuttle drivers are really nice if you talk to them!) to building 31 to meet Oli Messenger (which sounds like some kind of Microsoft product, but oh well.

Office Live - Workspace - Oli Messenger
Oli is short for Oliver, as I learned, and he was British, young, also a program manager, and very friendly. He asked me first about what kind of stuff I like in school (what "modules"). I told him about NLP and why I find it exciting. He then proceeded to the design question, which was pretty open-ended. It was making a system of 2 Roombas. The motivation was that the customer had a big house. The assumptions were that the Roombas could communicate wirelessly, and they could walk up stairs (somehow).

I went through some features that would be cool and hit upon interfacing the Roombas with a PC. He seemed to like that idea, so I drew out the UI and we went over what makes a good UI. I told him it was really dependent on the user; I also decided to add some advanced features to the UI for little home hackers. (I prepped this kind of answer ahead of time, whew!)

Towards the end, he pulled up Office Live Workspace on his computer and showed me some of the features. I asked him about differences between this and Zoho or Google Docs, among other things. He seemed to like answering those questions.

After this, I had an hour-long break (not typical at all). Since my next interview was in the same building, I just stayed in the lobby and connected to the local wireless.

Office Live - Small Business - Sarnath Pai
Sarnath was a lead PM (PM of PMs) in the Small Business side of Office Live. This was my lunch interview. I expected to be doing coding questions in the cafeteria, but instead, it was an exercise in small talk. Fortunately, Sarnath was still relatively young and managed to make me pretty comfortable. We talked about hiking and burgers before moving on to general PM job description stuff. I still didn't really get any questions, so just to keep the conversation going, I talked about my experiences managing an SATPrep program in college.

After getting back from lunch, we had about 30 minutes in the office to do some interviewing. He asked me to sort 50 test scores using "pen and paper." I did counting sort, which was apparently impressive and a surprise to him. The follow-up was that I had to explain why counting sort can be linear when the proven bound on sort is O(n log n). He wasn't that clear, but the point was that the bucket collisions would make counting sort useless. The last question was very open-ended. I had to brainstorm features and uses of an online Office. I listed things that it and other document-sharing services already do, but needed prodding to think of small business applications. Sarnath also mentioned that it could be used to help businesses draw customers using advertising and phone services (Live Search and TellMe).

After this, I had to go, though I had another long break (40 minutes).

Office Live - Workspace - Tara Brown
This was probably my worst interview, but it still wasn't bad. Tara had two questions; she showed me the Office Live workspace and asked me what I would change about it, and she asked me about how I would sync contacts between Facebook, Gmail, other sources, and Outlook. I don't know much about this, particularly network or server stuff, so I suggested a central server that would hold everything, and Outlook would sync with this. She prodded me to add features like a UI for seeing all the contacts online, and having automatic updates of changes in contact details. I argued that a way to see recent changes in details should be included, but she seemed to disagree. We ended on a good note, though, and she went to get my last interviewer.

Office Live - ?? - Brian
I'm not sure exactly who Brian was; I did notice that he seemed to be more "established" that the others, and he mentioned that he is usually everyone's last interview. He also said that if you don't end up having that last interview (#4 for interns, #5 for full-timers), you know you didn't do well. So maybe he was someone with more say as to whether people get hired. Brian asked me about my past work, then asked me to describe something in school that I think could be improved using technology. Since MIT's class registration system sucks more than anything else, I went off about that. I drew a storyboard of the UI for pre-reg on the whiteboard, which Brian seemed to like, since I didn't have to really explain how to improve it. He then asked me about some technology that people aren't using now but might be big later, sort of how Google and iPods became really popular despite the technology being around for a while before they got so huge. I talked about NLP again, and we went on to talk about the future of software and UI's. After this, it was time for me to go, so I took the shuttle back to building 19 to check out.

Wrap-up
Back at building 19, I hung out for a few minutes until the fill-in for Raquel gave me a packet with things to do in the Seattle area and sent me on my way. I'll be hearing back from them within a week or so, I hear, though I may be able to hurry that up if I send Raquel an email.

Overall, I thought the whole interview series was really easy. I felt on top of my game (get plenty of sleep and lots of caffeine!), but most of my energies went to talking about myself and easy UI-type ideas. I felt over-prepared in terms of technical and interview knowledge, but that might have been helpful in terms of feeling comfortable with what to say in front of the interviewers, and when to stop talking. Definitely read up on the interview tips Microsoft sends you. In general, being friendly and casual, with plenty of anecdotes and interest in the details of the position seem to have really helped me. I also always hopped up to the whiteboard whenever I had a design question of any sort, which seemed to go over well. I also told everyone how I like to follow through on plans, and had plenty of anecdotes (like planning Spring Break for a group) on hand.

That's all I have to add; for more tips definitely see this guy's post, which I used to prepare.