Interview adjacency list graph problems in C++: proper graph implementation

Question

I know this type of question has been asked before. However, my reason for asking it is gaining insight into what is expected in a 45 min interview when asked to implement graph algorithms. I have never had to give an interview, but have been asked in several interviews, questions pertaining to graphs. Specifically adjacency lists implementations. Several times I have asked the interviewer if they would like me to just implement the algorithm, or if they would prefer the basic structure of the graph too. Most times the response was to provide some level of structure before implementing the algorithm.

Provided the information above, my review request is as follows:

• Is my implementation of a graph (provided below) sufficient?
• Would you as a reviewer of the code be appalled provided I wrote it in under 20 min?
• How would you simplify the code below such that it would be suitable for an interview, and sufficient enough to convey that you could solve problems like depth or breadth first search with it?

namespace graph
{       
  template <typename T>
  struct directed_node
  {
    typedef typename std::list<std::shared_ptr<directed_node<T>>> adjacency_t;

    explicit directed_node(const T &t) :
      m_t(t)
    {}

    void connect(std::shared_ptr<directed_node<T>> node,
      typename adjacency_t::iterator addr)
    {
      auto it = m_adjacents.begin();
      for (it = m_adjacents.begin(); it != m_adjacents.end(); ++it) {
        if (node->m_t == (*it)->m_t) {
          break;
        }
      }

      if (it == m_adjacents.end()) {
        m_adjacents.push_back(node);
        node->m_adjacent_addr = addr;
      }
    }

    T m_t;
    adjacency_t m_adjacents;
    typename adjacency_t::iterator m_adjacent_addr;
  };

  template <typename T>
  struct directed
  {
    typedef typename std::list<std::shared_ptr<directed_node<T>>> adjacency_t;
    adjacency_t m_adjacency_list;

    typename adjacency_t::iterator insert(typename
      std::shared_ptr<directed_node<T>> node)
    {
      auto it = m_adjacency_list.begin();
      for (it = m_adjacency_list.begin(); it != m_adjacency_list.end(); ++it) {
        if ((*it)->m_t == node->m_t) {
          return it;
        }
      }

      return m_adjacency_list.insert(m_adjacency_list.end(), node);
    }
  };

  template <typename T>
  std::shared_ptr<directed<T>> create_directed()
  {
    return std::make_shared<directed<T>>();
  }

  template <typename T>
  std::shared_ptr<directed_node<T>> connect_directed(directed<T> &g,
    const T &from, const T &to)
  {
    std::shared_ptr<graph::directed_node<T>> n1 =
    std::make_shared<graph::directed_node<T>>(from);
    auto it1 = g.insert(n1);
    if (it1 != g.m_adjacency_list.end()) {
      n1 = (*it1);
    }

    std::shared_ptr<graph::directed_node<T>> n2 =
      std::make_shared<graph::directed_node<T>>(to);
    auto it2 = g.insert(n2);
    if (it2 != g.m_adjacency_list.end()) {
      n2 = (*it2);
    }

    n1->connect(n2, it2);

    return n1;
  }
}

int main()
{
  std::shared_ptr<graph::directed<int>> g = graph::create_directed<int>();
  graph::connect_directed(*g, 1, 2);
  return 0;
}

Answer 1

I'll be honest: if you've completed a task in 20 minutes during an interview, I'll probably forgive a lot. I'd assume you made a lot of assumptions about the compilation environment, and you may or may not have had access to reference materials, and that your code is basically as close to pseudocode as it is to actual code. Anyone who can't at least give you that benefit of the doubt is probably someone you don't want to work for.

Given that, there are a few things I'd recommend working on.

Naming

They say that naming things is one of the hardest things in computer science. (And not just computer science - biology has a hold field of taxonomy that classifies and names things. It's hard work!) Looking at your code, it's not immediately obvious to me what the difference between a directed and a directed_node is. They both declare a list of things they're adjacent to, but one has an m_t member and an iterator.

Also, what is m_t? It looks like you're using m_ to represent member variables. That's not my favorite way of doing things, but it makes sense and is a common way of naming things, so I wouldn't ding you for it. But m_t tells me nothing beyond that it's a member of the struct. Is t in this case just an instance of T? I'd prefer something generic like value or data over t, if that's the case. But if you can clarify with a better name than any of those, all the better.

Information Hiding

It's often a good idea to hide the details of how something works from the code which calls it. That allows you to swap out something with the same interface but a different implementation. Given that, I'm wondering why all your member variables are public in directed_node and directed? You probably don't want code outside of the struct changing those values out from underneath you. So make them protected or private.

Simplify

I don't know if this is possible, but you've used std::shared_ptr<directed_node<T> in several places. Would it be possible to define it as a type? You'd probably have to do it twice - once in directed_node and once in directed, which feels wrong. Maybe it's not worth it. Likewise, you've defined adjacency_t twice but with the same definition (assuming that you use the same type for your directed_node and directed). That feels weird, but maybe it's unavoidable? Certainly, I wouldn't ding you for doing this in only 20 minutes. But in a real project, I'd expect to have a code review where we would figure out some way of simplifying that, if possible.