Tuesday, October 26, 2004

The big Expedia Interview

Background
I had a screening interview with Expedia, and then they invited me over to Seattle to do an 'interview loop' there. They paid for me to fly over there, for a hotel room, a rental car, and some food. That was awesome, it felt like I was being 'courted' by a company... which is a friggin' great feeling. So, I flew over there on Sunday, interviewed on Monday, and flew back today (Tuesday).

Interview #1 - Prash
After filling out a bit of paperwork, Prash came and got me, and took me to his office. And so began the day. We chatted for about 20 seconds, and then he gave me a programming problem. The problem was: "Write the 'grow' function for a C++ vector class". Easy enough.
The second problem he gave me was a bit more difficult: Reverse a linked list. It took me about 15-20 minutes to come up with the solution and code it. But, I learned one important 'trick' to these types of interview questions. When you figure out an algorithm that takes a duplicate data structure, you can usually 'massage' the given data structure to get the solution you want.

Interview #2 - Mark The Lunch Interview
So, I got a free lunch at the Expedia cafeteria... but, that didn't mean I wasn't getting more interviewing questions. During lunch, I got the question: "How would you determine if someone has won a game of tic-tac-toe on a board of any size?". This really took me longer than it should have to figure out. The crazy thing is... no matter how big the board is, the solution is constant time.
Then, he gave me a pretty cool question: "The government wants cars to keep track of whether or not they are speeding. The unit to determine this is already able to determine the speed of the vechicle, how would you finish it". So, I spent some time rolling some ideas around in my head. Determined it wasn't feasible to 'read' speed limit signs reliably from a car. Then I thought if the car had a Mapquest-esque database of speed limits, and a GPS to report coordinates to the unit, you could determine if the car was speeding. And, the database could be updated once per year when you get your emissions checked (I know not everyone has to have their emissioned check... but its a good idea).
Then we went back to Mark's office, and the coding questions started. First, I had to write a binary search for a sorted array. I wrote it recursively, because thats the way I learned it. Then he had me write it iteratively... which wasn't too hard either.
Now, you've got an array of size 10^6, with the numbers 0 through (10^6)-1. The array has duplicate entries, so there will me missing numbers. Write a function to find one of the missing numbers. The solution should be in linear time.
Mark was a cool guy, and he'd be fun to work with.

Interview #3 - Ryan
Mark and I actually talked for quite a while about my senior design project. Then, he asked me to code for him (suprise!). Given a sorted array of integers, write a function to remove any duplicates (e.g. 1,2,3,3,3,4,4,5 would go to 1,2,3,4,5). I came up with a solution to this, but it wasn't that good... so we talked about a way to make it better. This was my 'worst' interview... but even this one wasn't too bad.

Interview #4 - Mike(?)
The first one he had me do was: write a function to find the 2 biggest numbers in an array, and return the sum. Then he had me write a function to find the K biggest elements in the array, and return the sum. Both in linear time. There were some good optimizations for this one too.
Then, I had to write a function the removed space from a given array of characters. I told him about the solution that me and Ryan had discussed and how it applied to this problem. Then we talked about a few of the finer points of this problem. I didn't end up having to write any code for that problem, which was good... because my shoulder was getting sore from writing on whiteboards all day (seriously... it still hurts).

Wrap-up with Recruiter - Katy
Then I went and talked with the recruiter about how the day went, yadda yadda. She told me I'd hear back in 5-7 business days.

I spent lots of mental energy coming up with the solutions to those problems... so, I'm not to just divuldge them (plus, I don't want someone to 'beat' my work :)

It was a long day. I got there at about 11AM to fill out some paperwork. I left after my talk with Katy at 4:30PM. It was 5.5 hours of almost pure 'testing'. It was F-U-N though. I learned a few new algorithms, and discovered a few too. It was also D-R-A-I-N-I-N-G... thats a long time to be constantly getting questions and pressure to come up with better solutions.

I've got a little interview with Deloitte on Thursday. So, maybe that means another post for the blog :)

11 comments:

chinarosesz said...

Hi Adam,

My name is Lila, I was doing some googling and found your blog talking about the Expedia interview.

I believe I passed the screen interview and really wanted to know more about your experience with Expedia during the interview.

By the way, was it an internship with Expedia that you were applying for because the questions seem pretty hard.

Let me know, my email is chinarosesz@gmail.com or you can view by blog for more information at http://chinarosesz.blogspot.com

suhasini_varadhan said...

Hi Adam,
I have a on site expedia interview for a Software Test position.Can you please let me know if the interview questions you posted where more for a "Software Design Engineer" Kind of post?Also do they ask more programming questions for Test positions too?
Please email me at suhasini14@gmail.com

Appreciate your help.

Pratik said...

HI Suhasini,

Can you please let me know abt ur Software test position interview @ Expedia...... Mine interview is next in this week.........so please help me.......thanx

Anonymous said...

good one dude. you have described the expedia interview quite well. thanks a lot it was an interesting read.

shaifali said...

Searched for expedia interview and i came to your site. Any idea how are the interviews now ? for an SDE. I heard they are really good and reputed in technology .. and pay decent joining bonus .. :-)

Protex said...

So how long did it take after your final interview to hear back from them?

Just curious about the process.

Ram said...

Hi Guys, Can someone point me to latest SDE interview questions in expedia. I have a Loop Interview request and I am preparing for that.

I would appreciate any help.
Thanks

Anonymous said...

Hi,
I have a phone interview with Expedia tomorrow for about 30 mins. They said that it is going to be a technical interview. what kind of interview questions can I expect. Its for a SDE position. Do they ask any coding, SQL etc questions
Please email me :sushamavti@yahoo.com

Anonymous said...

Can somebody please give me some pointers for Software Engineer in test interview questions. Especially what do they generally ask during telephonic interview . Email me at neetimohindra@yahoo.com

Anonymous said...

You had a lot of tough questions, and it sounds like you did well! Thanks a lot for sharing these.

Anonymous said...

Hello Everyone,

While searching the interview pattern for Expedia I discovered this nice blog.

I have a screening interview next week for Sr. Software Development Engineer post.

Would appreciate if someone can guide/point me on screening round and questions for SSDE post.

You can email me at mishra.p1994@gmail.com

Thanks in Advance.