Recently we started interviewing 4-5th year CS students for a C++/database programming job/internship. One of our questions is, if you have 10 computers and all are connected, how many connections do you have in the network (45)? Even after drawing the n=3,4 cases on the whiteboard as graphs, most CS majors cannot answer the question. As we spend more time on these interviews, we're considering making this our first question, and if somebody cannot answer it, however long it takes, interview is over, let's stop wasting each other's time. Similar no-go questions that people have problems with are: what's a JOIN, what does ACID actually mean, the difference between TCP and UDP.
Are you specifying that you want students with database and networking experience? If not, your expectations may be off. I did both my BS and MS in CS (both at schools you've heard of), but concentrated on theory and AI, and I'm not sure I'd get the last two questions right. TCP guarantees packet delivery and UDP doesn't, though I only happened to learn that in passing - for all I know there are other differences too. And I don't actually know what ACID stands for, though if I had to guess I'd say it describes a set of properties that a database may or may not have. But that guess, even if vaguely right, also comes from happening to have seen it in context somewhere, not from my education. Hmm...a friend of mine from grad school just started at Google and I don't think she'd be able to answer those either.
Our ad is "Database startup looking for C++ programmers". Also, here in Hungary CS majors take at least one semester of database, where they learn ACID.
Also, we're not looking for exhaustive answers, eg. in the TCP/UDP case all we want to hear is guaranteed delivery, packet reordering, stream oriented, packet oriented, UDP is good for audio, that's about it.
You should know we're a startup writing a distributed database (hence the n(n-1)/2 question), so virtually all code involves fairly low-level networking, and ACID is an everyday issue. This all of course is obvious from our website, which the interviewee presumably checks. The code is open-source, so they could actually look at the code to see what kind of questions to expect.
I would have said 90 as each node is connection to 9 other nodes if they really are all connected. I wouldn't have considered each connection as bidirectional so no divide by 2. It's possible I would have said 100 because it likely in practice that a program will also have a connection to itself. That's it for me I guess.
I know I used to get nervous during interviews, so we're really nice. It's OK if somebody says 90 or 100 or 10^9 at first, but I think it's a fair expectation that you should be able to figure it out. Btw. the formula for the number of edges of a total graph is n(n-1)/2, which here in Hungary CS majors learn in school. Also, I try to help out by reminding: you have n nodes, each has a connection to n-1 others, but you count each of them twice.
I'm still not completely clear on how filtering on such easily lookup up tactical sort of information will be an indictor or not if they will deliver software. This is like recipe stuff when cooking. I would be frustrated because you obviously have your favorite answer which might be less important than how they would actually solve a problem in a team environment given requirements and a schedule.
Assuming of course that each connection is bidirectional, and if you are modelling the network like a graph then you may not have bidirectional links in order to capture some asymmetric edge weighting for routing purposes :)
The historic reason I give this as an interview question is:
My first distributed networking framework (in our Keyspace product) used unidirectional connections, eg. I had two connections per node-pair (n(n-1) total). This was OK because Keyspace was meant to run on 3 nodes, and it's very easy to handle in terms of code.
However in ScalienDB, which is a generic sharded database meant to be run on 10-100s nodes, I wanted to get that /2 in the formula, after all "easy to handle in terms of code" is not a good excuse for having 2x as many TCP connections on the switch! It was surprisingly error-prone to get this right. The basic problem is both sides initiating connections, and then figuring out which one to drop.
Maybe just ask the question you want to ask? Modern stacks can handle hundreds of thousands of connections these days, so this concern may be outdated. Then you could have a conversation about if there's enough CPU, is there enough RAM to handle the connections, network bandwidth, how you handle replication, failover, structuring software to handle lots of connections, etc, all of which indicate someone may actually know something, but you'll never get to that point because of the magic formula. Often these problems are used as a proxy for something else when you can actually talk about at that something else. Sometimes I think it's just because most people are covering for not knowing about that something else.
Despite my other comment, I actually think anyone smart should be able to answer the complete graph question, especially if you walk through a couple smaller examples. You don't need a class on graph theory to recognize the pattern 1+2+...+(n-1).
You're right, and that's why I asked if nobody really "brute-forced" it, but one probably never knew about meshes and never wondered about the # of links in them until one has had someone describe it to them. My objection, if you will, is that the stimulus for such subjects comes mainly from a class on graph theory (sure, there are exceptions).
By the time the interviewee would be desperate enough to brute force it [were they in a room by themselves], they get so embarassed they say they don't know and they'd rather move on.
You shouldn't need graph theory to simply reason your way to an answer using a bit of thought and some basic arithmetic. Anybody how looks at a problem and goes "oh that looks like X and I don't know X" and then shut of their brains is probably not a great hire.
EDIT: Since a number of people asked, the ad was "Database startup looking for C++ programmers".
Btw., our pre-screening per-email test is to write the in-place remove_char() function which was posted here on HN a couple of months ago [10 LOC], and to write an instrusive stack [50 LOC]. People usually get them wrong but get it right the second time, when I explain what the point is.
