Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Despite saying that graphs are very important, none of my friends have got any graph related questions in interviews in Google and Amazon. I am preparing for these companies right now.

Should I worry about graph related questions?
What are the must-know things in Graph theory before going to interviews?

share|improve this question

closed as primarily opinion-based by Michael Durrant, MichaelT, jwenting, gnat, Ampt Jun 17 at 0:11

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise.If this question can be reworded to fit the rules in the help center, please edit the question.

    
If you're going to be interviewed for a, say, compilers developer position, expect graph theory questions. Otherwise they're unlikely (but you'll be very lucky if you won't face the graph-related problems in your work later). –  SK-logic Dec 14 '11 at 11:27
    
It is really up to the interviewer. If he/she likes graphs nobody forbids him/her to ask about them. –  faif Jun 11 at 9:21

3 Answers 3

From my experience of job interviews at Microsoft I can tell that I never got just a direct question about graphs, but many questions just implied the knowledge of graph algorithms.

The most common topic here are trees as data structures and algorithms on trees: breadth-first and depth-first searches, building the minimal spanning trees.

For directed and/or weighted graphs finding the shortest path between two nodes (the known algorithm of Dijkstra) is a very common problem and I saw it in many collections of sample interview questions.

There are many data structures that are based upon trees, for example heaps, that are quite common in interviews and you should be at least aware of why they are organized this way.

Less common are the algorithms that include the maximal flow calculation, coloring and other specific problems.

The question can be formulated in quite an absract way. During my interview for an intern developer position at Microsoft, for example, I was asked to implement a short algorithm to generate all possible letter combinations for a given phone number and I used tree traversion to derive a recursive algorithm, to discuss its pros and contras and to turn it finally into an iterative one.

share|improve this answer
    
Only seems to represent experiences from interviews at Microsoft. This is valid information but that small a sample is hard to answer the question about whether such questions are common. –  Michael Durrant Jun 10 at 19:30
    
@MichaelDurrant: Why downvote? I specially mentioned that my experience is limited, but I cannot imagine how else one could answer this question. –  Alexander Galkin Jun 10 at 22:51

Having recently interviewed at Google and a few others, graph algorithms have been very uncommon. Trees are the most commonly discussed (directly or indirectly). In terms of algorithms, BFS and DFS are commonly used in solutions.

After BFS and DFS, THE most common topic is heaps, most often the min/max variety. You probably won't be asked to implement one, but you should understand how they work, why you would use them, and how to use one if you were given an implementation.

In my experience, if an interview question involves graphs or specifically trees, some keyword will clue you in. If there is none, formulating the problem as a graph is probably a futile exercise and you'll have to dig yourself out during the interview... Been there.

Hope that helps, best of luck!

share|improve this answer

The questions you get asked will be very dependent on who interviews you. Each interviewer is going to have a different pet area/question. Either I, or acquaintances of mine, have been asked everything from dynamic programming to graph theory, hashing, etc. Pretty much everything in standard CS algorithms and data structures is fair game. Welcome to the "interviewer lottery" that is interviewing.

share|improve this answer
1  
+1 I think this is the best answer. Unfortunately it should have been a comment and that reflects the fact that the question is fairly subjective and opinion based. I doubt you'll get able to get definitive answers, and will likely get everyone's opinions unless someone can cite an actual survey with facts. –  Michael Durrant Jun 10 at 19:28
    
Amusingly enough, this answer started out as a comment but I decided it responded to the question well enough to be an actual answer. The bottom line is that you'll get asked whatever it is that the particular interviewer considers to be important. Questions will vary, even within the same company's interviews. –  Evicatos Jun 10 at 20:23

protected by GlenH7 Jun 10 at 18:42

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.