Solve a set of "restricted" linear equations efficiently

Question

I was recently asked to solve the following challenge (in C++) as part of the interview process. However, I haven't heard from them at all afterwards, and based on past experiences of unsuccessful applicants that I've read online, my submission didn't meet their standards. Since I did solve the challenge to the best of my abilities, I'm at a loss to understand in what ways I could have made a better solution. I'm posting the problem statement (in my own words) and my solution here. Please critique it as you would for a potential applicant to your team (as a means for gauging whether it's worthwhile to have a subsequent phone-screen with such an applicant).

Input Details

The utility would take as input an input file containing a list of equations, one per line. Each equation has the following format: <LHS> = <RHS>, where LHS is the left-hand side of the equation and is always a variable name. RHS is the right hand side of the equation and can be composed of the following only:

• Variables
• Unsigned integers
• The + operator

Assumptions

Input is well-formed i.e.

• Number of variables = Number of equations, with each variable occurring on the LHS of exactly one equation.
• The system of equations has an unique solution, and does not have circular dependencies.
• There are one or more white spaces between each token (numbers, + operator, variables).
• A variable name can only be composed of letters from the alphabet (e.g. for which isalpha(c) is true).
• All integers will fit in a C unsigned long.

Output Format

The utility would print the value of each variable after evaluating the set of equations, in the format <variable name> = <unsigned integer value>. The variables would be sorted in ascending (lexicographic) order.

Sample Input Output

Input file:

off = 4 + r + 1
l   = 1 + or + off
or  = 3 + 5
r   = 2

Expected output for the above input:

l   = 16
off = 7
or  = 8
r   = 2

Implementation Notes

Due to the simplified nature of the input equations, a full-blown linear equation solver is not required in my opinion (as such a solver would have at least quadratic complexity). A much simplified (and asymptotically faster) solution can be arrived at by modeling the set of input equations as a Directed Acyclic Graph (DAG), by observing the dependencies of the variables from the input equations. Once we can model the system as a DAG, the steps to derive the variable values are as follows:

• Construct the dependency DAG, where each node in the graph corresponds to a variable, and \$(a, b)\$ is a directed edge from \$a\$ to \$b\$ if and only if the variable \$a\$ needs to be fully evaluated before evaluating \$b\$.
• Order the vertices in the DAG thus constructed using topological sort.
• For each vertex in the sorted order, evaluate its corresponding variable fully before moving on to the next vertex.

The algorithm above has a linear complexity, which is the best we could achieve under the current assumptions. I've encapsulated the algorithm in the following class (I've used Google's C++ Style Guide in my code - not sure it's the best choice, but I preferred to follow a style guide that's at least recognized by and arrived at by a non-trivial number of engineers.)

Class header file:

//
// Class that encapsulates a (constrained) linear equation solver. See README.md
// for assumptions on input restrictions.
//
#include <unordered_map>
#include <vector>
#include <list>

#ifndef _EVALUATOR
#define _EVALUATOR

class Evaluator
{
  private:
    // Stores the values of each variable throughout algorithm
    std::vector<UL>                      variable_values_;

    // Hash tables that store the correspondence between variable name and index
    std::unordered_map<std::string, UL>  variable_index_map_;
    std::unordered_map<UL, std::string>  index_variable_map_;

    // Adjacency list for DAG that stores the dependency information amongst
    // variables. If A[i, j] is an edge, it implies variable 'i' appears on the 
    // RHS of definition of variable 'j'.
    std::vector<std::list<UL> >          dependency_adj_list_;

    // List of equations stored as indices. If the list corresponding to eq[i]
    // contains 'j', then variable 'j' appears on the RHS of variable 'i'.
    std::vector<std::list<UL> >          equation_list_;

    // For efficiency, this list stores the number of dependencies for each
    // variable, which is useful while executing a topological sort.
    std::vector<UL>                      num_dependencies_;

    // Resets all internal data structures
    void  Clear();  

    // Prints values of internal data structures to aid in debugging
    void  PrintState();

    // Adds an entry corresponding to each new variable detected while parsing input
    UL    AddNewVar(std::string& );

    // Parse the input equations from filename given as argument, and build the
    // internal data structures coressponsing to the input.
    bool  ParseEquationsFromFile(const std::string&);

    // If DAG in dependency_adj_list_ has a valid topological order, returns
    // true along with the ordered vertices in the input vector
    bool  GetTopologicalVarOrder(std::vector<UL>&);

  public:
    Evaluator() {};

    /**
     * @brief Evaluate the set of constrained linear equations and returns the
     *        values of the variables as a list.
     *
     * @param[in]  string: Filename containing list of constrained linear equations.
     * @param[in]  vector<string>: If solution exists, returns the values of
     *             variables in lexicographic order (ascending).
     *
     * @return True if solution exists (always exists for valid input), false if
     *              input is not well-formed (See README.md for more details about input
     *              format).
     */
    bool SolveEquationSet(const std::string&, std::vector<std::string>& );
};
#endif

The main class file:

#include "evaluator.h"
#include <sstream>
#include <unordered_set>
#include <set>
#include <queue>
#include <algorithm>
#include <cassert>

#ifdef _EVALUATOR

// Used for early returns if the expression is false 
#define TRUE_OR_RETURN(EXPR, MSG)    \
  do                                 \
  {                                  \
    bool status = (EXPR);            \
    if (status != true)              \
    {                                \
      cerr << __FUNCTION__           \
           << ": " << MSG << endl;   \
      return false;                  \
    }                                \
  } while(0)                 
#endif

using namespace std;
//****  Helper functions local to the file ****

// Returns true if each character in the non-empty string is a digit
bool IsNumber(string s)
{
  return !s.empty() && std::all_of(s.begin(), s.end(), ::isdigit);
}

// Given a string, returns a vector of tokens separated by whitespace
vector<string> ParseTokensFromString(const string& s)
{
  istringstream   iss(s);
  vector<string>  token_list;
  string          token;
  while (iss >> token)
    token_list.push_back(token);
  return token_list;
}

// Returns true if the string can be a valid variable name (i.e has
// only alphabetical characters in it).
bool IsValidVar(string& v) 
{
  for (auto& c: v)
    TRUE_OR_RETURN(isalpha(c), "Non-alphabetical char in variable: " + v);
  return true;
}

//********************************************

void Evaluator::Clear()
{
  variable_values_.clear();
  variable_index_map_.clear();
  index_variable_map_.clear();
  dependency_adj_list_.clear();
  equation_list_.clear();
  num_dependencies_.clear();
}

void Evaluator::PrintState()
{
  for (auto i = 0U; i < dependency_adj_list_.size(); ++i)
    cout << index_variable_map_[i] << "(" << i << ") =>"  
         << "Value(" << variable_values_[i] << "), Deps(" 
         << num_dependencies_[i] << ")" << endl;
}

// Ensures all data structures correctly set aside an entry for the new variable
UL Evaluator::AddNewVar(string& v)
{
  if (variable_index_map_.count(v) == 0)
  {
    dependency_adj_list_.push_back(list<UL>());
    equation_list_.push_back(list<UL>());
    variable_values_.push_back(0);
    num_dependencies_.push_back(0);
    variable_index_map_.insert(make_pair(v, dependency_adj_list_.size() - 1));
    index_variable_map_.insert(make_pair(dependency_adj_list_.size() - 1, v));

    assert(num_dependencies_.size() == variable_values_.size() &&
           variable_index_map_.size() == variable_values_.size() && 
           variable_values_.size() == dependency_adj_list_.size());
  }
  return variable_index_map_[v];
}

// Parses equation from given input file line-by-line, checking 
// for validity of input at each step and returning true only if 
// all equations were successfully parsed.
bool Evaluator::ParseEquationsFromFile(const string& sEqnFile)
{
  string    line;
  ifstream  infile(sEqnFile);

  // This LUT serves as a sanity check for duplicate definitions of vars
  // As per spec, only ONE definition (appearance as LHS) per variable is handled
  unordered_set<string>  defined_vars; 
  while (getline(infile, line))
  {
    vector<string> tokens = ParseTokensFromString(line);
    string         lhs    = tokens[0];

    // Check if equation is adhering to spec
    TRUE_OR_RETURN(tokens.size() >= 3 && IsValidVar(lhs) && tokens[1] == "=", 
        "Invalid equation: " + line);

    // Check if variable on LHS was previously defined - this would make the 
    // current approach untenable, and require general equation solver.
    TRUE_OR_RETURN(defined_vars.count(lhs) == 0, "Multiple defn for: " + lhs);
    defined_vars.insert(lhs);
    const UL lhs_idx = AddNewVar(lhs);

    // The operands appear in alternate positions in RHS, tracked by isOp
    for (size_t i = 2, isOp = 0; i < tokens.size(); ++i, isOp ^= 1)
    {
      string token = tokens[i];
      if (isOp) 
        TRUE_OR_RETURN(token == "+", "Unsupported operator: " + token);
      else 
      {
        if (IsNumber(token))
          variable_values_[lhs_idx] += stol(token);
        else
        {
          TRUE_OR_RETURN(IsValidVar(token), "Invalid variable name: " + token);

          // Token variable must be evaluated before LHS. 
          // Hence adding token => LHS edge, and adding token to RHS of 
          // equation_list_[lhs]
          auto token_idx = AddNewVar(token);
          dependency_adj_list_[token_idx].push_back(lhs_idx);        
          assert(lhs_idx < equation_list_.size());
          equation_list_[lhs_idx].push_back(token_idx);
          num_dependencies_[lhs_idx]++;
        }
      }
    }
  }
  return (variable_index_map_.size() == dependency_adj_list_.size() && 
          dependency_adj_list_.size() == variable_values_.size());
}

// Execute the BFS version of topological sorting, using queue
bool Evaluator::GetTopologicalVarOrder(vector<UL>& ordered_vertices)
{
  ordered_vertices.clear();
  queue<UL> q;
  for (auto i = 0U; i < dependency_adj_list_.size(); ++i)
    if (num_dependencies_[i] == 0)
      q.push(i);

  while (!q.empty())
  {
    UL var_idx = q.front();
    ordered_vertices.push_back(var_idx);
    q.pop();
    for (auto& nbr: dependency_adj_list_[var_idx])
    {
      assert(num_dependencies_[nbr] >= 0);
      num_dependencies_[nbr]--;
      if (num_dependencies_[nbr] == 0)
        q.push(nbr);
    }
  }
  return (ordered_vertices.size() == dependency_adj_list_.size());
}

// Solves the constrained set of linear equations in 3 phases:
// 1) Parsing equations and construction of the dependency DAG
// 2) Topological sort on the dependency DAG to get the order of vertices
// 3) Substituting the values of variables according to the sorted order,
//    to get the final values for each variable.
bool Evaluator::SolveEquationSet(const string& eqn_file, vector<string>& solution_list)
{
  Clear();
  vector<UL> order;
  TRUE_OR_RETURN(ParseEquationsFromFile(eqn_file), "Parsing Equations Failed");
  TRUE_OR_RETURN(GetTopologicalVarOrder(order), "Topological Order Not Found");

  // Populate variable values in topological order 
  for (auto& idx: order)
    for (auto& nbr: equation_list_[idx])
      variable_values_[idx] += variable_values_[nbr];

  // Get keys from the LUT sorted in ascending order
  set<pair<string, UL> > sorted_var_idx;
  for (auto& vi_pair: variable_index_map_)
    sorted_var_idx.insert(vi_pair);
  for (auto& vi_pair: sorted_var_idx)
    solution_list.push_back(vi_pair.first + " = " + 
        to_string(variable_values_[vi_pair.second]));

  return true;
}
#endif

The usage of the class is as follows:

   string          eqn_file, log_file;
   Evaluator       evaluate;
   vector<string>  solution_list;

   // Logic to get input filename from user - skipping it here
   bool bStatus = evaluate.SolveEquationSet(eqn_file, solution_list); 

   for (auto& s: solution_list)
     cout << s << endl;

Answer 1

I see a number of things that may help you improve your code. Note that I am not referring to Google's C++ style guide, so contradictions between my suggestions and that guide simply mean that Google is wrong. :)

Fix the bugs

There is a spurious #endif at the end of evaluator.cpp that prevents it from being compiled. The evaluator.h class relies on an undefined type UL. If that's something that's defined by your particular compiler, you should be aware that it's non-standard and therefore not portable. I fixed this by adding this line:

using UL = unsigned long;

Make sure you have all required #includes

The evaluator.cpp uses cerr and endl in the TRUE_OR_RETURN macro but doesn't #include <istream>. It also uses ifstream but doesn't #include <fstream>. Also, carefully consider which #includes are part of the interface (and belong in the .h file) and which are part of the implementation. For example, the interface relies on std::string but the .h file is missing #include <string>.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Don't use std::endl when '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl.

Avoid function-like macros

In modern C++, there are very few places that a function-like macro should be used. Let's look at yours:

// Used for early returns if the expression is false 
#define TRUE_OR_RETURN(EXPR, MSG)    \
  do                                 \
  {                                  \
    bool status = (EXPR);            \
    if (status != true)              \
    {                                \
      cerr << __FUNCTION__           \
           << ": " << MSG << endl;   \
      return false;                  \
    }                                \
  } while(0)                 

There are a number of problems with this macro. First, we don't really need the status variable at all. The if could be written: if (!(EXPR)). Second, cerr and endl (if it's used at all, see previous suggestion) should be fully qualified with the std namespace. Third, __FUNCTION__, while common, is not standard. One could use __func__ instead, which is standard. Fourth, I'd much rather see the macro eliminated entirely in favor of simple inline code, not least because printing the internal function name is not very user friendly and is only meaningful to a programmer working on the code.

Use const references where practical

The code currently declares its IsNumber function like so:

bool IsNumber(string s)
{
  return !s.empty() && std::all_of(s.begin(), s.end(), ::isdigit);
}

This has two problems. First it passes by value, so a new string is created on every call. This is quite wasteful of both time and memory. Second, it should actually be a const reference, since s is not modified within the function.

Think carefully about signed versus unsigned

If, indeed, my assumption about UL meaning unsigned long is correct, then this assert is useless:

assert(num_dependencies_[nbr] >= 0);

Because num_dependencies_ is defined as:

std::vector<UL>                      num_dependencies_;

So therefore the assert can never be false.

Declare only one variable per line

The test code includes this line:

string          eqn_file, log_file;

It's generally better style to declare each variable on its own line.

Don't visually align variables

The code currently contains a number of lines that look like these:

string          eqn_file, log_file;
Evaluator       evaluate;
vector<string>  solution_list;

While that may look pretty to some people, and perhaps you use an IDE or other code formatter that does that automatically, in my experience, it simply creates a maintenance headache because another programmer (who perhaps is not using your same tools) who modifies this (e.g. according to these suggestions) to add the missing namespace specifications ends up with this:

std::string          eqn_file; 
std::string log_file;
Evaluator       evaluate;
std::vector<std::string>  solution_list;

Now it doesn't look so pretty, so either that poor programmer has to redo all of the fiddly alignment or better, in my view, is to eliminate it entirely to end up with this:

std::string eqn_file; 
std::string log_file;
Evaluator evaluate;
std::vector<std::string> solution_list;

Rethink your interfaces

Right now, the code is used like this:

bool bStatus = evaluate.SolveEquationSet(eqn_file, solution_list); 

This has a couple of problems. First, why doesn't SolveEquationSet return a solution_list instead of taking it as a parameter (in an overly subtle way, by reference)? Second, it would be much more flexible if it would take a generic istream & rather than a string that's presumed to be a file name. This would allow, for example, simple testing by constructing equations in a std::stringstream and passing a reference to that for evaluation. Third, why is evaluate a class with non-static functions rather than, say a functor? Once it has returned the solution set, there's not really anything useful to do with it, so I'd suggest that the usage should look more like this:

auto solution_list = EquationSolver(infile);
if (solution_list.size() == 0) {
    std::cout << "There are no solutions\n";
} else {
    for (const auto &sol : solution_list) {
        std::cout << sol << '\n';
    }
}

Simplify your algorithm

The solution you've written works, which is good, but it's not very efficient in terms of time or space. Here's an alternative approach:

1. scan each equation into a Variable class which contains the variable name, a std::set of dependencies and a single unsigned for the sum of any constants
2. process the list by adding the value of each Variable with 0 dependencies to the constant of the current Variable, eliminating that Variable from the dependencies
3. repeat from step 2 until all dependency lists are empty

This is guaranteed to work because of the definition of the input equations and uses only a single nested std::set instead of maps, sets, vectors, and queues as with the current solution.

Test the code

We were both wondering about the complexity and runtime speed, so I wrote a test harness. It uses this stopwatch class for timing. I made a slight change to your code to allow it to either take its input from a stream or by passing a filename and put that in "orig.h" and factored out the revised version from this question into "Variable.h".

#include "orig.h"
#include "Variable.h"
#include "stopwatch.h"
#include <fstream>
#include <sstream>
#include <cassert>

std::string original(std::istream &in) {
    static Evaluator evaluate;
    std::vector<std::string> solution_list;
    evaluate.SolveEquationSet(in, solution_list); 
    std::stringstream ss;
    for (const auto &item: solution_list)
        ss << item << '\n';
    return ss.str();
}

std::string Edward(std::istream &in) {
    auto sol{solve(in)};
    std::stringstream ss;
    for (const auto &item: sol)
        ss << item << '\n';
    return ss.str();
}

class TestRig {
public:
    TestRig(std::string myname,
        std::string (*myfunc)(std::istream &in)) :
        name{myname}, testfunc{myfunc}
    {}
    std::string operator()(const std::string &instring) const {
        std::stringstream in{instring};
        Stopwatch<> sw;
        auto solution = testfunc(in);
        sw.stop();
        std::cout << name << ": " << sw.elapsed() << "us\n";
        return solution;
    }
private:
    std::string name;
    std::string (*testfunc)(std::istream &in);
};

static const TestRig tests[]{
    { "Edward", Edward }, 
    { "original", original }, 
};

int main() {
    const std::string input{"b = c + d + 3\nd = e + 4\na = b + c + d + 1\ne = 7\nc = d + 2"};
    std::stringstream in{input}; 
    const auto golden = original(in);
    for (auto testcount = 10; testcount; --testcount) {
        for (const auto &test: tests) {
            auto sol = test(input);
            assert(sol == golden);
        }
    }
}

Results

I compiled the program on my 64-bit Linux machine with g++ version 6.3.1 and -O2 optimization. Here's what I got when I ran the program:

Edward: 18us
original: 32us
Edward: 12us
original: 18us
Edward: 11us
original: 16us
Edward: 10us
original: 15us
Edward: 10us
original: 15us
Edward: 15us
original: 15us
Edward: 10us
original: 15us
Edward: 10us
original: 15us
Edward: 10us
original: 15us
Edward: 10us
original: 15us

So it seems that the revised code is about 50% faster.

Answer 2

For the code: just small things (some of which I already mentioned in the comments):

• The #ifndef _EVALUATOR part should be at the top of your header afaik. So you don't include all libraries again every time. p.s. #pragma once.
• using namespace std; you include a lot of libraries when you do this. Only add the functions you use: e.g. using std::vector.
• To use Evaluator(), you first have to create an object. I would have opted for a singleton instance and/or a static function.
• The 'helper functions' should from OO point of view at least have been part of Evaluator. But you could also have made a(n embedded) class e.g. HelperFunctions that contains the functions as static functions.
• I'm not sure about the TRUE_OR_RETURN macro. It probably works, but you're actually implementing you own exception handling. C++ has try, throw and catch for this purpose.
• Comment your code: if I look at for instance AddNewVar or GetTopologicalVarOrder() I see a lot that is happening, but I have no idea what! There isn't a single line of comment in the code... The person reviewing your code, or later a person maintaining it will have a very hard time trying to understand what the code is doing and why it is doing that.

But now lets look at the bigger picture: you seem to be under the assumption that you were declined because your code did not meet the standards. But is that really the case? You said you never heard from them again, so you don't really know. Did you ever ask them? It could be that something else happened: budgets were cut, they found someone internally, or you had some very good competition (you know: a guy that everyone wants, that has 20 years of experience and works for the salary of a 20-year old)

In my culture (the Netherlands) it is quite common to contact the company to ask what the status of your application is. Usually we call a week after we assumed our application letter was received. Etc. Then, if you are turned down it is quite normal if you ask them for the reasons. I don't see why you should just try contacting them about this. If they don't reply, it might not even be the kind of company you want to work for.

Now you're just making assumptions that your code is bad and worrying about that. But it looks quite reasonable to me.

By the way: What kind (level) of function were you applying for? Senior software architect? Or just a starting position? It could be that you aimed too high for a first job?