Implement the intersection of two sets.
After some discussion of what the "contract" should be between the caller and the function, which I presumed was how you specify what the types of the arguments are and how exceptions are raised/caught, I gave the naive O(n2) algorithm, and noted it as such. There was some discussion afterwards about how to improve it, first by sorting the input sets so comparisons do not always need to traverse the second set each time, but it is still O(n2) on average and worst case. We had a discussion about using hashing, and what type of hash would yield the least likelihood of collisions, but I started losing my train of thought. (As I explained previously, sometimes I just need to stop and think quietly about something.) So the interviewer decided to move on to ...
Explain how traceroute works.
It just so happens that some time ago, I thought about what I would say if I were asked this question. So I was able to get most of the way through this one. The only hiccup was when I said that it sent UDP packets. According to the man page I have (FreeBSD, 1996), it sends UDP packets. The interviewer said that it didn't ... there is a newer traceroute, but I don't remember the details; maybe it doesn't use UDP by default any more. But I was able to explain how the probes work by incrementally increasing the TTL (from zero) each time, and when the TTL is decremented below zero by a router, an ICMP time exceeded packet is sent back to the sender, which logs it as the next hop on the path to the destination. But he seemed reasonably satisfied, so on we went to ...
Describe the three way TCP handshake.
This is something I'd thought about how I would answer it if asked, but it was over a year ago, after reading the 6.829 lectures and the TCP RFC. So my explanation of the handshake was ok, but I didn't mention TCP windows at first, and my explanation was a little fuzzy (although I did explain how dropped packets at a router can cause retransmissions, and how the windows can be reduced to avoid filling the pipe too quickly risking more retransmissions). I could have done a better job of preparation here, but possibly at the expense of covering other questions I might be asked about. We proceeded to ...
If you had a generic operating system, how would you figure out what the average time-slice was for when your process would be scheduled?
I thought to myself "Duh!" ... I really had no clue. I asked if I had tools available, such as system calls, and he said yes. So I was trying to think of some system call that would help me out, but came up empty. Previously in the interview, he said it was ok to ask for hints, so I asked. He asked what would happen if a program was written that repeatedly called gettimeofday() (reads the system clock) and recorded the results. I said that if you throw out the results that come back immediately, you get the results that included overhead, such as the swapping or paging in/out of the process. But there was something about this that bothered me, but I couldn't figure out what it was until now: if the system time comes from NTP (network time protocol), not the internal (hardware) clock, you might get some extra fluctuation. (In fact, this sometimes happened on the AV frontends, which caused time to "go backwards", and I had to explain to people why certain clickstreams appeared to be out of order. I also vaguely remember spending more time on this with a Linux box I had at home.) Anyway, I wasn't really able to get much further with this, and was starting to lose my train of thought. The interviewer wanted me to come up with a way of getting the process to sleep without explicitly calling sleep(), but the best I could come up with was doing something like malloc() (allocate memory) to cause page faults, which he said was like an explicit sleep(). Turns out he actually had to implement something like this, and he created multiple processes that repeatedly obtained and recorded the system time. If these are the only processes running on the machine, each will be swapped out eventually, and the "gaps" will average out to the time slice interval. I told him it sounded interesting (thinking to myself this isn't something I've really had to deal with professionally).
Then came the time for me to ask questions. I asked him what project he was on; he's part of Enterprise Search. I asked him what he did with his 20% time; he spends it on Finance. He actually perked up quite a bit while discussing his 20% time. When I asked if he felt he always had time to devote to his 20% time project, he said that he made an effort to do so. I asked if there were any restrictions on what types of projects one could choose, and he said as long as it fits the general "organize the world's information" ethos, it would probably be OK. However, he recommended that people first ask around various projects to see what was needed. We touched on some other issues such as how long people tend to stay on projects; if people are responsible for what they did on an project they'd left; how one progresses to the point where one is allowed to check code into the release tree. All very interesting. I got the feeling that it might be a good idea to ask about the 20% time in general.
So that was it, basically. I could have done better (hindsight). I've certainly done worse. I don't know if I did well enough to make it to the next round. I think I'm getting a bit better at predicting what types of questions I'll be asked. I still wonder what types of people get most, or all of these questions correct? Part of my problem is that I wasn't fortunate enough during my time at AV to work on high-level engineering issues. But on past projects and jobs, I didn't touch a wide variety of areas of CS. Practically speaking, I can't cover a wide variety of topics, especially if the questions I'm asked are open-ended.
As a final thought, it has occurred to me that if I do make it to additional rounds, one of those rounds might have to take place while I'm on my trip. That will put me at a disadvantage, not being at home, perhaps not having a speakerphone so my hands are free to make notes on paper, not having all of my notes around me of things to remember, perhaps not being able to review things online before the interview.