Détection de référence circulaire

Question

Donc, dans une interview, on m'a posé une simple question qui va comme ceci, disons que j'ai une réponse JSON imbriquée, [a, b, c, d [a, [b, [d, e ], g], h]. On me demande de mettre en œuvre une classe qui peut essentiellement gérer pour stocker ces données et une méthode d'impression de le faire, alors voici ce que j'ai:

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

} 

Maintenant, il dit qu'il y aura des problèmes circulaires de références quand j'imprimer, en d'autres mots j'ai la liste A = [a, b, c, D] et D = [q, t, y, A]. Alors il a dit que je devrais empêcher d'ajouter D en utilisant le checkCircular ci-dessus. J'ai fait une tentative. Aussi juste un nœud que je connais mon recurseJSONode n'est pas correct et l'impression aussi, donc à la recherche d'une suggestion pour résoudre cela aussi .. Je suis juste curieux de ce problème.

Answer 1

d'abord, il devrait être comme

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

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

Vous devez vérifier récursivement, si le nœud donné fait partie du nœud parent et le parent du parent et ainsi de suite ...

Donc, plus comme

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(pNodes.get(i).getNodes(),temp)) 
      return true; 
    } 
    return false; 
    } 

Answer 2

La raison pour laquelle votre vérification circulaire n'est pas correcte est que vous recherchez uniquement une copie existante de JSONode sous le nœud auquel vous essayez de l'ajouter. Mais A peut être sous B et B est sous A, donc chacun est unique dans la liste de ses parents.

Re: utilisation d'une pile pour l'activité de suivi de piste dans une fonction récursive:

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

puis à l'intérieur 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); 
} 

L'avantage de HashSet est que add et remove fonctionnent généralement en temps constant - La taille de l'arbre est sans importance.

À titre de comparaison:

Réponse de Markus Lausberg suggère de faire une recherche récursive complète de l'arbre entier, ce qui serait O (N) où N est le nombre de noeuds dans l'arborescence, et que vous faites ce chèque pour chaque nœud, il finit par être O (N^2). Un arbre de 10 nœuds effectuera 100 comparaisons de nœuds; un arbre de 1000 nœuds fera 1000.0000 comparaisons de nœuds.

Dans la réponse de kan, la vérification implique la recherche de la chaîne parente, qui dépendra de la profondeur de l'arbre. Pour un arbre parfaitement déséquilibré (dans le pire des cas), la profondeur sera la même que le nombre de nœuds, donnant à nouveau O (N^2). Pour un arbre équilibré, la profondeur sera ~ log N, pas beaucoup mieux (rappelez-vous, la vérification doit être faite pour chaque nœud).

L'effet de ces différences dépend de l'opération de comparaison utilisée pour déterminer si deux nœuds sont identiques. Si c'est juste une comparaison de pointeur (c'est-à-dire que vous vous souciez seulement s'ils sont le même objet) et que l'arbre n'est jamais très grand, le surcoût de HashSet peut avoir un impact négatif. Alors que si vous avez besoin de comparer deux nœuds d'une manière plus complexe, donc chaque comparaison est coûteuse, et l'arbre est grand, alors la recherche optimisée de HashSet deviendra bénéfique.