# Nathan Cooprider Phone Interview In Google

Tags: | Posted by Admin on 10/29/2008 9:51 AM | Comments (0)

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(n2). 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:

### Interview questions

Below are some of the technical questions I have been asked in an interview. If you are having a technical interview in Computer Science, use these to warm up:

• Do a deletion on a linked list
• Reverse the bits in an int
• Implement a string search and replace
• Create aligned versions of malloc and free
• Count the color clusters of three or more in a binary tree
• Object-oriented design of an alarm clock
• Return the "Hello" string in C without allocation
• What does printf("abcdef\n"+1); print?
• Store all the words in a book
• Emulate a 7-sided die with 5-sided dice
• Count pairs which add to certain sum in a list
• How do you make a function reentrant?
• What does the stack frame look like during a function call?
• What are the different types of variables? local, global, static, register, pointer
• Write some code to determine the endian-ness of a machine
• Design a file system for a scratchpad memory