4 ms·

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

by Maro 16y ago

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.

endtime 16y ago
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.
- deleted 16y ago
  [deleted]
- Maro 16y ago
  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.
  - endtime 16y ago
    Okay, fair enough. I probably wouldn't apply for a job like that, but if I were I'd make sure to learn a bit about DBs first, if not networking.
mfukar 16y ago
CS students that haven't taken graph theory yet probably don't know the number of links in a mesh grid. Have you considered that? And honestly, are you telling me that nobody answered in "however long it takes", ie. nobody just counted them on paper?
- endtime 16y ago
  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).
  - mfukar 16y ago
    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).
    - Maro 16y ago
      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.
      - mfukar 16y ago
        That's a failure of the interviewer in my opinion. Means he managed to intimidate (not pressure) the guy/gal enough to back off.
- dagw 16y ago
  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.
toddh 16y ago
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.
- Maro 16y ago
  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.
  - jaf656s 16y ago
    I think you mean complete graph. They are quite different: http://mathworld.wolfram.com/TotalGraph.html http://mathworld.wolfram.com/TotalGraph.html http://mathworld.wolfram.com/CompleteGraph.html http://mathworld.wolfram.com/CompleteGraph.html Thanks, btw, I hadn't actually come across total graph before, you learn something everyday.
  - toddh 16y ago
    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.
  - HenryR 16y ago
    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 :)
Maro 16y ago
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.

by Maro 16y ago

endtime 16y ago

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.

deleted 16y ago
[deleted]
Maro 16y ago
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.
- endtime 16y ago
  Okay, fair enough. I probably wouldn't apply for a job like that, but if I were I'd make sure to learn a bit about DBs first, if not networking.

mfukar 16y ago

CS students that haven't taken graph theory yet probably don't know the number of links in a mesh grid. Have you considered that? And honestly, are you telling me that nobody answered in "however long it takes", ie. nobody just counted them on paper?

endtime 16y ago
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).
- mfukar 16y ago
  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).
  - Maro 16y ago
    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.
    - mfukar 16y ago
      That's a failure of the interviewer in my opinion. Means he managed to intimidate (not pressure) the guy/gal enough to back off.
dagw 16y ago
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.

toddh 16y ago

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.

Maro 16y ago
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.
- jaf656s 16y ago
  I think you mean complete graph. They are quite different: http://mathworld.wolfram.com/TotalGraph.html http://mathworld.wolfram.com/TotalGraph.html http://mathworld.wolfram.com/CompleteGraph.html http://mathworld.wolfram.com/CompleteGraph.html Thanks, btw, I hadn't actually come across total graph before, you learn something everyday.
- toddh 16y ago
  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.
- HenryR 16y ago
  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 :)

Maro 16y ago

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.