Java – is there a better algorithm than the one I gave in the TripAdvisor interview?

Just received a telephone interview from TripAdvisor (no reduction)

I got the following code and asked to implement findbesttravelalert (in Java)

Given a list of travelalert objects, find the best travel alert to display for a particular location see http://www.tripadvisor.com/Tourism-g147306-Haiti-Vacations.html Examples of

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<TravelAlert> lAlerts; // already populated,static

      // Return null if no alert
      TravelAlert findBestTravelAlert(int locationId) {
      // implement this
      }
  }

Example: if we have 3 travel reminders, one in Boston, one in Massachusetts and one in the United States:

>Users viewing Boston specific pages should see Boston travel alerts instead of Massachusetts travel alerts > users viewing Massachusetts pages should see travel alerts Massachusetts > users viewing Newton specific pages should see Massachusetts travel alerts > users viewing NYC specific pages should see us travel alerts > View Monterey Travel alerts should not be visible on a specific user's user page

The way I did this was naive, but it was all I came up with under pressure: search the travelalerts list to see if the locationid matches the locationid If not, repeat the search and check for matches with the parent's locationid If we find a match at any time during this process, travelalert. Is returned If we reach the end of the process (that is, there is no parent location), null is returned

This is the 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<TravelAlert> cur_list) {
    if(cur_list == null) {
        return null;
    }
    else if(cur_list.locationId == locationId) {
        return cur_list;
    }
    else {
        searchList(locationId,cur_list.next())
    }
}

The time complexity is O (NK), where n is the length of the travelalerts list and K is the height of the location hierarchy tree

So my question is:

I'm sure the answer to the second question is yes; There must be built-in methods I can use. Am I more familiar with Java

Any help will be greatly appreciated Good luck to all future applicants!

Solution

1) Your searchlist () method doesn't work (or even compile) There is no locationid field on the list. When you try to make a recursive call, you try to pass the elements in the list to the second parameter, where the list is expected

2) You do not follow sun's de facto standard coding conventions or sample coding conventions

3) In general, recursion is less efficient than loops (because you have to keep a large number of stack frames instead of a single pointer / index into the array) – and because both of your recursive functions are tail recursive, they can be replaced by loops

If you don't have a better data structure (for example, the location ID map of travel alerts), or know that the travel alert list has been sorted (you may have obtained some credit), You can save some time calculating the list of location IDS (i.e. the chain from the location of the tree to the top), then walking through the list of travel alerts once (assuming it is much deeper than the location tree) and comparing each alert with the list. The location ID determines the best match