title: Check my anagram code from a job interview in the past
body: <p>Had the following as an interview question a while ago and choked so bad on basic syntax that I failed to advance (once the adrenalin kicks in, coding goes out the window.)</p>
  
  <p>Given a list of string, return a list of sets of strings that are anagrams of the input set.  i.e. "dog","god", "foo" should return {"dog","god"}.  Afterward, I created the code on my own as a sanity check and it's been around now for a bit.  I'd welcome input on it to see if I missed anything or if I could have done it much more efficiently.  Take it as a chance to improve myself and learn other techniques:</p>
  
  <p><pre><code>
  void Anagram::doWork(list input, list> &amp;output)
  {
    typedef list &lt; pair &lt; string, string>> SortType;
    SortType sortedInput;<br>
    // sort each string and pair it with the original
    for(list&lt; string >::iterator i = input.begin(); i != input.end(); ++i)
    {
      string tempString(*i);
      std::sort(tempString.begin(), tempString.end());
      sortedInput.push_back(make_pair(*i, tempString));
    }<br>
    // Now step through the new sorted list
    for(SortType::iterator i = sortedInput.begin(); i != sortedInput.end();)
    {
      set&lt; string > newSet;<br>
      // Assume (hope) we have a match and pre-add the first.
      newSet.insert(i->first);<br>
      // Set the secondary iterator one past the outside to prevent
      // matching the original
      SortType::iterator j = i;
      ++j;<br>
      while(j != sortedInput.end())
      {
        if(i->second == j->second)
        {
          // If the string matches, add it to the set and remove it
          // so that future searches need not worry about it
          newSet.insert(j->first);
          j = sortedInput.erase(j);
        }
        else
        {
          // else, next element
          ++j;
        }
      }<br>
      // If size is bigger than our original push, we have a match 
      // - save it to the output
      if(newSet.size() > 1)
      {
         output.push_back(newSet);
      }<br>
      // erase this element and update the iterator
      i = sortedInput.erase(i);
    }
  }
  </pre></code></p>
  
  <p>Here's a second pass at this after reviewing comments and learning a bit more:</p>
  
  <p><pre><code>
  void doBetterWork(list input, list> &amp;output)
  {
    typedef std::multimap&lt; string, string > SortedInputType;
    SortedInputType sortedInput;
    vector&lt; string > sortedNames;<br>
    for(vector&lt; string >::iterator i = input.begin(); i != input.end(); ++i)
    {
      string tempString(*i);
      std::sort(tempString.begin(), tempString.end());
      sortedInput.insert(make_pair(tempString, *i));
      sortedNames.push_back(tempString);
    }<br>
    for(list&lt; string >::iterator i = sortedNames.begin(); i != sortedNames.end(); ++i)
    {
      pair&lt; SortedInputType::iterator,SortedInputType::iterator > bounds;
      bounds = sortedInput.equal_range(*i);<br>
      set&lt; string > newSet;
      for(SortedInputType::iterator j = bounds.first; j != bounds.second; ++j)
      {
        newSet.insert(j->second);
      }<br>
      if(newSet.size() > 1)
      {
        output.push_back(newSet);
      }<br>
      sortedInput.erase(bounds.first, bounds.second);
    }
  }</p>
  
  <p></pre></code></p>