title: TripAdvisor interview. Is there a better algorithm than the one I gave?
body: <p>Just had a phone interview with TripAdvisor (and didn't make the cut).</p>
  
  <p>I was given the code below and asked to implement <code>findBestTravelAlert</code> (in Java).</p>
  
  <hr>
  
  <p>Given a list of TravelAlert objects, find the best travel alert to display for a specific location. See example at <a href="http://www.tripadvisor.com/Tourism-g147306-Haiti-Vacations.html" rel="nofollow">http://www.tripadvisor.com/Tourism-g147306-Haiti-Vacations.html</a></p>
  
  <pre><code> class TravelAlert {
        int id;
        String message;
        int locationId;
   }
  
   class Location {
        int locationId;
        int parentLocationId; // -1 if no parent, location is hierarchy
        String name;
  
        static Location findLocation(int locationId) {...}
   }
  
   class TravelAlertStore {
        private List&lt;TravelAlert&gt; lAlerts; // already populated, static
  
        // Return null if no alert
        TravelAlert findBestTravelAlert(int locationId) {
        // implement this
        }
    }
  </code></pre>
  
  <p><strong>Examples</strong>: If we have 3 travel alerts, one in Boston, one in Massachusetts, and one in the USA:</p>
  
  <ul>
  <li>A user looking at a Boston specific page should see the travel alert of Boston and not the one of Massachusetts</li>
  <li>A user looking at a Massachusetts page should see the travel alert of
  Massachusetts</li>
  <li>A user looking at a Newton specific page should see the
  travel alert of Massachusetts</li>
  <li>A user looking at a NYC specific page
  should see the US travel alert</li>
  <li>A user looking at a Montreal specific
  page should see no travel alert.</li>
  </ul>
  
  <hr>
  
  <p>The way I did it was rather naive, but it was all I could come up with under pressure:<br>
  Search through the list of <code>TravelAlerts</code> and see if the <code>locationId</code> matches that of our <code>locationId</code>. If not, repeat the search and check for matches with the <code>locationId</code> of the parent. If at any point in this process we find a match, return that <code>TravelAlert</code>. If we reach the end of the process (i.e. there is no parent location), return <code>null</code>.</p>
  
  <p>Here's the code:</p>
  
  <pre><code>TravelAlert findBestTravelAlert(int locationId) {
      TravelAlert current_alert = searchList(locationId, lAlerts);
      if(current_alert != null) {
          return current_alert;
      }
      else {
          int parentLocationId = findLocation(locationId).parentLocationId;
          if(parent_locId == -1)
              return null;
          else {
              return findBestTravelAlert(parentLocationId);
          }
      }
  }
  TravelAlert searchList(int locationId, List&lt;TravelAlert&gt; cur_list) {
      if(cur_list == null) {
          return null;
      }
      else if(cur_list.locationId == locationId) {
          return cur_list;
      }
      else {
          searchList(locationId, cur_list.next())
      }
  }
  </code></pre>
  
  <p>The time complexity is <em>O(nk)</em>, where <em>n</em> is the length of the List of TravelAlerts and <em>k</em> is the height of the location hierarchy tree.</p>
  
  <hr>
  
  <p>So, my question is:</p>
  
  <blockquote>
    <ul>
    <li>Is there a better algorithm for doing this, and</li>
    <li>Is there a better way of implementing my algorithm?</li>
    </ul>
  </blockquote>
  
  <p>I'm sure the answer to the second question is yes; there must be built-in methods I could have used, were I more familiar with Java.</p>
  
  <p>Any help would be appreciated. Good luck to all future applicants!</p>