Elliott C. Back: Technology FTW!

The Microsoft Interview Revealed

Posted in Code, Education, Microsoft by Elliott Back on November 3rd, 2004.

This Monday I had an interview with Microsoft for a summer internship position. I decided I would go for the Software Design Engineer in Test. It’s a job that involves writing code to break code, writing secure code, profiling, and a lot of debugging–all things I enjoy. For my classes, I’ve written software compilers that don’t crash on mp3s, games that persist even if the AI or the server dies, and databases that even silly users can’t ruin. It’s interesting how much testing goes into good software. I’ve written code to write testcases for other code, and turned in 40 pages of SML test code for one CS312 assignment. You can see how much I enjoy it!

After we discussed the position, I was asked to write a piece of code to take a 7 digit phone number, and generate all possible combinations of the letters in their 7 places. Imagine a slots machine with 7 spinners. The problem is to write out all the possible slots combinations you could arrive at by pulling the level and spinning each digit. (Aside: I was tempted to write this as a random problem, and draw a random set of digits until I had exhausted the set space. I resisted.)

Here’s simple code to solve this Microsoft problem:

  1. public void myCutiePie(char[] in, int level){
  2.     if(level == in.length){
  3.         System.out.println(in);
  4.         return;
  5.     }
  6.      for(int j = 0; j < 3; j++){
  7.          char temp = in[level];
  8.          in[level] = getNextLetter(temp, j);
  9.          myCutiePie(in, level+1);
  10.          in[level] = temp;
  11.      }
  12. }

The getNextLetter() function just takes a digit and returns the appropriate letter. It’s just a little bit of character arithmetic that I didn’t want to write in an interview without an ASCII reference. Of course, the interviewer didn’t mind, since that wasn’t the point. When I was done, after a false start where I wanted to generate all the combinations of all the letters, he asked me:

How would you test this code?

Well, if I had a better method of generating these permutations, I could test this new one against the verified output of the old one. I would test cornercases–sorted , unsorted, and alternating arrays of digits. I’d test invalid inputs, like an array of size 0, or in a loosely typed language, another datatype. I’d also test some random, easy to check cases, as well. After he looked at my code, he said:

That’s an interesting way to write it.

Apparently he was expecting me to nest 7 for-loops… which is not my idea of good code. And, it would have filled up the whole page. Icky. The next brain teaser was

How do you cut a cake in half where some rectangle has already been cut out?

You have to bisect both rectangles and cut along the line formed by the points of bisection–but he had to walk me through that. Geometry and cakes is not my strong point. After that, we talked more about the position and my qualifications.

All in all, the interview went well, and the famous Microsoft brainteaser coding question didn’t seem as hard as last year’s, where I was expected to reverse a string in place, by word.

Update: I should have mentioned that duplicates were considered OK.

Update 2: My outer loop was duplicating the results from the recursion. No point in doing that!

This entry was posted on Wednesday, November 3rd, 2004 at 8:28 pm and is tagged with software design engineer, summer internship position, digit phone number, nbsp nbsp nbsp nbsp nbsp, microsoft problem, slots machine, software compilers, writing secure code, random problem, good software, test code, println, public void, arithmetic, level 1, digits, combinations, wit, little bit, lt. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback.

Viewing 21 Comments

 

Trackbacks

(Trackback URL)