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 DetailsThe 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:VariablesUnsigned integersThe + operatorAssumptionsInput 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 FormatThe 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 OutputInput file:off = 4 + r + 1l   = 1 + or + offor  = 3 + 5r   = 2Expected output for the above input:l   = 16off = 7or  = 8r   = 2Implementation NotesDue to the simplified nature of the input equations, a full-blown linearequation 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 _EVALUATORclass 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>& );};#endifThe 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)                 #endifusing namespace std;//****  Helper functions local to the file ****// Returns true if each character in the non-empty string is a digitbool IsNumber(string s){  return !s.empty() && std::all_of(s.begin(), s.end(), ::isdigit);}// Given a string, returns a vector of tokens separated by whitespacevector<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 variableUL 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 queuebool 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;}#endifThe 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;
Solve a set of restricted linear equations efficiently
c++;algorithm;object oriented;c++11;interview questions
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 bugsThere 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 #includesThe 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 stdPutting 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 doUsing 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 macrosIn 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 practicalThe 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 unsignedIf, 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 lineThe 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 variablesThe 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 interfacesRight 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 algorithmThe 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: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    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 dependenciesrepeat from step 2 until all dependency lists are emptyThis 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 codeWe 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);        }    }}ResultsI 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: 18usoriginal: 32usEdward: 12usoriginal: 18usEdward: 11usoriginal: 16usEdward: 10usoriginal: 15usEdward: 10usoriginal: 15usEdward: 15usoriginal: 15usEdward: 10usoriginal: 15usEdward: 10usoriginal: 15usEdward: 10usoriginal: 15usEdward: 10usoriginal: 15usSo it seems that the revised code is about 50% faster.