Интервью 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 предупреждения о поездках, одно в Бостоне, одно в Массачусетсе и одно в США:

• Пользователь, просматривающий конкретную страницу в Бостоне, должен видеть предупреждение о путешествии в Бостоне, а не в Массачусетсе
• Пользователь, просматривающий страницу Массачусетса, должен увидеть предупреждение о путешествии Массачусетс
• Пользователь, просматривающий конкретную страницу Ньютона, должен увидеть туристическая тревога Массачусетса
• Пользователь, просматривающий определенную страницу Нью-Йорка должен увидеть предупреждение о поездке в США
• Пользователь, смотрящий на Монреаль на странице не должно быть предупреждений о путешествиях.

---

То, как я это сделал, было довольно наивно, но это было все, что я мог придумать под давлением:
Просмотрите список 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 - высота дерева иерархии местоположений. .

---

Итак, мой вопрос:

• Есть ли лучший алгоритм для этого, и
• Есть ли лучший способ реализации моего алгоритма?

Я уверен, что ответ на второй вопрос - да; Должны быть встроенные методы, которые я мог бы использовать, если бы я был более знаком с Java.

Любая помощь будет оценена. Удачи всем будущим претендентам!

Answer 1

Используя то, что сказал 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 2

1) Ваш метод searchList() не работает (или даже не компилируется). В List нет поля locationId, и при попытке сделать рекурсивный вызов вы пытаетесь передать элемент из списка во второй параметр, где ожидается этот список.

2) Вы не следовали ни стандартным соглашениям Sun по фактическому кодированию, ни соглашениям по кодированию, приведенным в примере.

3) Как правило, рекурсия менее эффективна, чем зацикливание (потому что вы должны хранить множество кадров стека вместо, скажем, одного указателя / индекса в массиве) - и поскольку обе ваши рекурсивные функции являются хвостово-рекурсивными оба они могут быть заменены петлями.

Без построения более совершенной структуры данных (например, Map идентификатора местоположения для предупреждения о поездке) или без знания того, что список предупреждений о поездках отсортирован (что вы, вероятно, получили бы за упоминание), вы, вероятно, могли бы сохранить некоторое время, предварительно вычислив список идентификаторов местоположения (то есть цепочку от местоположения до вершины дерева) и затем один раз пройдя список предупреждений о путешествиях (предполагая, что он значительно больше, чем глубина дерева местоположений) и сравнив каждое оповещение со списком идентификаторов местоположения для определения наилучшего соответствия.

Answer 3

Я знаю, что уже поздно, но я попытался придумать свое решение.Он рекурсивно проверяет родителей в списке, пока родитель не станет -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;
  }
}

Answer 4

Это рекурсивное решение, которое может быть не самым эффективным, но выполнит работу.

TravelAlert findBestTravelAlert(int locationId) {
    for (TravelAlert alert : lAlerts {
        if (alert.locationId == locationId) {
            return alert;
        }
    }
    int parentId = Location.findLocation(locationId).parentLocationId;
    if (parentId == -1) {
        return null;
    }
    return findBestTravelAlert(parentId);
}

Answer 5

Я написал эту версию решения, не глядя ни на кого.Затем я посмотрел на ответы и думаю, что Реми мог бы быть лучше, но трудно сказать, потому что это зависит от набора данных.

Версия Реми даже не вызывает поиск родительских местоположений, если естьсоответствует дочернему местоположению, что хорошо, если поиск местоположений занимает время.

Моя версия сначала ищет местоположения и все родительские местоположения и дает им веса.Затем он просматривает список предупреждений и записывает лучшее совпадение, найденное на этом пути.Если он достигает чего-то с нулевым весом, он останавливается и немедленно возвращается.

Если поиск местоположения был быстрым (т.е. также HashMap), я думаю, что моя версия МОЖЕТ быть лучше в ситуации, когда естьтонна предупреждений о поездках и, возможно, более одного «лучшего соответствия», поскольку вам не придется проходить первый список.

Например, для Бостона может быть 500 записей.10000 для МА.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 6

Вы могли бы немного ускорить его, если бы прикрепили оповещения к дереву местоположений. Например (не знаю, что синтаксис S.O. думает, что это в ...):

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

Затем, при условии, что вы можете сопоставить веб-страницу с узлом в дереве местоположений, все, что вам нужно сделать, - это пробраться вверх по дереву в поисках предупреждений о поездках. Если вы попадаете на вершину, не видя ничего, там ничего не отображается. Это уменьшит время выполнения до O(k), где k - высота дерева.