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個旅遊警示，一個在波士頓，一個在馬薩諸塞州，一個在美國：

• 用戶看着波士頓特定頁面應該看到波士頓的旅行警告，而不是馬薩諸塞州的
• 看着馬薩諸塞頁面的用戶應該看到的 旅行警報馬薩諸塞
• 一款採用了一個[R看着牛頓特定的頁面應該看到馬薩諸塞 旅行警報
• 看着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），其中Ñ是TravelAlerts的列表的長度和ķ是位置分層結構樹的高度。

---

所以，我的問題是：

• 是否有這樣做的更好的算法，並
• 有沒有實現我的算法的更好的辦法？

我確定第二個問題的答案是肯定的;必須有我可以使用的內置方法，我是否更熟悉Java。

任何幫助，將不勝感激。祝所有未來的申請人都好運！

Answer 1

1）您的searchList()方法不起作用（甚至編譯）。 List上沒有locationId字段，當您嘗試進行遞歸調用時，您試圖將列表中的元素傳遞到第二個參數，列表是預期的。

2）您沒有遵循Sun事實上的標準編碼慣例或示例的編碼慣例。 3）一般來說，遞歸的效率比循環低（因爲你必須保留大量的棧幀而不是像單個指針/索引到數組中） - 並且由於你的遞歸函數都是尾部遞歸函數，遞歸它們都可以被循環替換。

如果沒有建立更好的數據結構（例如的位置ID用於旅行警報），或者知道旅行警報列表已經排序（您可能已經獲得了一些提及的功勞），您可能可以節省一些通過預先計算位置標識列表（即從位置到樹頂部的鏈），然後行走旅行警報列表一次（假設它遠大於位置樹的深度），並比較每個位置提醒位置ID列表以確定最佳匹配。

Answer 2

如果將警報附加到您的位置樹，您可以加快它的速度。例如（說不上什麼語法，因此認爲這是...）：

+ World 
    + Canada 
    - Montreal 
    + United States [A!] 
    + Massachusetts [B!] 
     - Boston [C!] 
    + New York 
     - Albany 
     - New York City 

然後，只要你能在你的位置樹網頁映射到一個節點，所有你所要做的就是您的方式工作樹尋找旅行警報。如果你沒有看到任何東西，就沒有任何顯示。這將使您的運行時間降至O(k)，其中k是樹的高度。

Answer 3

使用dty所說的話，我去了並編寫了示例以瞭解它的外觀。

第一步是將List轉換爲hashMap。這個想法是，它需要O（N）來完成這個映射，但是之後是O（1）來查找一個位置以查看是否有有效的TravelAlert。

另外，正如dty指出的那樣，遞歸會大量加載堆棧。一個簡單的while（）循環可以用來遍歷locationId和所有潛在的parentIds。

// Return null if no alert 
public TravelAlert findBestTravelAlert(int locationId) { 
    TravelAlert result = null; 

    // Convert list to map 
    HashMap<Integer,TravelAlert> alertMap = new HashMap<Integer,TravelAlert>(); 
    for (TravelAlert a : lAlerts) { 
     alertMap.put(a.locationId, a); 
    } 

    // search the map with the given locationId as well as parentIds of the locationId 
    while (result == null && locationId > 0) { 
     result = alertMap.get(locationId); 
     locationId = Location.findLocation(locationId).parentLocationId; 
    } 

    // TravelAlert returned 
    // if there are no more parentIds, result will still be null 
    return result; 
} 

Answer 4

我寫了這個版本的解決方案，沒有看任何人的答案。然後我看了答案，我認爲雷米可能會更好，但很難說，因爲它取決於數據集。

如果查找位置需要時間，那麼Remy的版本甚至不會調用父級位置的查找，這是一件好事。

我的版本首先查找位置和所有父位置並給它們加權。然後，它遍歷警報列表，並記錄目前爲止發現的最佳匹配。如果它的權重爲零，它將停止遍歷並立即返回。

如果執行位置查找的速度很快（即也是一個HashMap），我認爲我的版本COULD在有大量旅行警報並且可能有多個「最佳匹配」的情況下會更好，因爲您不會必須遍歷第一個列表。

例如，波士頓可能有500個條目。 10,000爲MA。美國500,000。如果您在波士頓的網頁上，只要您爲波士頓選擇了一個，該方法就會返回。

但是，如果查找位置昂貴，雷米的可能會更好。因爲我在開始遍歷列表之前查找所有父母。

TravelAlert findBestTravelAlert(int locationId) { 
    // LocationID mapped to weight (0 is best) 
    HashMap<Integer,Integer> pref = new HashMap<Integer,Integer>();  
    int weight=0; 
    while (locationId != -1) 
    { 
     Location loc = Location.findLocation(locationId); 
     if (loc == null) { 
      // Possibly log an error but don't give up yet 
      break; 
     } 
     pref.put(locationId,weight); 
     weight++; 
     locationId = loc.parentLocationId; 
    } 

    if (pref.size() == 0) { 
     throw new InvalidArgumentException(String.Format("Could not locate location with id {0}", locationId)); 
    } 

    TravelAlert best=null; 
    int bestWeight=Integer.MAX_VALUE; 
    foreach(TravelAlert ta in lAlerts) { 
     Integer wt = pref.get(ta.locationId); 
     if (wt != null && wt < bestWeight) 
     { 
      bestWeight = wt; 
      best=ta;    
     } 
     if (bestWeight == 0) break; 
    } 

    return best; 
} 

Answer 5

我知道這已經很晚了，但是我試着拿出我的解決方案。它會遞歸檢查列表中的父項，直到父項變爲-1。 O(n)

class TravelAlertStore { 
private List<TravelAlert> lAlerts; 

    TravelAlert getLAlert(int locationId) { 
    for (TravelAlert t : lAlerts) { 
     if(t.locationId == locationId) 
     return t; 
    } 
    return null; 
    } 

    int findHierarchy(int locationId) { 

    if(lAlerts.contains(locationId)) 
     return locationId; 

    int parentLocationId = Location.findLocation(locationId).parentLocationId; 
    if(parentLocationId == -1) 
     return -1; 

    return findHierarchy(parentLocationId); 
    } 

    TravelAlert findBestTravelAlert(int locationId) { 

    int bestLocation = findHierarchy(locationId); 

    return bestLocation > -1 ? getLAlert(bestLocation) : null; 
    } 
}