I was lucky to get an interview through a company recruiter as a result of applying for a software engineer position via their website. The recruiter called me about a month later and arranged for me to have an on-site interview, which was scheduled a week ahead.

I was interviewed by 4 very technical engineers, and the interview lasted for 4 1/2 hours. The interview was made up of programming questions, design questions, and a discussion of my work over a long period, since I have been in the industry a long time.

Although I had prepared well ahead, I was still C-algorithm-savvy enough to answer some of their questions.

1. Given a binary tree, find the path from leaf node to leaf node such that the values of nodes in between are the maximum. The interviewer was interested more in the maximum sum than the path itself.

2. Write/describe an algorithm to re-sort a rotated sorted array with O(1) complexity.

3. Given an array of integers, design an algorithm to return the sum of all integers in a given range with O(1) complexity. So, sum(i1, i2) returns the sum of all integers from i1 to i2. No for() loops. Now, how would you do it if the array were 2-dimensional?

4. Merge two linked lists. So, if the linked lists are L1 and L2, the resultant list will be L1->next = L2, L2->next = L1(original)->next; ... They may not have the same number of elements.