Блог

Итак, в интервью мне на самом деле задали простой вопрос, который звучит примерно так: скажите, что у меня есть вложенный JSON-ответ, [a, b, c, d [a, [b, [d, e], g], h] . Меня просят реализовать класс, который в принципе может обрабатывать для хранения этих данных, и метод печати для этого, так что вот что у меня есть:

 public class JSONode
{
   private String str;
   private JSONode nodes;

   public JSONode (String a, ArrayList<String> n)
   {
        str = a;
        nodes = n;
   }
}

public class JSONResp
{
  private ArrayList<JSONode> arr;

  public JSONResp ()
  {
    arr = new ArrayList<JSONode>();
  }

  public boolean checkCircular(JSONode temp)
  {
    for (int i = 0; i < arr.size(); i  )
    {
        if (arr.get(i).nodes == temp)
            return true;
    }
    return false;
  }

  public void add (JSONode nd)
  {
    if (!checkCircular(nd))
    arr.add(nd);
  }

  public void recurseJSONode(JSONode)
  {
      if (!JSONode.node)
           System.out.print(JSONode.str);
      else {
          System.out.print(JSONode.str);
          recurseJSONode(JSONode.node);
      }
  }

  public void print()
  {
    for (int i = 0; i < arr.size(); i  )
       recurseJSONode(arr.get(i));
  }

  public static void main (String[] args) {
      JSONResp x = new JSONResp();
      x.add(new JSONode("a", null);
      x.add(new JSONode("b", null);
  }

}
  

Теперь он сказал, что при печати будут проблемы с циклическими ссылками, другими словами, у меня есть список A = [a, b, c, D] и D = [q, t, y, A] . Поэтому он сказал, что мне придется запретить добавлять D, используя checkCircular выше. Я предпринял попытку. Кроме того, я знаю, что мой recurseJSONode неверен, как и печать, поэтому ищу предложение по исправлению этого.. Мне просто любопытно узнать об этой проблеме.

Причина, по которой ваша циклическая проверка неверна, заключается в том, что вы ищете только существующий дубликат JSONode под одним узлом, к которому вы пытаетесь его добавить. Но A может находиться под B, а B — под A, поэтому каждый из них уникален в родительском списке.

Re: использование стека для отслеживания активности в рекурсивной функции:

 Set<SomeNodeType> stack = new HashSet<SomeNodeType>();
someRecursiveThing(rootNode, stack);
  

А затем внутри someRecursiveThing:

 void someRecursiveThing(SomeNodeType under, Set<SomeNodeType> stack) {

    if (!stack.add(under)) {
        return;

    // continue happily, e.g. call self with child node,
    // passing down the stack

    SomeNodeType child = ...
    someRecursiveThing(child, stack)

    // finish by removing 'under' from the stack:
    stack.remove(under);
}
  

Преимущество HashSet заключается в том, что add и remove обычно выполняются в постоянное время — размер дерева не имеет значения.

Для сравнения:

Ответ Маркуса Лаусберга предлагает выполнить полный рекурсивный поиск по всему дереву, который будет равен O (N), где N — количество узлов в дереве, и, поскольку вы выполняете эту проверку для каждого узла, в итоге получается O (N ^ 2). Дерево из 10 узлов выполнит 100 сравнений узлов; дерево из 1000 узлов выполнит 1000,0000 сравнений узлов.

В ответе кана проверка включает поиск родительской цепочки, которая будет зависеть от глубины дерева. Для идеально однобокого дерева (в худшем случае) глубина будет такой же, как количество узлов, что снова даст O (N ^ 2). Для сбалансированного дерева глубина будет ~ log N, не намного лучше (помните, проверка должна выполняться для каждого узла).

Эффект этих различий зависит от операции сравнения, используемой для определения того, являются ли два узла одинаковыми. Если это просто сравнение указателей (т. Е. Вам важно только, являются ли они одним и тем же объектом), а дерево никогда не бывает очень большим, накладные HashSet расходы могут оказать негативное влияние. В то время как, если вам нужно сравнить два узла более сложным способом, поэтому каждое сравнение обходится дорого, а дерево большое, тогда оптимизированный поиск HashSet станет полезным.

Прежде всего, это должно быть похоже

 public class JSONode
{
   private String str;
   private ArrayList<JSONode> nodes;

   public JSONode (String a, ArrayList<JSONode> n)
   {
        str = a;
        nodes = n;
   }
}
  

Вы должны рекурсивно проверить, является ли данный узел частью родительского узла и родительского родительского узла и так далее…

Так что больше похоже

 public static boolean checkCircular(JSONode temp)
  {
    if(temp == null){
       return false;
    }

    ArrayList<JSONode> pNodes = temp.getChildrens();

    for (int i = 0; i < nodes.size(); i  )
    {
        if (pNodes.get(i).getString().equals(temp.getString()))
            return true;
        if(checkCircular(temp))
            return true;
    }
    return false;
  }