java - TripAdvisor 采访。有没有比我给的算法更好的算法？

Question

刚刚接受了 TripAdvisor 的电话面试(没有成功)。

我得到了下面的代码并要求我实现 findBestTravelAlert(用 Java)。

---

给定一个 TravelAlert 对象列表，找到针对特定位置显示的最佳旅行警报。请参阅 http://www.tripadvisor.com/Tourism-g147306-Haiti-Vacations.html 中的示例

 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
      }
  }

示例:如果我们有 3 个旅行警报，一个在波士顿，一个在马萨诸塞州，一个在美国:

• 查看波士顿特定页面的用户应该看到波士顿的旅行警报，而不是马萨诸塞州的旅行警报
• 查看马萨诸塞州页面的用户应该会看到旅行提醒马萨诸塞州
• 查看 Newton 特定页面的用户应该看到马萨诸塞州的旅行警报
• 查看 NYC 特定页面的用户应该看到美国旅行警报
• 正在查看蒙特利尔特有的用户页面应该看不到旅行警报。

---

我当时的做法很幼稚，但这是我在压力下所能想到的:
搜索 TravelAlerts 列表并查看 locationId 是否与我们的 locationId 匹配。如果不是，请重复搜索并检查是否与父级的 locationId 匹配。如果在此过程中的任何时候我们找到匹配项，则返回该 TravelAlert。如果我们到达流程的末尾(即没有父位置)，则返回 null。

代码如下:

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())
    }
}

时间复杂度是O(nk)，其中n是TravelAlerts列表的长度，k是列表的高度位置层次树。

---

所以，我的问题是:

• Is there a better algorithm for doing this, and
• Is there a better way of implementing my algorithm?

我确定第二个问题的答案是肯定的；如果我对 Java 更熟悉的话，肯定有我可以使用的内置方法。

如有任何帮助，我们将不胜感激。祝所有 future 的申请者好运!

Answer 1

1) 您的searchList() 方法不起作用(甚至无法编译)。 List 上没有 locationId 字段，当您尝试进行递归调用时，您试图将列表中的元素传递到第二个参数，其中列表是预期。

2) 您既没有遵循 Sun 事实上的标准编码约定，也没有遵循示例的编码约定。

3) 通常，递归比循环效率低(因为你必须保留大量堆栈帧而不是，比如说，数组中的单个指针/索引) - 因为你的两个递归函数都是尾递归的它们都可以用循环代替。

没有构建更好的数据结构(例如，位置 id 到旅行警报的 Map)，或者不知道旅行警报列表已排序(您可能会因提及而获得一些荣誉) ，您可能可以通过预先计算位置 ID 列表(即从位置到树顶部的链)然后遍历旅行警报列表一次(假设它比深度大得多)来节省一些时间位置树)并将每个警报与位置 ID 列表进行比较以确定最佳匹配。