Google phone interview

I had a phone interview with Google this morning. Overall it was a pleasant and slightly fun experience. I do not think I botched it up too badly, but I definitely do not think I had a slam dunk either. Here are the questions the Google engineer asked me in the interview:

• Describe pluggable abstract domains to me. This one related directly to my research. It impressed me for two reasons: the interviewer had read and understood my resume and the thing he asked about wasn't RAM compression (which is what everybody else asked about. He had some follow up questions about mathematical functors (which he had studied in school), interval analysis (which he had done before) and dynamic typing (other potential application). He followed up the type theory question by using Lisp as an example.
  
• Simulate a seven-sided die using only five-sided dice. The tricky part of this is generating a uniform distribution between one and seven. Just rolling seven of the five-sided dice does not work because the totals in the middle have higher probability. The solution I eventually arrived at (with a little poke in the right direction by my interviewer) is to change each five-sided die into a binary digit (1-2 are zero, 3-4 are 1, five is a re-roll) and then roll three of them. Interpret the number as binary, with zero being a re-roll.
  
• Come up with an algorithm to count number pairs which add to a certain sum in a list. The "obvious" way to do this is to check the first one with all the others, then the second ones with all the others minus the first one, and so on. The problem is that this is O(n²). The better solution is to sort the list first and then go through and look for the missing half of a pair. In other words, if the first number is one and you want to add to six, look for a five in the list. The complexity of this depends on the sorting methodology. If a bin-sort is able to be used (number of possible values is small) then it is O(n). This is because look up and counting is easy with the bin-sort structure as well. If we can't use bin-sort we have to use another sorting method, plus the lookups are more expensive as well. This results in O(n log n). The interviewer always asked me about the complexity of my algorithm (makes sense, since this is Google).
  

Of course, I will never see these questions again, and you probably won't either. However, just thinking about them is probably good practice for future interviews. I collect the technical questions I am asked in interviews here.