Technical Interview

Value: 2% of final grade. Appointments will start on Tuesday, September 2.

Many employers in the software industry — including Microsoft, Google, Amazon, and Facebook — rely on the “technical interview” for their hiring. These interviews largely eschew the stereotypical interview questions (“What's your biggest weakness?”) in favor of questions where you directly establish your ability to write and think about programs. The most common type of question poses a problem, and your job is to think through a good algorithm and then to write code on a whiteboard to solve the problem.

In this assignment, we'll do a 30-minute mock interview with your instructor as the mock interviewer. To be realistic, you will not know the question before the interview starts. However, I will give you one advantage that real interviewers don't: The question will pertain to working with a one-dimensional array of numbers. Here are a few examples of what the question might be:

1. Given an array of numbers, reverse the order of the numbers in the array. For instance, given the array <3, 4, 6, 5>, your method should rearrange the array to have <5, 6, 4, 3>.

2. Given an array of integers betwen 0 and 100, return `true` or `false` depending on whether all numbers in the array appear at most once. For instance, given the array <3, 8, 20, 8>, your method should return `false` (since 8 appears twice), but given <3, 90, 5>, your method should return `true`.

3. Given an array of integers, rearrange the array so that all zeroes in the array are shifted to the end (but the order of the nonzero numbers is preserved). For instance, given the array <4, 0, 8, 0, 0, 4>, you would rearrange the array to be <4, 8, 4, 0, 0, 0>.

4. Given an array of integers, find the length of the longest consecutive sequence of the same integer. For instance, given <2, 2, 5, 5, 5, 2, 0, 2, 2>, you would return 3, since there are three adjacent 5's and no sequence of four or more adjacent numbers. (There are five 2's, but they are not adjacent.)

5. Given an array of digits between 0 and 9, return the integer it corresponds to in base 10. For instance, given the array <1, 0, 2, 4>, you would return the integer 1,024.

(You might use these questions as good ones to tackle for preparation. In these five cases, it happens that there is a O(n) algorithm that the interviewer would expect you to identify.)

I will expect you to write your solution in either Java or C.

Some basic tips for technical interviews:

• When the question is posed, feel free to ask for clarifications on cases not fully addressed in the question. For example, for the last question above, it would be natural to ask what should happen when the integer might be too large to fit into an `int`. In fact, this particular question could impress the interviewer more than actually solving the problem correctly.
• Talk through possible approaches before you start coding. If you're going in a problematic direction, an interviewer will be happy to stop you and give you a hint.
• Explain your code a bit while you write it, to help the interviewer understand.
• Think carefully about whether your solution would work in all cases. For example, you would almost always want to think about what happens if the array contains just one value or even no values at all.

By the way, there are entire books written about these technical interviews: Two of the more popular ones are Cracking the Coding Interview and Programming Interviews Exposed. If you plan to apply for software jobs, they are recommended reading.